线图

✍ dations ◷ 2025-02-24 14:11:39 #线图

在图论中,图 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} 的结构。以该定理为中介,可以证明线图的许多其它性质。线图总是无爪图,即线图的所有导出子图均不是 K 1 , 3 {displaystyle K_{1,3}}

G {displaystyle G} 的线图 L ( G ) {displaystyle L(G)} 定义如下:

该定义也可以用图论的语言表述如下:设 G = ( V , E ) {displaystyle G=(V,E)} ,那么 L ( G ) = ( E , E ~ ) {displaystyle L(G)=(E,{tilde {E}})} ,且 ( 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 }

下面的例子演示了由原图生成线图的流程。

原图

制作线图的过程

结果

根据线图的定义,若性质/概念P仅取决于原图 G {displaystyle G} 中边的邻接性,那么P便可以转移(或者说对偶)到线图 L ( G ) {displaystyle L(G)} 上去变成性质/概念P',刻画线图顶点的邻接属性。例如,图 G {displaystyle G} 中的一个匹配指的是图中一组不相交的边,把这一概念平移到线图上去,就等价于线图的一组不相邻的顶点——用术语来说即线图上的一个独立集。

下面就列举了原图和线图之间的若干联系:

惠特尼同构定理阐述了以下事实:设有连通图 G 1 {displaystyle G_{1}} G 2 {displaystyle G_{2}} 且它们均不是三角形 K 3 {displaystyle K_{3}} 或爪形 K 1 , 3 {displaystyle K_{1,3}} 。如果 L ( G 1 ) L ( G 2 ) {displaystyle L(G_{1})cong L(G_{2})} ,那么 G 1 G 2 {displaystyle G_{1}cong G_{2}} 。也就是说,除了极特殊的情形,图 G {displaystyle G} 的结构可以由线图 L ( G ) {displaystyle L(G)} 的结构中唯一地恢复出来。

任何的线图都是无爪的,亦即不包含 K 1 , 3 {displaystyle K_{1,3}} 作为导出子图。因此,任意含有偶数个顶点的连通线图都存在完美匹配。

线图 L ( G ) {displaystyle L(G)} 的邻接矩阵 A m × m {displaystyle A_{mtimes m}} 的全部特征值都不小于-2。这是因为 A = J T J 2 I {displaystyle A=J^{operatorname {T} }J-2I} ,其中 J n × m {displaystyle J_{ntimes m}} 是原图 G {displaystyle G} 的关联矩阵(incidence matrix)。又由于矩阵 J T J {displaystyle J^{operatorname {T} }J} 是半正定的,所以 A {displaystyle A} 的任何特征值 λ {displaystyle lambda } 均满足 λ + 2 0 {displaystyle lambda +2geq 0}

Beineke给出了线图的一种等价刻画: H {displaystyle H} 是某图的线图当且仅当 H {displaystyle H} 不包含九种类型的导出子图(见右图)。

如果 H {displaystyle H} 的最小度至少为5,那么只有左边一列和右边一列是必要的。换言之,此时, H {displaystyle H} 是某图的线图当且仅当 H {displaystyle H} 不包含六种类型的导出子图(见右图的左边一列和右边一列)。

相关

  • 模型论模型论(英语:Model theory)一般是指数学中集合论的论述角度对数学概念表现(representation)的研究,或者说是对于作为数学系统基础的“模型”的研究。粗略地说,该学科假定有一些既
  • 外子丈夫,是男女婚姻中对男性的称谓,与妻子相对应。古代妻子对自己配偶又称夫婿、夫君、相公、官人,闽南语则称翁婿(闽南语读“ㄤ”(ang /ɑŋ/),字用“翁”)、头家、夫婿。外子则是妻
  • 在宅医疗在宅医疗(英语:Home healthcare)源自日本,是为了配合高龄化社会 的长期照顾需要,发展出结合医疗与健康照护的全天候到宅医疗照顾服务,在日本已行之多年,成为日本政府制定的社区整体
  • 普莱恩菲尔德 (加利福尼亚州)普莱恩菲尔德(英语:Plainfield)是位于美国加利福尼亚州优洛县的一个非建制地区。该地的面积和人口皆未知。普莱恩菲尔德的座标为38°35′27″N 121°47′49″W / 38.59083°N 1
  • 蜂窝大厦蜂窝大厦(Beehive)是新西兰国会园区内的一座建筑。现在蜂窝大厦被列入新西兰的一级保护建筑。蜂窝大厦的设计者是苏格兰人建筑师Basil Spence,修建于1969年至1979年之间。现在
  • 藤田麻衣子藤田麻衣子(1984年1月16日-)为日本爱知县名古屋市绿区出身的创作歌手。经纪公司为GOOD-DAY。2006年9月以单曲“恋に落ちて”出道,现在共发行了10张单曲及5张专辑。所有的歌曲均
  • 保加利亚奥林匹克委员会保加利亚奥林匹克委员会(Bulgarian Olympic Committee)是保加利亚的国家奥林匹克委员会。该组织成立于1923年,是国际奥林匹克委员会和欧洲奥林匹克委员会的成员。1896年,他们参
  • 帕斯卡微架构2016年4月,NVIDIA公司联合创始人兼CEO黄仁勋发布了首个采用“帕斯卡”(Pascal)架构的新一代计算显卡Tesla P100。帕斯卡微架构主要用于NVIDIA GeForce 10系列GPU。工艺:TSMC 16n
  • 蔺新江蔺新江(1946年8月28日-),出生在山东省。已退役足球运动员,前中国国家足球队球员,著名教练。15岁时入选河北青年队,之后随球队在全国足球甲级联赛中不断征战并获得过较好的成绩。1970年入选国家队,在此期间多次随队参加国际比赛。1971年访非洲,1972年迎战来华访问的智利国家队。1974年参加第7届亚运会和第6届亚洲杯预赛,并取得决赛权。1976年退役并开始从事教练工作,曾执教过北京部队,天津泰达队、厦门厦新队以及中国女子足球国家队。
  • 威廉·P·费森登威廉·皮特·费森登(英语:William Pitt Fessenden,1806年10月16日-1869年9月8日),美国政治家,曾任美国众议院议员(1841年-1843年)、美国参议院议员(1854年-1864年)和美国财政部长(1864年-1865年)。