查看“︁補圖”︁的源代码

[[File:Petersen graph complement.svg|thumb|300px|[[佩特森圖]]（左）以及其補圖（右）]]
{{expand English}}
在[[圖論]]裡面，一個圖''G''的'''補圖'''（complement）或者'''反面'''（inverse）是一個圖有著跟''G''相同的點，而且這些點之間有邊相連[[若且唯若]]在''G''裡面他們沒有邊相連。在製作圖的時候，你可以先建立一個有''G''所有點的[[完全圖]]，然後清除''G''裡面已經有的邊來得到補圖。這裡的補圖並不是圖本身的[[補集]]；因為只有邊的部份合乎補集的概念。

== 形式化表述 ==

令<math>G = (V, E)</math>是一个图，<math>K</math>包含所有<math>V</math>的二元子集。则图<math>H = (V, K \setminus E)</math>是<math>G</math>的补图。

== 應用與範例 ==

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

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

== 參考資料 ==

* {{citation
 | last1=Bondy
 | first1=John Adrian
 | authorlink1=John Adrian Bondy
 | last2=Murty
 | first2=U. S. R.
 | authorlink2=U. S. R. Murty
 | title=Graph Theory with Applications
 | year=1976
 | publisher=North-Holland
 | isbn=0-444-19451-7
 | url=http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
 | deadurl=yes
 | archiveurl=https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
 | archivedate=2010-04-13
 | accessdate=2011-07-29
 }}, pages 6 and 29.

* {{Citation

| last=Diestel | first=Reinhard
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
| year=2005
| edition=3rd
| isbn=3-540-26182-6
}}. [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ Electronic edition]{{Wayback|url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ |date=20110728103939 }}, page 4.

{{Stub}}
{{图论}}

[[Category:圖論]]
[[Category:圖形操作]]