補圖：修订间差异

2023年8月20日 (日) 13:19的最新版本

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

形式化表述

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

應用與範例

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

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