線せん圖ず

在ざい图论中なか，图 $G$ 所ところ对应的てき线图是ぜ一いち张能够反映はんえい $G$ 中ちゅう各かく边邻接せっ性せい的てき图，记作 $L(G)$ 。简单来らい说， $L(G)$ 将はた $G$ 中なか的てき每ごと条じょう边各自かくじ抽象ちゅうしょう成なり一いち个顶点てん；如若原げん图中两条边相邻，那な么就给线图中对应顶点之の间连接せっ一いち条じょう边。因よし为线图将原げん图的边化作さく了りょう顶点，所以ゆえん也可以将其视作原さくはら图的一いち种对偶。

哈斯勒·惠めぐみ特とく尼あま证明了りょう：假定かてい图 $G$ 是これ连通的てき，那な么除了りょう一种特殊情况外，我わが们总能のう根ね据すえ线图 $L(G)$ 的てき结构还原出で $G$ 的てき结构^[1]。以该定理ていり为中介かい，可か以证明あかり线图的てき许多其它性せい质。线图总是无爪图，即そく线图的てき所有しょゆう导出子こ图均ひとし不ふ是ぜ $K_{1,3}$ 。

正式せいしき定義ていぎ

圖ず $G$ 的てき線せん圖ず $L(G)$ 定義ていぎ如下：

$L(G)$ 的てき一いち個こ頂點ちょうてん對應たいおう $G$ 的てき一いち邊へん

$L(G)$ 的てき頂點ちょうてん相しょう鄰若わか且唯若わか它們在ざい $G$ 對應たいおう的てき邊あたり相しょう鄰（有ゆう公共こうきょう頂點ちょうてん）。

该定义也可か以用图论的てき语言表ひょう述じゅつ如下：设 $G=(V,E)$ ，那な么 $L(G)=(E,{\tilde {E}})$ ，且 $(e_{1},e_{2})\in {\tilde {E}}\iff e_{1}\cap e_{2}\neq \emptyset$ 。

例れい子こ

下面かめん的てき例れい子こ演えんじ示しめせ了りょう由ゆかり原げん图生成せいせい线图的てき流りゅう程ほど。

原圖げんず
製作せいさく線せん圖ず的てき過程かてい
結果けっか

性質せいしつ

由ゆかり原げん图转移うつり过来的てき性せい质

根ね据すえ线图的てき定てい义，若わか性せい质／概念がいねんP仅取决于原げん图 $G$ 中ちゅう边的邻接性せい，那な么P便びん可か以转移うつり（或ある者もの说对偶）到いた线图 $L(G)$ 上うえ去さ变成性せい质／概念がいねんP'，刻こく画が线图顶点的てき邻接属性ぞくせい。例れい如，图 $G$ 中なか的てき一いち个匹ひき配はい指ゆび的てき是ぜ图中一组不相交的边，把わ这一概念平移到线图上去，就等价于线图的てき一组不相邻的顶点——用よう术语来らい说即线图上じょう的てき一いち个独立どくりつ集しゅう。

下面かめん就列举了原げん图和线图之の间的若干じゃっかん联系：

若わか原圖げんず是ぜ連れん通どおり的てき，線せん圖ず也是。
若わか两个图同构，那な么它们的线图也同构。
若わか $G$ 的てき顶点数すう和わ边数分ぶん别为 $n$ 和わ $m$ ，那な么 $L(G)$ 的てき顶点数すう和わ边数分ぶん别是 $m$ 和わ ${\textstyle \sum _{v}{\binom {\deg(v)}{2}}}$ 。
$\chi _{E}(G)=\chi _{V}(L(G))$ ，即そく原圖げんず的てき邊あたり色しょく數すう等とう於線圖ず的てき點てん色しょく數すう。
$G$ 中なか的てき一个匹配对应了 $L(G)$ 中なか的てき一いち个独立どくりつ集しゅう，且其大小だいしょう相等そうとう。于是， $G$ 中ちゅう最大さいだい匹ひき配はい的てき大小だいしょう等とう于 $L(G)$ 最大さいだい独立どくりつ集しゅう的てき大小だいしょう。借か助じょ这一关系，可か以通过求解かい后きさき者しゃ来らい求もとめ解かい前者ぜんしゃ，但ただし反はん之これ不ふ总是可か行ぎょう，因いん为并非ひ所有しょゆう图都能のう表示ひょうじ为某个 $G$ 的てき线图。在ざい计算机つくえ科学かがく中ちゅう，最大さいだい匹ひき配はい问题和わ最大さいだい独立どくりつ集しゅう问题是ぜ两个重要じゅうよう的てき问题。前者ぜんしゃ已やめ经被高だか效こう解かい决（Edmonds' Blossom Algorithm）；而后者しゃ则是NP完全かんぜん问题，被ひ普遍ふへん认为无法高だか效こう求もとめ解かい。
若わか $G$ 存在そんざい欧おう拉ひしげ回路かいろ，则 $L(G)$ 存在そんざい哈密顿回路ろ，但ただし反はん之これ不ふ然しか。

惠めぐみ特とく尼あま同どう构定理ていり

惠めぐみ特とく尼あま同どう构定理ていり^[1]阐述了りょう以下いか事こと实：设有连通图 $G_{1}$ 和わ $G_{2}$ 且它们均不ふ是ぜ三角形さんかっけい $K_{3}$ 或ある爪つめ形がた $K_{1,3}$ 。如果 $L(G_{1})\cong L(G_{2})$ ，那な么 $G_{1}\cong G_{2}$ 。也就是ぜ说，除じょ了りょう极特殊こと的てき情じょう形がた，图 $G$ 的てき结构可か以由线图 $L(G)$ 的てき结构中ちゅう唯一ゆいいつ地ち恢复出来でき。

其它性せい质

任にん何なん的てき线图都と是ぜ无爪的てき，亦また即そく不ふ包含ほうがん $K_{1,3}$ 作さく为导出で子こ图。因よし此，任意にんい含有がんゆう偶数ぐうすう个顶点てん的てき连通线图都と存在そんざい完かん美び匹ひき配はい。

线图 $L(G)$ 的てき邻接矩のり阵 $A_{m\times m}$ 的てき全部ぜんぶ特とく征せい值都不ふ小しょう于-2。这是因いん为 $A=J^{\operatorname {T} }J-2I$ ，其中 $J_{n\times m}$ 是ぜ原げん图 $G$ 的てき关联矩のり阵（incidence matrix）。又また由よし于矩阵 $J^{\operatorname {T} }J$ 是ぜ半はん正せい定じょう的てき，所以ゆえん $A$ 的てき任にん何なん特とく征せい值 $\lambda$ 均ひとし满足 $\lambda +2\geq 0$ 。