一道图论问题的证明

2023-02-10 本文已影响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，所以操作的步数必定有限步完成。$

证毕

一道图论问题的证明

证明

猜你喜欢

热点阅读