习题十二1．一个简单图G有多少不同的定向图？分析：由于简单图的每条边有两种不同的方向可供选择，因此具有q条边的无向简单图G共有2q个不同的定向图。解.设),(qpG是简单图，则G共有2q个不同的定向图。2．简单有向图的基础图一定是简单图吗？分析：有向图的基础图是将有向边变成无向边所得到的无向图，由于在有向图中（u,v）和(v,u)是两条不同的边，而在无向图中却属于同一条边，这样无重边的有向图变成无向图以后就有可能含有重边，从而不是简单图。解：不一定，如右图。3．设),(qpD是简单有向图，证明：（1）若D是强连通图，则)1(ppqp（2）若D是弱连通图，则)1(1ppqp分析：强连通图D是指D中任意两个顶点间存在双向的通路，因此D的基础图G必含H回路，一条H回路的边数至少有p条边，因此pq；另一方面，由于完全强连通图的边数等于)1(pp，因此简单有向图D的边数)1(ppq。弱连通图D是指D的基础图是连通图的有向图，根据习题5第16题（1）有具有q个顶点的连通图的边至少有p-1条，因此qp1。证明（1）因D是强连通图，故D中任意两个顶点vu,之间既存在),(vu通路，又存在有向),(uv一通路，于是，D的基础图G必含H回路.故pq，又因D是简单有向图.故D中任何两个顶点之间最多有二条弧，从而)1(ppq，故)1(ppqp.（２）因D是弱连通图，故D的基础图G是连通的，若G无回路，则1pq，因此，)1(1ppqp4．设),(qpD是有向图，证明：pipiiDiDudqud11)()(分析：)(vdD是指有向图D中顶点v的出度，即以顶点v为尾的弧的条数；由于D中的任一弧恰有一个头和一个尾，因此，每增加一条弧，对D的所有顶点来说，肯定会增加一个出度，同时也会增加一个入度。证明：因为有向图中的每条弧对应一个顶点（尾）的出度和另一个顶点（头）的入度计数.故pipiiDiDqudud11)()(5．基础图是完全图的有向图),(qpD满足pipiiDiDudud1122))(())((分析：显然基础图是完全图的有向图),(qpD中每个顶点满足：1)()(pududii又根据第4题对D中每个顶点ui来说满足pipiiDiDudppqud11)(2)1()(，因此有2)1()()(11ppududpipiiDiD证明.由D的假设知，对任何)(DVui有1)()(pududii（1）于是，222)1())()()(2))(pududududiiii（2）又由（1）有)()1()(iiudpud，代入（2）有222)1())(()()]()1[(2))((pudududpudiiii整理得222)1())(()()1(2))((pududpudiii（3）由题4知piippqud1)1(21)(（完全有向图）整理得pipiDiDudud11212))(()((6．设D是单连通图.试证明：若对任意)(DVu，均有)()(udud，则D有一条有向回路。分析：单连通图D，是任意两个顶点)(,DVvu，存在一条单向通路，考虑D中的极长通路P的始点u，由)()(udud即能得到D中的一条有向回路。证明：因为D是单连通图，所以D中至少存在一条通路。假设P（uv0v1„vn）(vn=v)是D的一条极长通路，因为)()(udud，所以0)(ud，因此在D中存在以u为头的弧e，由P是极长通路，所以e的尾必在P中，不妨假设e的尾是vi，于是viuv0v1„vi构成了D的一条有向回路。7．设D是一个简单有向图，求证（1）D中包含长度至少为},max{的有向通路（2）若0},max{k，则D中包含长度至少为1k的有向回路.其中)}({min)},({maxvdvdvDvVDv分析：（1）由对称性，不妨假设},max{=，考虑D中极长有向通路P（uv0v1„vn）(vn=v)，假设P的长度小于，由的定义，知)(vd，因此以v为尾的弧的条数应不小于，因此至少有一条弧的头不在P上，与P是极长通路矛盾。本小题使用反证法。（2）同样考虑P上的顶点v，由以v为尾的弧的条数应不小于，且这些弧的头都在P上，可构造一条长度不小于k+1的有向回路。证明（1）不妨假设},max{（否则考虑其反向图）设P（uv1v2„vn）(vn=v)是D中极长的有向),(vu通路.若||P，则由于G是简单有向图，必有尾为v而头不在P上的弧，因此P可以延长，此与P...
