一道图论问题的证明

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

<<数学之美>> part5
小学课本的“七桥问题”
《数学之美》笔记图论与网络爬虫
算法概论笔记 - 图
张胜贵
Dynamic Graph，一道图论题
算法与数据结构（十）总结
欧拉七桥问题
图论的图与普通的图有什么关系？
网状结构（图）的基本知识

命题

若图 $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，所以操作的步数必定有限步完成。$

证毕

<<数学之美>> part5
摘要: [图论] [网络爬虫] [图的遍历] 图论说到图论,必须要提的就是KonigsBerg七桥问题,简单说就...
小学课本的“七桥问题”
柯尼斯堡七桥问题（Seven Bridges of Konigsberg）是图论中的著名问题,也是世界上第一个图论...
《数学之美》笔记图论与网络爬虫
离散数学包括数理逻辑，集合论，图论，近世代数。图论哥尼斯堡七桥问题（图论的起源）：只有每个点的度都是偶数的情况...
算法概论笔记 - 图
现实生活中有很大一类问题可以用简洁明了的图论语言来描述，可以转化为图论问题。相关定义图可以表示为G=(V, E...
张胜贵
图论发展的第一阶段葛底斯堡七桥问题图论发展的第二阶段哈密顿问题同时也出现了用图解决其他领域中一些问题的成果...
Dynamic Graph，一道图论题
题目链接：https://icpc-camp-cdn.b0.upaiyun.com/permanent/probl...
算法与数据结构（十）总结
课程总结过程：线性问题：树形问题：图论问题：更多算法问题算法设计相关：贪心：从最小到最大，或从最大到...
欧拉七桥问题
什么是“欧拉七桥问题”？柯尼斯堡七桥问题（Seven Bridges of Königsberg）是图论中的著名...
图论的图与普通的图有什么关系？
知乎问答图论的图与普通的图有什么关系？问题描述: 就是说一张这样的，图论里面讨论的由点和边组成的图，和我们平时...
网状结构（图）的基本知识
如果说树型结构是种层次结构的话，图则是网状结构。可以说，树是图的一种特例。学习图论后，树的很多问题可以通过图论算法...