设G=<V,E:是 n个顶点的无向图(n>2),若对任意u,v V,有d(u) d(v) 山_则G是连通图
设G=
发布时间：2025-07-11 23:56:46
请在 下方输入 要搜索的题目：
推荐参考答案 (
由 快搜搜题库 官方老师解答 )
答案：证明:用反证法证明。若G不连通,则它可分成两个独立的子图 q和G2,其中 |V(G 1 )| |V(G 2 )|-2=n ,且G1中的任一个顶点至多只和 G1中的顶点邻接,而 G2中的任一顶点至多只和 G2中的顶点邻接。任取u V(G1),v V(G2 ),则 d(u) |V(G 1)|-1, d(v) |V(G 2 )|-1 。故 d(u) d(v) (|V(G 1 )|-1) (|V(G 2)|-1) |V(G 1)| |V(G 2 )|-2=n-2
相关试题
-
1.设G=
- 2.在有向图G中，若对于V(G)中任意两个不同顶点u和v，都存在 从u到v以及v到u的路径，则称G是 ______
- 3.在图G中，顶点u到v的距离d(u, v)不满足以下哪条性质？
- 4.设有图G=(V(G),E(G))和图H=(V(H),E(H)) ，若V(G)=V(H)，E(H)⊆E(G)，则称图H是图G的一个_________。
-
5.在一个有n个顶点的G=
中,u〃V。若存在一条从u到v的条通路,则必有一条从u到v的长度不超过n-1的通路。 -
6.【单选题】设G=
- 7.已知文法G[V]: V->N|N[E] E->V|V+E N->i则follow(V)=( )
- 8.Nguyễn Văn Hùng thích uống gì?
- 9.给定图G=(V,E), |V|=n, |E|=m, 遍历其邻接表的时间复杂度为θ( )
- 10.已知有向图 G=(V,E)其中 G 的拓扑序列是（）。
