题目内容
(请给出正确答案)
[单选题]
设G为连通的无向简单图,若G恰有2个奇度结点,则G一定具有()。
A.欧拉回路
B.欧拉通路
C.哈密尔顿回路
D.哈密尔顿通路
答案
查看答案
A.欧拉回路
B.欧拉通路
C.哈密尔顿回路
D.哈密尔顿通路
第1题
设G是恰合2k(k2≥1)个奇度顶点的无向连通图,证明G中存在k条边不重的简单通路使得
第2题
在简单无向图中,如果每个顶点的度数都为是,则称此图为k—正则图。现设图G是有向图,其n个顶点分别为v1,v2,…,vn,如果图G的底图是3—正则图,且图G是强连通图。证明图G中各顶点出度的立方之和等于各顶点入度的立方之和。
第3题
设图G是n阶无向简单图,其中n是偶数,若图G中有k个奇数度点,问:在其补图中有多少个奇数度点?
第6题
A.G'为G的子图
B.G'为G的连通分量
C.G'为G的极小连通子图且V'=V
D.G'是G的无环子图
第8题
设有无向图G=(v,E)和G’=(V’,E’),如果G’是G的生成树,则下列不正确的是()。 I,G’为G的连通分量 II,G’为G的无环子图 III,G’为G的极小连通子图且V’=V
A.I、II
B.只有III
C.II、III
D.只有I
第11题
若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。
(1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上,则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥,将把图分割成两个连通分量。
(2)编写一个时间复杂度为O(n+e)的使用邻接表表示的算法,判断连通图G中是否有桥,若有。输出这样的桥。