多重圖

含有平行邊的圖稱為多重圖。也稱若圖中某兩個結點之間的邊數多於一條，又允許頂點通過同一條邊和自己關聯，則稱為多重圖。多重圖的定義和簡單圖是相對的。

基本介紹

• 中文名：多重圖
• 外文名：multigraph
• 定義：含平行邊的圖稱為多重圖
• 相關概念：有向圖、無向圖、平行邊等

定義

在無向圖中，關聯一對頂點的無向邊如果多於1條，則稱這些邊為平行邊，平行邊的條數稱為重數。在有向圖中，關聯一對頂點的有向邊如果多於1條，並且這些邊的始點與終點相同(也就是他們的方向相同)，稱這些邊為平行邊。含平行邊的圖稱為多重圖，既不含平行邊也不含環的圖稱為簡單圖。

在圖1中，(a)中 與 是平行邊，在(b)中 與 是平行邊；注意， 與 不是平行邊。(a)和(b)兩個都不是簡單圖。

圖1（a）

t圖1（b）

基礎概念

一個圖是一個有序的二元組<V，E>，記作G，其中

(1) 是有限非空集合，稱為頂點集，其元素稱為頂點或結點。

(2) 是有限集合，稱為邊集，E中每個元素都有V中的結點對與之對應，稱為邊。

邊e既可以是有向的，也可以是無向的。有向邊與有序結點對 對應，這時稱u為e的起點，v為e的終點。無向邊與無序結點對 對應，u，v稱為e的兩個端點。

(3)將圖的集合定義轉化成圖形表示之後，常用 表示圖的邊 ，稱頂點或邊用字母標定的圖為標定圖，否則稱為非標定圖。

(4)將有向圖各有向邊均改成無向邊後的無向圖稱為原有向圖的基圖。

(5)若一條邊連線同一個點，稱其為圈。

(6)若 ，則通常稱它為 圖。p稱為圖G的階。(1，0)圖稱為平凡圖。邊集E為空集的圖稱為零圖。頂點集V和邊集E都是有限集的圖稱為有限圖。 、

(7)若 ，則稱點u與點v相鄰接。並說點u與邊e相關聯，點v與邊e相關聯。同樣，若邊e和邊f有一個共同的端點，則也稱邊e和邊f相鄰接。沒有邊關聯於它的頂點稱為孤立點，不與其他任何邊相鄰接的邊稱為孤立邊。

多重圖的矩陣表示

可以用類似於有向圖的方法，用矩陣來表示一個多重圖，其中每個元素 ，若從 到 無邊相連，則有 ；若有邊相連，且其重數為k，則 。

有向多重圖

圖2

圖2中的圖形描繪了一個有向多重圖(directed multi-graph)。在頂點W上有一個有向環(directed loop)h，從V到X存在平行有向邊(parallel directed edges)i和j。因為有向圖也是一種特殊的有向多重圖，所以在有向多重圖上給出的定義也可以套用於有向圖。

注意：諸如f和m這樣的有向邊不是平行有向邊，但i和j是平行有向邊。

如果對每個 ，則稱頂點和有向邊的交替序列

為從 到 的有向通路(directed path)。這條有向通路的長度為n，即有向邊的數目。所以R，a，S，b，T， e，W是一條從R到W長度為3的通路，也可以記作：R，S，T，W或a，b，e。由於從V到X存在兩條有向邊，有向通路V，i，X，k，U，m，V，j，X不能只用頂點來描述。但是，這條有向通路可以通過僅列出有向邊i，k，m，j來描述。此外，T，b，S，d，V不是有向通路，因為有向邊b不是從T到S而是從S到T的。同樣，不存在從Y出發的長度為正數的有向通路。如前所述，一個頂點是長度為0的有向通路。

有向通路a，d，g是一條從R到W的簡單有向通路(simple directed path)。即沒有重複頂點的有向通路。有向通路a，d，i，k，m，g不是簡單有向通路，這是因為頂點V重複出現了，容易看出每條有向通路都包含一條簡單有向通路。

定理 每一條U-V有向通路都包含一條U-V簡單有向通路。

圖2中的有向通路a，d，f，c是一個有向迴路(directed cycle)，因為在這條從P到R的長度為正數的有向通路中不存在其他被訪問兩次的頂點。但是，b，e，g，d不是有向迴路，這是因為有向邊g和d的方向不對。h和f，m都可看作有向迴路。有向通路k，m，f，c，a，d不是有向迴路，這是因為頂點U和V出現了兩次。在有向多重圖D中，如果對每對頂點A和B都存在一條從A到B的有向通路，那么稱D為強連通(strongly connected)的。所以，在一個強連通的有向多重圖中，可以沿著有向邊，按照某條路線從任何一個頂點出發到達其他任何一個頂點。