西交《离散数学》faq（八）

作业辅导

西交《离散数学》FAQ（八）
第六章 图论一、有四个城市v1，v2，v3，v4，其中v1与v2间有公路e1相连，v1与v4间有公路e2相连，v2与v3间有公路e3相连。
答：上述事实可用图G=（V，E）表示。图G中结点集V=
，图G中边集
E=
，它的图示如图1所示。

二、  有四个程序，它们之间存在如下的调用关系：P1能调用P2，P2能调用P3，P2能调用P4。
答：上述事实也可用一图G=（V，E）来表示。图中结点V=
，图中边集E=
，它的图示如图2所示。

三、七桥图（见图3），按定义3，可用一图G=（V，Σ，E）来表示。
图中结点集V=
，图中标号集
，图中边集E=



答：它的的图示如图3所示。
四、七桥图（见图10），按定义4，可用一图G（V，E，γ）来表示。图中结点集V=
，图中边集答：E=
，图中关联函数γ：E→
使



五、图G及其子图、生成子图、真子图、平凡子图分别如下图11所示：


六、在下面的无向图在，其中：
答：deg（v1）=5，deg（v2）=3，deg（v3）=3，
deg（v4）=2，deg（v5）=0，deg（v6）=1；
奇结点：v1，v2，v3，v6；
偶结点：v4，v5；
悬挂点：v6；
悬挂边：（v2，v6）。


并且有如下结论：
（1）所有结点的度数之和等于边数的二倍；
5+3+3+2+0+1=2×7
（2）所有奇结点的度数之和是偶数；
5+3+3+1=12。
本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986