圖同構和同態

同構

如果兩個圖 G 和 H 含有數量相等的頂點並且連線方式相同，則稱兩個圖是同構圖 (表示為 G ≅ H)。

檢查非同構比同構容易。如果發生以下任一條件，則兩個圖是非同構的 −

• 連通分量的數量不同
• 頂點集合勢不同
• 邊集合勢不同
• 度序列不同

示例

以下圖是同構圖 −

同態

從圖 G 到圖 H 的同態是一種對映 (可能不是雙射對映) h: G → H，使得 − (x, y) ∈ E(G) → (h(x), h(y)) ∈ E(H)。它將圖 G 的相鄰頂點對映到圖 H 的相鄰頂點。

同態的特性

• 如果同態是雙射對映，則同態是同構。

• 同態始終保留圖的邊和連通性。

• 同態的複合也是同態。

• 找出是否存在另一個圖的同態圖是一個 NP 完全問題。

Mahesh Parahar

更新於: 2019 年 8 月 23 日

7 千次以上瀏覽

職業生涯進階

透過完成課程獲得認證

開始