^ 1.01.1Whitney, Hassler. . American Journal of Mathematics. 1932-01, 54 (1): 150 [2020-10-23]. doi:10.2307/2371086. (原始内容存档于2020-10-26).
^Beineke, Lowell W. . Journal of Combinatorial Theory. 1970-09-01, 9 (2): 129–135 [2020-10-23]. ISSN 0021-9800. doi:10.1016/S0021-9800(70)80019-9. (原始内容存档于2020-10-30) (英语).
行進 17, 2024
線圖, 此條目目前正依照en, line, graph上的内容进行翻译, 2020年10月23日, 如果您擅长翻译, 並清楚本條目的領域, 欢迎协助翻譯, 改善或校对本條目, 此外, 长期闲置, 未翻譯或影響閱讀的内容可能会被移除, 目前的翻译进度为, 在图论中, 图g, displaystyle, 所对应的线图是一张能够反映g, displaystyle, 中各边邻接性的图, 记作l, displaystyle, 简单来说, displaystyle, 将g, displaystyle, 中的每条边各自抽象成一个. 此條目目前正依照en line graph上的内容进行翻译 2020年10月23日 如果您擅长翻译 並清楚本條目的領域 欢迎协助翻譯 改善或校对本條目 此外 长期闲置 未翻譯或影響閱讀的内容可能会被移除 目前的翻译进度为 80 在图论中 图G displaystyle G 所对应的线图是一张能够反映G displaystyle G 中各边邻接性的图 记作L G displaystyle L G 简单来说 L G displaystyle L G 将G displaystyle G 中的每条边各自抽象成一个顶点 如若原图中两条边相邻 那么就给线图中对应顶点之间连接一条边 因为线图将原图的边化作了顶点 所以也可以将其视作原图的一种对偶 哈斯勒 惠特尼证明了 假定图G displaystyle G 是连通的 那么除了一种特殊情况外 我们总能根据线图L G displaystyle L G 的结构还原出G displaystyle G 的结构 1 以该定理为中介 可以证明线图的许多其它性质 线图总是无爪图 即线图的所有导出子图均不是K 1 3 displaystyle K 1 3 目录 1 正式定義 2 例子 3 性質 3 1 由原图转移过来的性质 3 2 惠特尼同构定理 3 3 其它性质 4 等价刻画 5 参考文献正式定義 编辑圖G displaystyle G nbsp 的線圖L G displaystyle L G nbsp 定義如下 L G displaystyle L G nbsp 的一個頂點對應G displaystyle G nbsp 的一邊L G displaystyle L G nbsp 的頂點相鄰若且唯若它們在G displaystyle G nbsp 對應的邊相鄰 有公共頂點 该定义也可以用图论的语言表述如下 设G V E displaystyle G V E nbsp 那么L G E E displaystyle L G E tilde E nbsp 且 e 1 e 2 E e 1 e 2 displaystyle e 1 e 2 in tilde E iff e 1 cap e 2 neq emptyset nbsp 例子 编辑下面的例子演示了由原图生成线图的流程 nbsp 原圖 nbsp 製作線圖的過程 nbsp 結果性質 编辑 nbsp 有些圖總不是線圖由原图转移过来的性质 编辑 根据线图的定义 若性质 概念P仅取决于原图G displaystyle G nbsp 中边的邻接性 那么P便可以转移 或者说对偶 到线图L G displaystyle L G nbsp 上去变成性质 概念P 刻画线图顶点的邻接属性 例如 图G displaystyle G nbsp 中的一个匹配指的是图中一组不相交的边 把这一概念平移到线图上去 就等价于线图的一组不相邻的顶点 用术语来说即线图上的一个独立集 下面就列举了原图和线图之间的若干联系 若原圖是連通的 線圖也是 若两个图同构 那么它们的线图也同构 若G displaystyle G nbsp 的顶点数和边数分别为n displaystyle n nbsp 和m displaystyle m nbsp 那么L G displaystyle L G nbsp 的顶点数和边数分别是m displaystyle m nbsp 和 v deg v 2 textstyle sum v binom deg v 2 nbsp x E G x V L G displaystyle chi E G chi V L G nbsp 即原圖的邊色數等於線圖的點色數 G displaystyle G nbsp 中的一个匹配对应了L G displaystyle L G nbsp 中的一个独立集 且其大小相等 于是 G displaystyle G nbsp 中最大匹配的大小等于L G displaystyle L G nbsp 最大独立集的大小 借助这一关系 可以通过求解后者来求解前者 但反之不总是可行 因为并非所有图都能表示为某个G displaystyle G nbsp 的线图 在计算机科学中 最大匹配问题和最大独立集问题是两个重要的问题 前者已经被高效解决 Edmonds Blossom Algorithm 而后者则是NP完全问题 被普遍认为无法高效求解 若G displaystyle G nbsp 存在欧拉回路 则L G displaystyle L G nbsp 存在哈密顿回路 但反之不然 惠特尼同构定理 编辑 惠特尼同构定理 1 阐述了以下事实 设有连通图G 1 displaystyle G 1 nbsp 和G 2 displaystyle G 2 nbsp 且它们均不是三角形K 3 displaystyle K 3 nbsp 或爪形K 1 3 displaystyle K 1 3 nbsp 如果L G 1 L G 2 displaystyle L G 1 cong L G 2 nbsp 那么G 1 G 2 displaystyle G 1 cong G 2 nbsp 也就是说 除了极特殊的情形 图G displaystyle G nbsp 的结构可以由线图L G displaystyle L G nbsp 的结构中唯一地恢复出来 其它性质 编辑 任何的线图都是无爪的 亦即不包含K 1 3 displaystyle K 1 3 nbsp 作为导出子图 因此 任意含有偶数个顶点的连通线图都存在完美匹配 线图L G displaystyle L G nbsp 的邻接矩阵A m m displaystyle A m times m nbsp 的全部特征值都不小于 2 这是因为A J T J 2 I displaystyle A J operatorname T J 2I nbsp 其中J n m displaystyle J n times m nbsp 是原图G displaystyle G nbsp 的关联矩阵 incidence matrix 又由于矩阵J T J displaystyle J operatorname T J nbsp 是半正定的 所以A displaystyle A nbsp 的任何特征值l displaystyle lambda nbsp 均满足l 2 0 displaystyle lambda 2 geq 0 nbsp 等价刻画 编辑 nbsp 九种排除在线图之外的导出子图Beineke给出了线图的一种等价刻画 H displaystyle H nbsp 是某图的线图当且仅当H displaystyle H nbsp 不包含九种类型的导出子图 见右图 2 如果H displaystyle H nbsp 的最小度至少为5 那么只有左边一列和右边一列是必要的 换言之 此时 H displaystyle H nbsp 是某图的线图当且仅当H displaystyle H nbsp 不包含六种类型的导出子图 见右图的左边一列和右边一列 参考文献 编辑 1 0 1 1 Whitney Hassler Congruent Graphs and the Connectivity of Graphs American Journal of Mathematics 1932 01 54 1 150 2020 10 23 doi 10 2307 2371086 原始内容存档于2020 10 26 Beineke Lowell W Characterizations of derived graphs Journal of Combinatorial Theory 1970 09 01 9 2 129 135 2020 10 23 ISSN 0021 9800 doi 10 1016 S0021 9800 70 80019 9 原始内容存档于2020 10 30 英语 取自 https zh wikipedia org w index php title 線圖 amp oldid 72654206, 维基百科,wiki,书籍,书籍,图书馆,