一道图论问题的证明

一道图论问题的证明

作者: 花雪白芷 | 来源:发表于2023-02-10 20:00 被阅读0次

命题

若图 $G=(V,E)$ ,其中 $V为点集，\vert V \vert为点集的数目；E为边集，\vert E \vert为边集的数目。$

$若\vert E \vert>\frac{1}{2}(\vert V\vert -1)(\vert V\vert -2) ,则图 G是连通的。$

证明

$考虑以V为点集的完全图\hat{G} =(V,\hat{E} )，其中\hat{E}为\hat{G} 的边集。$

$记F=\hat{E} -E，不难看出，图G可以通过图\hat{G}删除边集F中的边得到，下面我们进行逐步删除操作。$

$第一步，找出V中与F中边关联最多的点，记作v_{1}，并记F_{1}=\{e|e\in F且e \sim v \}。$

$由题意得，\vert F_{1} \vert \leq \vert F\vert<\frac{1}{2}(\vert V\vert -1)(\vert V\vert )-\frac{1}{2}(\vert V\vert -1)(\vert V\vert -2)=\vert V \vert-1 。$

$由于\hat{G} 为完全图，那么点v_{1}的度数为d(v_{1})=|V|-1，也就是说即使v_{1}删除边集F_{1}中所有的边，$

$它仍然至少有一条边与由V_{1}=V-\{v_{1}\}生成的完全图记作G_{1}=(V_{1},E_{1})的某个顶点相连，$

$从而整个图\hat{G}删除边集F_{1}是连通的。$

$第二步，找出V_{1}中与F中边关联最多的点v_{2}，记F_{2}=\{e|e\in F且e \sim v_{2}\}。$

由第一步可以知道， $\vert F_{2} \vert < \vert V\vert-1-|F_{1}|\leq|V|-2=|V_{1}|-1$ 。

$由于G_{1} 为完全图，那么点v_{2}的度数为d(v_{2})=|V_{1}|-1，也就是说即使v_{2}删除边集F_{2}中所有的边，$

$它仍然至少有一条边与由V_{2}=V_{1}-\{v_{2}\}生成的完全图G_{2}=(V_{2},E_{2})的某个顶点相连，$

$那么删除边集F_{2}\subset E_{1}的图G_{1}是联通的。。$

$由于E_{1}\cap F_{1}=\emptyset，则F_{2}\cap F_{1}=\emptyset$ 。 $那么点v_{1}与G_{1}仍然相连。则整个图G连通。$

依次如此进行下去， $由于|F|<|V|-1，所以操作的步数必定有限步完成。$

证毕

相关文章

网友评论

本文标题：一道图论问题的证明

本文链接：https://www.haomeiwen.com/subject/yywkkdtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

代数图论

简友广场

散文

想法

关于我们|服务条款|联系我们|一道图论问题的证明|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！