重圖

在數學中，更具體地為在圖論中， 重圖，也稱多重圖（multigraph）或偽圖（pseudograph）是一個允許有重邊（也稱多重邊，平行邊）的圖。重邊即兩個頂點之間可能存在多條邊。 每一對頂點之間至多有兩條重邊的圖叫2-重圖（2-multigraph）。

含有多重邊（紅色）和自環（藍色）的多重圖。並非所有的多重圖都允許包含自環。

重邊有兩種不同的類型:

• 邊沒有身份:邊的身份僅由其兩端頂點定義。這種情況下，術語「重邊」表示同一條邊在兩個節點間多次出現。
• 邊有身份:邊與節點一樣是基本實體。當多條邊連接兩個節點時，這些邊是不同的邊。

重圖與超圖不同，超圖是指一條邊可以連接任意數量的節點，而不是兩個。

一些學術文章中，偽圖和重圖是同義詞。另一些則認為偽圖是允許有自環的重圖。

無向重圖(沒有同一性的邊)

重圖G是一個有序對G=(V, E)，其中：

• V是一組頂點或節點，
• E是一組無序的頂點對，稱為邊或線。

無向重圖(具有同一性的邊)

重圖G是一個有序的三元組合G=(V, E, r)，其中

• V是一組頂點或節點，
• E是一組邊或線，
• r : E → {{x,y} : x, y ∈ V},為每條邊對應的一對無序節點。

一些文章允許重圖有自環，即一條只與一個頂點連接的邊；而另一些則稱有自環的圖為偽圖，在沒有自環的情況下才是多重圖。

有向重圖(沒有同一性的邊)

有向重圖是允許有向自環存在的有向圖，即具有相同源節點和目標節點的有向邊。有向重圖G是一個有序對G=(V,A)，其中

• V是一組頂點或節點，
• A是一組有序的頂點對，稱為有向邊。

混合重圖G = (V,E,A) 可以用與混合圖類似的方法定義。

有向重圖(具有同一性的邊)

有向重圖G是一個有序的四元組合G=(V, A, s, t)，其中：

• V是一組頂點或節點，
• A是一組邊或線，
• $s:A\rightarrow V$為每條邊對應的源節點，
• $t:A\rightarrow V$為每條邊對應的目標節點。

這個概念可以用來為航空公司建立潛在航線建立模型。在這種情況下，重圖將是一個有向圖，每一對有向平行的代表航線的邊與代表城市的節點連接，以表明有可能多次飛離或飛到某地點。

在範疇論中，一個小的範疇可以被定義為一個有向重圖(邊具有同一性)，它具有結合律，在每個頂點上都有一個結合律和一個可區分的自環作為組合的左右標識。因此，在範疇理論中，「圖」一詞通常被理解為「有向重圖」，該範疇的潛在有向重圖被稱為潛在有向圖。

標籤

重圖和有向重圖也以類似的方式支持圖標記的概念。然而，在這種情況下沒有統一的術語。

帶標記的重圖和帶標記的有向重圖的定義是相似的，在此我們只對後者作定義。

定義1:帶標記的有向重圖是標記有向邊的標記圖。

正式定義：帶標記的有向重圖G是將頂點和有向邊進行標記的重圖。 其嚴格定義為八元組合 $G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})$，其中

• V是一組頂點，A是一組有向邊。
• $\Sigma _{V}$ 和 $\Sigma _{A}$ 是給定字母中可用於作頂點和有向邊標籤的部分。
• $s\colon A\rightarrow \ V$ 和 $t\colon A\rightarrow \ V$是兩個表示有向邊源節點和目標節點的集合。
• $\ell _{V}\colon V\rightarrow \Sigma _{V}$ 和 $\ell _{A}\colon A\rightarrow \Sigma _{A}$ 兩個描述有向邊源節點和目標節點的集合。

定義2:帶標記的有向重圖是標記有向重邊的標記圖，這種邊即為標記了相同頂點和相同方向的邊(注意，標記圖的概念與圖標記中給出的概念不同)。

參見

• 多維網絡
• 圖論術語表
• 圖論

參考文獻

• Balakrishnan, V. K. Graph Theory. McGraw-Hill. 1997. ISBN 0-07-005489-4. 
• Bollobás, Béla. Modern Graph Theory. Graduate Texts in Mathematics 184. Springer. 2002. ISBN 0-387-98488-7. 
• Chartrand, Gary; Zhang, Ping. A First Course in Graph Theory. Dover. 2012. ISBN 978-0-486-48368-9. 
• Diestel, Reinhard. Graph Theory. Graduate Texts in Mathematics 173 4th. Springer. 2010. ISBN 978-3-642-14278-9. 
• Gross, Jonathan L.; Yellen, Jay. Graph Theory and Its Applications. CRC Press. 1998. ISBN 0-8493-3982-0. 
• Gross, Jonathan L.; Yellen, Jay (編). Handbook of Graph Theory. CRC. 2003. ISBN 1-58488-090-2. 
• Harary, Frank. Graph Theory. Addison Wesley. 1995. ISBN 0-201-41033-8. 
• Janson, Svante; Knuth, Donald E.; Luczak, Tomasz; Pittel, Boris. The birth of the giant component. Random Structures and Algorithms. 1993, 4 (3): 231–358. ISSN 1042-9832. MR 1220220. doi:10.1002/rsa.3240040303. 
• Wilson, Robert A. Graphs, Colourings and the Four-Colour Theorem. Oxford Science Publ. 2002 [2019-05-22]. ISBN 0-19-851062-4. （原始內容存檔於2019-07-25）. 
• Zwillinger, Daniel. CRC Standard Mathematical Tables and Formulae 31st. Chapman & Hall/CRC. 2002. ISBN 1-58488-291-3. 

外部連結

•  本條目引用的公有領域材料。材料來自NIST的文檔：Black, Paul E. Multigraph. 演算法與資料結構辭典.