第七章节图论课件(1844KB).pptVIP

练习7-9 1．计算非同构的有向树的个数。 （1）2个结点非同构的有向树的个数是 。 （2）3个结点非同构的有向树的个数是 。 （3）4个结点非同构的有向树的个数是 。 1 4 2 2． 对上图给出的二元树进行三种方式的周游。 （1）先根周游结果为_________________。 （2）中根周游结果为_________________。 （1）后根周游结果为_________________。 abcdefgih dcebfagih decfbaghi 习 题 1．下面各图有几个结点？ （1）16条边，每个结点度均为2。 （2）21条边，3个度为4的结点，其余都是度为3的结点。 解 根据握手定理 计算 （1）2m=32，所以 ，因此结点数n=16 因此结点数n=10+3=13。 （2）设度为3的结点x个，2m=42， 所以3?4+3x=42，解得x=10 2．设图G的每一结点的度均为2，试证明G的每一 分图均将包含一个环。 证明 设G?是G的任一分图，包含n个结点v1，v2，…，vn和m条边。 因为G?中每一结点的度为2，所以 ，于是m = n， 若G?不包含环，则G?是一棵树，有m = n–1, 但这与m = n相矛盾，因此G?必包含有环。 3． 一棵树T有5个度为2的结点，3个度为3的结点，4个度为4的结点，2个度为5的结点，其余均是度为1的结点，问T有几个度为1的结点？ 解 设T有x个度为1的结点，则有 5?2+3?3+4?4+2?5+x = 2m m = n–1 5+3+4+2+x = n 解以上三个方程得 x = 19 4．某次会议有12人参加，其中每人都至少有6个朋友， 这12个人围成一圆桌入席，要想使每人相邻的两位 都是朋友是否可能？说明理由。 解 题目的要求可以办到，其理由如下： 在平面上用12个结点分别表示12个人，若 两人是朋友，则在相应的两结点间连一条边， 设得到的图为G，则G中每一结点的度≥6，因此 G中每一对结点度之和≥12 。 根据定理 G是哈密尔顿图，即G中存在哈密尔顿环，故12人 围成一桌时，可以使每人与相邻两人是朋友。 二、树的性质 定理7.7.1 设T是一棵树，vi和vj是T中任意两个不同的结点，则vi和vj由唯一条真路相连接。若vi和vj不相邻接，那么当给T添加一条边{ vI，vj }后形成的图恰有一个环。 定理7.7.2 若T是一（n，m）树，则m=n–1。 证明 （对结点数n进行归纳） 当n=1和n=2时，定理成立。 设对结点数少于n的所有树定理成立。T是一具有n个结点的树， 由于T不包含环，因此从T中去掉任何一条边都将使T变成两个分图，且这两个分图也是树， 设它们分别是（n1，m1）树和（n2，m2）树， 由归纳假设m1=n1–1，m2=n2–1。 又因为n=n1+n2，m=m1+m2+1，所以， 有m=（n1–1）+（n2–1）+1=n–1。定理结论成立。 定理7.7.3 具有两个或更多结点的树至少有两片树叶。 证明 设T是一棵（n，m）树，n≥2，显然T中所有结点的度之和S=2m，由定理7.7.2，S=2n–2。 若T中无树叶结点，则由T连通，每一结点的度≥2，因此S≥2n，这与S=2n–2矛盾。 若T中只有一个树叶结点，则S≥2（n–1）+1，即S2n–2，也与S=2n–2矛盾。 由上可知，T中至少有两片树叶。 树的有些性质可用来作为树的定义: （1）任何两个结点间存在唯一一条路径的图是树； （2）m=n–1的连通图是树； (3）m=n–1且无环的图是树。 (4)任一边都是桥的图是桥 三、生成树与最小生成树 1．生成树 定义7.7.2 若连通图G的生成子图T是一棵树，则称T为G的生成树。 例4 下图中（b）和（c）都是（a）的生成树。