惠特尼定理

✍ dations ◷ 2025-08-03 20:11:03 #惠特尼定理

图论中,惠特尼定理(英语:Whitney's theorem),又称为惠特尼连通性定理(Whitney's theorem on connectivity),是美国数学家哈斯勒·惠特尼于1932年提出的关于2连通图等价性质的定理,该定理提供了关于2连通图的不同点对之间的连通性质刻画,描述了2连通图的特殊性质。

对一个图 G {displaystyle G} ,若 G {displaystyle G} 至少存在3个点,则 G {displaystyle G} 是2连通的当且仅当对 G {displaystyle G} 中任意两个点 u , v {displaystyle u,v} G {displaystyle G} 中至少存在连接 u , v {displaystyle u,v} 的2条内部不相交路径,即除首尾相同(皆为 u , v {displaystyle u,v} )外,没有其他公共顶点的路径。

因为任意两点之间均存在路径,于是 G {displaystyle G} 是连通的。

进一步,对于任意两点之间有至少存在两条内部不相交路径,所以考虑删除 G {displaystyle G} 中任意一点,其均不会造成 G {displaystyle G} 不连通。于是 G {displaystyle G} 是2连通的。

G {displaystyle G} 是2连通的,希望证明对于任意两点 u , v V ( G ) {displaystyle u,vin V(G)} ,能找到至少两条连接 u , v {displaystyle u,v} 的内部不相交路径。

下面通过对 u , v {displaystyle u,v} 之间的距离 d ( u , v ) {displaystyle d(u,v)} 进行归纳来由数学归纳法证明:

于是根据数学归纳法,当 G {displaystyle G} 是2连通图时,对于任意两点 u , v V ( G ) {displaystyle u,vin V(G)} ,能找到至少两条连接 u , v {displaystyle u,v} 的内部不相交路径。

根据惠特尼定理的结论,可以得到关于2连通图的等价描述的推论:

G = G { w , z } { u w , v w , x z , y z } {displaystyle G'=Gcup {w,z}cup {uw,vw,xz,yz}} 。首先 G {displaystyle G'} 仍然是2连通的,这是因为, G {displaystyle G'} 的构造过程是加入两个点且两个点均与原图 G {displaystyle G} 中两个点相连,则考虑 G {displaystyle G'} 中的割集 S {displaystyle S} 。若割集中含有新加入的点 { w , z } {displaystyle {w,z}} ,则除去新加入的点, S { w , z } {displaystyle S-{w,z}} 是原图 G {displaystyle G} 的割集,而根据描述1, G {displaystyle G} 本是2连通的,则 | S | 2 + 1 = 3 {displaystyle |S|geq 2+1=3} | S | 2 + 2 = 4 {displaystyle |S|geq 2+2=4} ;若割集中不含有新加入的点,如果割集取自 { u , v , x , y } {displaystyle {u,v,x,y}} ,则 | S | 2 {displaystyle |S|geq 2} ,否则 S {displaystyle S} 实际上是原图 G {displaystyle G} 的割集,所以同样, | S | 2 {displaystyle |S|geq 2} 。所以无论如何,对于 G {displaystyle G'} 的任意割集,其大小至少为2,故 G {displaystyle G'} 仍然是2连通的。实际上,关于向 k {displaystyle k} -连通图加入辅助点的更一般的结论称为“扩展引理”(expansion lemma),它也在证明门格尔定理中发挥了作用。

那么根据描述3,对于 G {displaystyle G'} ,一定存在环 C {displaystyle C} w , z {displaystyle w,z} 均位于 C {displaystyle C} 上。而 w , z {displaystyle w,z} 的度均为2,所以 u w , v w , x z , y z {displaystyle uw,vw,xz,yz} 也位于 C {displaystyle C} 上,且 C {displaystyle C} 的其他边均来自原图 G {displaystyle G} 。于是可以将 u w v {displaystyle uwv} 替换成 u v {displaystyle uv} x z y {displaystyle xzy} 替换成 x y {displaystyle xy} ,从而 u v , x y {displaystyle uv,xy} 均位于原图中的一个环上。

惠特尼定理提供了对于2连通性的更具体的性质刻画,从而提供了另一种对于2连通性的具体证明方向。

相关

  • b梁/b font style=color:#888small502–557/small梁(502年-557年),又称南梁,是中国历史上南北朝时期南朝的第三个朝代,由南齐宗室萧衍称帝,改国号为梁,都建康(今江苏南京)。以萧衍封地在古梁郡,故国号为梁。因为皇帝姓萧,又称萧梁。南齐
  • 始祖鸟科始祖鸟科(学名:Archaeopterygidae)是生活于侏罗纪的一科非鸟恐龙。其下包含了最为知名的始祖鸟。始祖鸟科与早期鸟类不同的是其长及骨质的尾巴,一些物种甚至有较长的第二趾。始
  • 维克斯-阿姆斯特朗公司维克斯-阿姆斯特朗有限公司(Vickers-Armstrongs Limited)是英国的一家造船公司,由维克斯有限公司及阿姆斯特朗-惠特沃斯于1927年合并而成。公司大部分股份在1960-70年代间国有
  • 捷克哈比屯捷克哈比屯(捷克语:Český Hobitín)是捷克赫拉德茨-克拉洛韦州科内日诺河畔里赫诺夫Dobré的旅游景点,位在鹰山,仿制自J·R·R·托尔金所著小说《魔戒》及彼得·杰克逊导演电影
  • 尼克·贝尔格尼古拉斯·伊万·“尼克”·贝尔格(英语:Nicholas Evan "Nick" Berg,1978年4月2日-2004年5月8日),是一位美国宾夕法尼亚州费城市郊的美国商人。他在2004年3月前往伊拉克寻找通讯生
  • 中国文化大学出版部中国文化大学出版部,简称华冈出版部,是中国文化大学附设的大学出版社,1962年中国文化大学建校同时成立,出版方向为辞典、大学专业丛书、文艺丛书、地图集、外文书籍与期刊等。荣
  • 何景寮何景寮(1903年1月5日-1978年3月28日),字克良,台湾高雄县人,台中一中毕业后,内渡中国大陆,就读厦门大学预科、上海大厦大学文科,其间加入中国国民党。1927年毕业后返回台湾,参与台湾文
  • 乔恩·特里克特乔恩·特里克特(Jon Trickett,1950年7月2日-)是一位英格兰政治人物,他的党籍是工党。自1996年开始,他担任赫姆斯沃思选区选出的英国下议院议员。他是36位投票支持杰里米·科尔宾当
  • 恰拉尔·瑟云聚恰拉尔·瑟云聚(Çağlar Söyüncü,1996年5月23日-),是一名土耳其足球运动员,现时效力英超俱乐部莱斯特城和土耳其国家足球队。司职中后卫。瑟云聚于2016年夏季转会窗由阿特诺度(Altınordu S.K.)转投德国足球甲级联赛俱乐部弗赖堡,成为首位直接由土耳其足球甲级联赛转会至德甲的球员。2016年,瑟云聚首次代表土耳其国家足球队上场,成为自1938年的萨伊德·阿特诺度(英语:Said Altınordu)后,首位效力Altınordu S.K.期间获得土耳其国家队上场机会的球员。于20
  • 山胁正隆山胁正隆(日语:山脇正隆,やまわき まさたか;1886年3月2日-1974年4月21日),日本陆军大将。官位从三位勋一等功三级。山胁正隆1886年3月2日出生于高知县甲原村(现土佐市)的一个世代为土佐山内氏(日语:土佐山内氏)服务的土器师士族家庭。山胁正隆1900年毕业于广岛陆军地方幼年学校(日语:広島陸軍地方幼年学校),1905年毕业于陆军士官学校第18期,1914年毕业于陆军大学校第26期,排名第一,大正天皇恩赐军刀。1927年任参谋本部编成班长。1929年任参谋本部编成动员科科长。1931年任第22