補圖 - 维基百科，自由的百科全书

此條目可参照英語維基百科相應條目来扩充。 若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。

在圖論裡面，一個圖G的補圖（complement）或者反面（inverse）是一個圖有著跟G相同的點，而且這些點之間有邊相連若且唯若在G裡面他們沒有邊相連。在製作圖的時候，你可以先建立一個有G所有點的完全圖，然後清除G裡面已經有的邊來得到補圖。這裡的補圖並不是圖本身的補集；因為只有邊的部份合乎補集的概念。

形式化表述[编辑]

令${\displaystyle G=(V,E)}$是一个图，${\displaystyle K}$包含所有${\displaystyle V}$的二元子集。则图${\displaystyle H=(V,K\setminus E)}$是${\displaystyle G}$的补图。

應用與範例[编辑]

許多圖論的概念都互相以補圖的關係連接：

• 無邊圖的補圖是完全圖，反之亦然。
• 獨立集的補圖是团，反之亦然。
• triangle-free graph的補圖是claw-free graph。
• self-complementary graph是一個與自己的補圖同構的圖。
• Cograph是由不交並（可參考集合論的不交並）以及補集建立起來圖的集合。而且，這個集合是self-complementary；也就是說，任何cograph的補圖也必然是cograph（雖然可能不是同構的圖）。

參考資料[编辑]

• Bondy, John Adrian; Murty, U. S. R., Graph Theory with Applications, North-Holland, 1976 [2011-07-29], ISBN 0-444-19451-7, （原始内容存档于2010-04-13） , pages 6 and 29.

• Diestel, Reinhard, Graph Theory 3rd, Springer, 2005, ISBN 3-540-26182-6 . Electronic edition（页面存档备份，存于互联网档案馆）, page 4.

这是一篇小作品。你可以通过编辑或修订扩充其内容。 查 论 编