设G是n个顶点的无向简单图,则下列说法不正确的是()A、若G是树，则其边数等于n-1B、若G是欧拉图，则G中必有割边C、若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点D、若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路

题目
设G是n个顶点的无向简单图,则下列说法不正确的是()

A、若G是树，则其边数等于n-1

B、若G是欧拉图，则G中必有割边

C、若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点

D、若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路

相似考题

1.2、设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。A．nB．n-1C．2nD．2n-1

2.一个n阶无向简单图，n大于1且为奇数。如果G中有r个奇度数顶点，则G的补图中有多少个偶度数顶点A．不确定B．rC．2rD．n-r

3.设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。A．2nB．nC．n/2D．n(n-1)

4.设G是一个n阶无向简单图，n是大于等于2的奇数．图G与它的补图中的奇数度顶点个数相等．

更多“设G是n个顶点的无向简单图,则下列说法不正确的是() ”相关问题

  • 第1题：

    下列说法正确的是？

    A．若图G是具有n个顶点的简单图，如果G中的每一对顶点的度数之和大于或等于n-1，则在G中存在一个哈密顿路。

    B．若G是简单无向图，G是哈密顿图，当且仅当它的闭包是哈密顿图。

    C．无向图G若是二分图当且仅当G中所有回路的长度均为偶数。

    D．一个连通无向图至少有一个生成树。


    ABC

  • 第2题：

    下列说法正确的是？

    A．有向图G是强连通的当且仅当G中有一回路，它至少通过每个顶点一次。

    B．一个有向图是单向连通图当且仅当它有一条经过所有结点的路。

    C．设简单平面图G中顶点数n=7，边数m=10，则G是连通的。

    D．在一个有n个顶点的G=＜V,E＞中，若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的通路。


    强连通分量

  • 第3题：

    5、5.设无向图G中顶点数为n，则图G至少有（）条边。


    0n(n-1)/2

  • 第4题：

    若n个顶点的简单无向图G的边数e=n−1，则G一定是树.


    [证明]用反证法，设图G不是连通图，不妨设图G有两个连通分支G 1 和G 2 构成，其中G 1 含有k个顶点(1≤k＜n)，G 2 含有2n-k个顶点。在连通分支G 1 中任取一点v 1 ，在连通分支G 2 中任取一点v 2 。由于图G是简单图，所以G 1 和G 2 也是简单图，于是有 deg(v 1 )≤k-1 deg(v 2 )≤2n-k-1由此可得 deg(v 1 )+deg(v 2 )≤k-1+2n-k-1=2n-2 但假设图G中每个顶点的度数至少为n，因此 deg(v 1 )+deg(v 2 )≥2n由此引出矛盾，本题得证。

  • 第5题：

    设G是具有n个顶点的无向图，下列说法错误的是

    A．若G中恰好有n-1条边，则G一定是树。

    B．若G中的每对顶点间都是连通的，则G一定是树。

    C．若G中每条边都是割边，则G一定是树。

    D．若G连通但是去掉任意一条边都不连通，则G一定是树。


    N-1

相关内容