資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究圖的補圖
設'G−' 是一個簡單圖，其部分頂點與 'G' 的頂點相同，且如果邊在 G 中不存在，則邊 {U, V} 存在於 'G−' 中。這意味著，如果兩個頂點在 G 中不相鄰，則它們在 'G−' 中相鄰。
如果存在於圖 I 中的邊在另一個圖 II 中不存在，並且如果圖 I 和圖 II 組合在一起形成一個完全圖，則圖 I 和圖 II 稱為彼此的補圖。
示例
在以下示例中，圖 I 有兩條邊 'cd' 和 'bd'。它的補圖 II 有四條邊。
請注意，圖 I 中的邊不存在於圖 II 中，反之亦然。因此，這兩個圖的組合給出了一個具有 'n' 個頂點的完全圖。
注意 - 兩個補圖的組合構成一個完全圖。
如果 'G' 是任何簡單圖，則
|E(G)| + |E('G-')| = |E(Kn)|，其中 n = 圖中頂點的數量。
示例
設 'G' 是一個具有九個頂點和十二條邊的簡單圖，求 'G-' 中邊的數量。
你有，|E(G)| + |E('G-')| = |E(Kn)|
12 + |E('G-')| =
9(9-1)2 = 9C2
12 + |E('G-')| = 36
|E('G-')| = 24
'G' 是一個具有 40 條邊和補圖 'G−' 具有 38 條邊的簡單圖。求圖 G 或 'G−' 中頂點的數量。
設圖中頂點的數量為 'n'。
我們有，|E(G)| + |E('G-')| = |E(Kn)|
40 + 38 = n(n-1) 2
156 = n(n-1)
13(12) = n(n-1)
n = 13
更新於： 2019年8月23日
3K+ 次瀏覽
廣告