-
線圖
（圖論概念）
鎖定
- 中文名
- 線圖
- 外文名
- line graph
線圖定義
線圖定理
定理（van Rooij 和 Wilf[1965]）對於簡單圖G，L(H)=G有解當且僅當G是無爪形的並且G的任意雙三角沒有兩個奇三角形。
證明：必要性。設G=L(H)。設e是G的頂點，其相鄰頂點為x,y,z；於是，e在H中對應的邊e與邊x,y,z均關聯。由於e在H中只有兩個端點，x,y,z中必有兩條邊在其中一個端點處關聯到e，於是這兩條邊在G中是相鄰的。因此，爪形不可能是G的誘導子圖。
G中雙三角的頂點必須對應於H中掌形的邊。特別地，G的這兩個三角形中有一個三角形的頂點對應於H中的一個三角形的邊。該三角形定是偶的，因為H中只與三角形的一個頂點關聯的任意邊都恰好與三角形的兩條邊共享一個頂點。因此，在G的任意雙三角形中，至少有一個三角形是偶的。
充分性。設G滿足定理給定的條件。可以假定G是連通的，否則，將下面的構造應用到每個連通分支上即可。下面的這種情況很特殊：G是無爪形的並且某個雙三角的兩個三角形均是偶的。只存在三個這樣的圖。這裏，只考慮一般的情況，即G的任意雙三角恰有一個奇三角形。
根據定理（Krausz[1943]）對於簡單圖G，L(H)=G有解當且僅當G可以分解成完全子圖使得G的每個頂點至多出現在該分解的兩個完全子圖中，只需將C分解成完全子圖並使得任意頂點只在其中兩個完全子圖中出現。令
是G中所有非偶三角形極大完全子圖；令
是屬於某個偶三角形但不屬於任何奇三角形的所有邊。因此斷言，這些完全子圖和邊一起構成了所求的分解B。
每條邊均出現在某個極大完全子圖中；但是，在頂點個數大於3的完全子圖中，每個三角形均是奇的。因此序列中的每個
不含於任意
中；並且
和
沒有公共邊，因為G沒有雙三角使得它的兩個三角形均是奇三角。因此，B中的子圖兩兩之間沒有公共邊。
如果e∈E(G)，則e在某個
中，除非包含e的唯一極大團是一個偶三角形。在這種情況下，e是某個
，因為不允許有雙三角使得它的兩個三角形均是奇三角形。因此B是邊集的一個劃分。
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：3次歷史版本
- 最近更新： 浅笑眉语间