设G 是具有n 个结点的无向简单图，若在G 中存在一条哈密顿通路，则 G 中每一对结点的度数之和与n-1 的关系为（）A．不确定B．大于等于C．小于等于D．大于

题目

设G 是具有n 个结点的无向简单图，若在G 中存在一条哈密顿通路，则 G 中每一对结点的度数之和与n-1 的关系为（）

A．不确定

B．大于等于

C．小于等于

D．大于

相似考题

1.设G=(n,m)且G中每个结点的度数不是k就是k＋1,则G中度数为k的结点的个数是()。A、n/2B、n(n+1)C、nkD、n(k+1)-2m

2.下面哪一种图不一定是树?()。A、无回路的连通图B、有n个结点n-1条边的连通图C、每对结点间都有通路的图D、连通但删去一条边则不连通的图

3.在n个结点的无向图中,若边数大于n-1,则该图必是连通图。()

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

参考答案和解析
n(n －1)/2
更多“设G 是具有n 个结点的无向简单图，若在G 中存在一条哈密顿通路，则 G 中每一对结点的度数之和与n-1 的关系为（）”相关问题

  • 第1题：

    如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路。()

    此题为判断题(对，错)。


    答案：错

  • 第2题：

    设无向图G中顶点数为n,图G最多( )有条边。

    A: n

    B: n-1

    C: n*(n-1)/2

    D: n*(n-1)


    正确答案: A

  • 第3题：

    设顺序表中结点个数为n，向第i个结点后面插入一个新结点，设向每个位置插入的概率相等，则在顺序表中插入一个新结点平均需要移动的结点个数为( )。

    A．(n-1)/2

    B．n/2

    C．n

    D．(n+1)/2


    正确答案：B
    解析：若顺序表中结点个数为n，且往每个位置插入的概率相等，则插入一个结点平均需要移动的结点个数为n/2。

  • 第4题：

    设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为()。

    A.e，n
    B.n.e
    C.2n，e
    D.n.2e

    答案：D
    解析：
    使用邻接表存储图，图有多少结点，邻接表就有多少个表头，无向图的表结点个数为2e。

  • 第5题：

    设E为程序图G中边的总数；N为程序图中结点的总数，则该程序图的环形复杂度为 （）。


    正确答案:E–N+2

  • 第6题：

    设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）

    • A、n，e
    • B、e，n
    • C、2n，e
    • D、n，2e

    正确答案:D

  • 第7题：

    设G为具有N个顶点的无向连通图，则G至少有（）条边。


    正确答案:N-1

  • 第8题：

    某完全有向图G含有n个结点，则它含有边的数目（）。

    • A、（n-1）n/2
    • B、n（n+1）
    • C、n/2
    • D、n（n－l）

    正确答案:D

  • 第9题：

    填空题
    在无向图G中，若对于任意一对顶点都存在路径，则称无向图G为（）

    正确答案： 连通图
    解析： 暂无解析

  • 第10题：

    单选题
    设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。
    A

    2n

    B

    n

    C

    n/2

    D

    n（n-1）


    正确答案： B
    解析： 暂无解析

  • 第11题：

    单选题
    设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）
    A

    n，e

    B

    e，n

    C

    2n，e

    D

    n，2e


    正确答案： D
    解析： 暂无解析

  • 第12题：

    多选题
    无向图G有n（n>=2）个顶点（假设为简单图），则G的边的数目可以是（）。
    A

    n-1

    B

    n-2

    C

    （n-1）n/2

    D

    （n+1）n/2


    正确答案： B,D
    解析： 暂无解析

  • 第13题：

    设图G是有5个结点的连通图,结点度数总和为10,则可从G中删去6条边后使之变成树。()

    此题为判断题(对，错)。


    答案：错

  • 第14题：

    设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和边表接点的个数分别为()。

    A.n,e

    B.e,n

    C.2n,e

    D.n,2e


    正确答案：A

  • 第15题：

    设,|V|=n(n>1),当且仅当(59),G=是强连通图。A.G中至少有一条路B.G中至少有一条回路C.G中有通

    设，|V|=n(n＞1)，当且仅当(59)，G=＜V，E＞是强连通图。

    A．G中至少有一条路

    B．G中至少有一条回路

    C．G中有通过每个结点至少一次的路

    D．G中有通过每个结点至少一次的回路


    正确答案：D
    解析：本题考查的是图论中的基本知识点。在简单有向图G中，任何一对结点问两者之间是相互可达的，则称这个图是强连通的。如图：A→B只有A到达B，有一次路，但是该图不是强连通的。所以，C错。

  • 第16题：

    设无向图G有n个顶点m条边，则其邻接表中表结点数是（）

    • A、n
    • B、2n
    • C、m
    • D、2m

    正确答案:D

  • 第17题：

    在无向图G中，若对于任意一对顶点都存在路径，则称无向图G为（）


    正确答案:连通图

  • 第18题：

    设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。

    • A、2n
    • B、n
    • C、n/2
    • D、n（n-1）

    正确答案:B

  • 第19题：

    无向图G有n（n>=2）个顶点（假设为简单图），则G的边的数目可以是（）。

    • A、n-1
    • B、n-2
    • C、（n-1）n/2
    • D、（n+1）n/2

    正确答案:A,B,C

  • 第20题：

    设一棵有2n+1个结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（）个叶结点。

    • A、n
    • B、n+1
    • C、n+2
    • D、n-1

    正确答案:B

  • 第21题：

    填空题
    设G为具有N个顶点的无向连通图，则G至少有（）条边。

    正确答案： N-1
    解析： 暂无解析

  • 第22题：

    单选题
    某完全有向图G含有n个结点，则它含有边的数目（）。
    A

    （n-1）n/2

    B

    n（n+1）

    C

    n/2

    D

    n（n－l）


    正确答案： D
    解析： 暂无解析

  • 第23题：

    填空题
    设E为程序图G中边的总数；N为程序图中结点的总数，则该程序图的环形复杂度为 （）。

    正确答案： E–N+2
    解析： 暂无解析

  • 第24题：

    单选题
    设无向图G有n个顶点m条边，则其邻接表中表结点数是（）
    A

    n

    B

    2n

    C

    m

    D

    2m


    正确答案： B
    解析： 暂无解析

相关内容