1650: 算法基础（图论2）

1、【NOIP2001提高组】无向图G=(V，E)，其中V={abcdef} E={(ab)(ae)(ac)(be)，(cf)(fd)(ed)}，对该图进行深度优先遍历得到的顶点序列正确的是（     ）。

   A．abecdf   B．acfebd   C．aebcfd   D．abedfc

2、【NOIP2002提高组】在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（     ）倍。

    A．1/2          B．1            C．2            D．4

3、假设我们用d=(a1a2...a5)表示无向图G的5个顶点的度数，下面给出的哪个组d 值合理（     ）。

   A．{5，4，4，3，1}         B．{4，2，2，1，1}         C．{3，3，3，2，2}        D．{5，4，3，2，1}    

4.【NOIP2007提高组】欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中 不一定是欧拉图的是（     ）。

   A. 图G中没有度为奇数的顶点

   B. 包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径)

   C. 包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径)

   D. 存在一条回路 通过每个顶点恰好一次

   E. 本身为闭迹的图

5.【NOIP2004普及组】某大学计算机专业的必修课及其先修课程如下表所示：

请你判断下列课程安排方案哪个是不合理的（  ）。

A. C0 C6 C7 C1 C2 C3 C4 C5    B. C0 C1 C2 C3 C4 C6 C7 C5

C. C0 C1 C6 C7 C2 C3 C4 C5    D. C0 C1 C6 C7 C5 C2 C3 C4

E. C0 C1 C2 C3 C6 C7 C5 C4

6. 【NOIP2011普及组】对一个有向图而言，如果每个结点都存在到达其他任何结点的路径，那么就称它是强连通的。例如，右下图就是一个强连通图。事实上，在删掉边(    )后，它依然是强连通的。

     A.  a      B. b      C. c      D. d