求下图G的色多项式P(G，k)
答：P(G，k)=k(k?1)(k?2)(k?3)(k?4)+3k(k?1)(k?2)(k?3)+k(k?1)(k?2)
=k5?7k4+18k3?20k2+8k
求下图G的色多项式P(G，k)
答：P(G，k)=k(k?1)(k?2)(k?3)(k?4)+3k(k?1)(k?2)(k?3)+2k(k?1)(k?2)
=k5?7k4+20k3?26k2+10k
求下图G的色多项式P(G，k)
答：P(G，k)=k(k?1)(k?2)(k?3)(k?4)+2k(k?1)(k?2)(k?3)+k(k?1)(k?2)
=k5?8k4+24k3?31k2+14k
求下图G的色多项式P(G，k)
答：P(G，k)=k(k?1)(k?2)(k?3)(k?4)+2k(k?1)(k?2)(k?3)
=k5?8k4+23k3?28k2+12k
K3,4的边色数为 。
Petersen图（单星妖怪）的边色数为 。
下图的点色数为_______；边色数为_______
有8个顶的轮，其顶色数是 。 有8个顶的轮，其顶色数是 。 顶大于2的树T的顶色数是 。
右图G的独立数??(G)＝ A．1 B．2 C．3 D．4
右图G的支配数??(G)＝ A．1 B．2 C．3 D．4
右图G的独立数??(G)＝ A．1 B．2 C．3 D．4
右图G的支配数???(G)＝ A．1 B．2 C．3 D．4
任意一个p阶图，总有K3子图或4个点的独立集，则p的最小值为 A．6 B．7 C．8 D．9
一群人中，总有3个人互相认识或者彼此不认识，则这群人的人数至少是 A．5 B．6 C．7 D．8
任意一个p阶图，总有K3子图或3个点的独立集，则p的最小值为( ) A．4 B．5 C．6 D．7
有8种化学品a，b，c，d，e，f，g，h要放进贮藏室保管。出于安全原因，下列各组药品不能贮在同一个室内：a-f，a-c，a-h，e-f，e-g，g-h，b-h，b-d，c-d，f-g，b-f，d-e，c-g，d-g，问贮藏这8种药品至少需要多少个房间？ 以8种药品作为顶点，若两种药品不能贮在同一个室内，则它们之间有一条边，这样得右图，转化为图的正常顶着色问题。
g（1）对各顶点按次数的递减顺序排列为gfdechab；
（2）对g及不与之相邻点a、b着1色；
e（3）对f及不与之相邻点d、h着2色； fch（4）对e和c着3色。 d故?(G)≤3；又因为e，f，g为K3子图，故着色数?(G)≥3，从而?(G)=3。
ba因此贮藏这8种药品至少需要3个房间。贮藏方式之一为gab，dfh，
ce。
以下说法错误的是
A．欧拉回路必经过图中所有的边 B. 欧拉回路必经过图中所有的顶点 C. 哈密顿回路必经过图中所有的边 D. 哈密顿回路必经过图中所有的顶点
无向图G存在欧拉行迹，当且仅当 A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点
C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点
以下必为欧拉图的是
A．顶点度数全为偶数的连通图 B．奇数顶点只有2个的图 C．存在欧拉迹的图 D．没有回路的连通图。
下图中是Euler图的是
A． B． C． D．
下列图中为欧拉图的是
A． B． C． D．
下图中既是欧拉图又是哈密顿图的是 A．K9 B．K10 C．K2,3 D．K3,3
设G为完全二部图K2,3，下面命题中为真的是 A．G为Euler图 B．G为Hamilton图 C．G为平面图 D．G为正则图
在Petersen图（单星妖怪）中至少添加 条边才能构成欧拉图。5
有4个顶的无向连通图G是欧拉图， A．1,2,3,4 B．2,4,6,8 C．1,2,4,6 D．5,2,3,4
设m≥1，n≥3，下面命题中，为真的是 A．完全图Kn都是Euler图 B．完全二分图Kn,m都是Euler图 C．完全图Kn都是Hamilton图 D．完全二分图Kn,m都是Hamilton图
构造Euler图，其顶点数p和边数q满足p，q的奇偶性相反。
有四个村庄的地下各有一个防空洞甲、乙、丙、丁，相邻两个防空洞之间有地道相通，且每个防空洞各有一条地道与地面相通，如下图所示（图中◎表示地道）。问能否从某一个防空洞开始，每个地道走一次且仅走一次后回到该防空洞。要求有一定的分析过程。 甲乙
丁丙
求下图的中国邮路问题，设vi为邮局。（1）写出“倍边”的过程；（2）列出最后所得的从v1出发的中国邮路。
v6v23 2412
v1v33v7 243 v5v47
（1）图中，奇次顶集为{v1,v2,v4,v3}。计算出每对顶的距离：
d(v1,v2)=4，d(v1,v3)=5，d(v1,v4)=7，d(v2,v3)=2，d(v2,v4)=5，d(v3,v4)=3， 求出{v1,v2,v4,v3}构成的完全加权图的最佳匹配M={v1v2,v3v4}，
P(v1,v2)=v1v7v2，P(v3,v4)=v3v4，在G中沿P(v1,v2)与P(v3,v4)变成同权“倍边”。 （2）v1v7v2v3v4v5v1v6v2v7v3v4v7v1。
一个连通的无向图G，如果它的所有顶点的度数都是偶数，那么它具有一条 A．Hamilton回路 B．Euler回路 C．Hamilton轨 D．含所有顶的圈
设完全图Kn有n个顶点(n≥2)，m条边，Kn中存在欧拉回路的条件是
A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数
K7中两两无公共边的Hamilton圈有 A．2 B．3 C．4 D．7
下面哪个图不是Hamilton图
A． B． C． D．
Petersen图（单星妖怪）是Hamilton图。
若G是一个Hamilton图，则G一定是( )． A．平面图 B．自对偶图 C．欧拉图 D．连通图
若G是一个Euler图，则G一定是( )． A．平面图 B．Hamilton图 C．连通图 D．自对偶图
Petersen图（单星妖怪）是 A．Hamilton图 B．Euler图 C．平面图 D．非平面图
K11中有 条边不重的Hamilton回路。5
若图G的任一对顶u，v皆有d(u)?d(v)≥V(G)，则G是Hamilton图。
若G是Hamilton图，则对于V(G)的任意子集S都有??(G?S)≤|S|。
在下列图中，既是Euler图又是Hamilton图的是
A． B． C． D．
设G是n(n≥3)阶单图，则其顶的最小次数?≥n/2是G为哈密尔顿图的 A．必要条件 B．充分条件 C．充分必要条件 D．既不充分也不必要条件
设G是有10个顶点的无向图，对于G中任意两个不邻接的顶点u和v，均有d(u)+d(v)≥9，则G是Hamilton图。
作一个图，使其是Euler图但非Hamilton图。
画出两个具有8条边、6个顶的无向简单图，并使其是Euler图。 画出两个具有7条边、6个顶的无向简单图，并使其是Euler图。
下列图中，v2可达v4的是 v1v1v4v4v1v4v4v1 v2v2v3v2v3v3v2v3A． B． C． D．
下列有向图中是强连通图的是
A． B． C． D．
对具有m条边的单图定向能得到______个不同的有向图。2m