22问答网
所有问题
设G为无向连通图，有n个结点，那么G中至少有多少条边?为什么?若是有向图又如何?
如题所述
举报该问题
推荐答案 2023-04-19
【答案】：至少有n-1条边．因为G为无向连通图，设有n个结点v
1
，v
2
，…，v
n
由连通性知，G中每对结点问都有路，每个结点都有与其相邻的结点，因此，每个结点至少关联一条边．不妨以给定结点的顺序相邻(或重新按序编号)，则有v
2
与v
1
相邻有边e，v
3
与v
2
或v
1
相邻有边e
2
，…，v
n
必与v
1
，v
2
，…，v
n-1
中某结点相邻有边e
n-1
．故G中至少有n-1条边．
若G为有向图，将方向略去对相应的无向图讨论，结果相同(因为只是讨论有多少条边，并未要求边的方向)．
温馨提示：答案为网友推荐，仅供参考
当前网址：
http://22.wendadaohang.com/zd/CI26Ch0I20IfT2II6hh.html
相似回答
设
无向连通图G有n个
顶点,证明
G至少有
(n-1)
条边
。
答：
不妨设为A，由于去掉这条边AB后不影响其他点的连通性，
那么剩下的n个点之间有归纳假设至少有（n-1)条边，所以G至少有n条边
。任意一条边都代表u连v以及v连u。无向图是相对于有向图来说明的，就是说每条边都是双向边，而有向图每条边都是单向边，也就是说只能由一个点指向另一个点。
一般
n个
节点的
连通图,
最少有几
条边?
答：
n个节点的有向连通图,最少有n-1条边
。在数据结构中,n个顶点的连通图至少要有（n-1）条边（也就是树）才能保证图为连通图。一个无向图G=(V,E)是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。即连通图边数最少为E-1。连通图的含义 1、连通分量：无向图G...
大家正在搜
设一个连通图G中有n个顶点e条边
设e为无向连通图G中的一条边
任何连通无向图G至少有
设G是具有n个结点m条边k
设某无向图G中有n个顶点
设G是n个节点m条边k个面
设连通简单平面图G有6个顶点
设G是具有m条边的n阶简单图
设G是一个无向图