e≥30，这和已知边数小于30相矛盾。 所以结论成立。
2、证明：每个面至少有4条边任何连通简单平面图中， m≤2n-4,其中n为结点数，m为边数。
证明：设这个图的面数为r，由欧拉公式n－m+r=2得r=m-n+2
因为deg(R)≥4，所以2m=∑deg(R)≥4(m-n+2)，解得m≤2n－4
3、证明：下图（彼得森图）不是欧拉图，也不是平面图。
证明：（1）彼得森图每个结点的度数都等于3，所以不是欧拉图。 （2）证明思路：只要能找出和K5或K3,3同胚的子图就行了。不过我找不出来，请各位学友找一找。
4、证明：在有6个结点12条边的连通简单平面图中，每个面由3条边组成。
证明：由欧拉公式可得，r＝8，假设至少有一个面不是3条边围成，则必定大于3条边，所以2e＞3r＝24，所以e＞12，这与已知有12条边相矛盾。
习题参考答案
1、说明具有6个结点的非同构的无向树的数目是多少。
答：应是6个。因为它是连通且无回路的无向树，因此在此树中只能有5条边。将这5条边按不同方式连接6个结点可得到6种形态的无向树，大家不妨画一画。
2、下面哪一种图不是树
a)无回路的连通图 b)有n个结点，n-1条边的连通图；
c)每对结点间都有路的图； d)连通但删去一条边则不连通的图。 答：c)不是树。每个结点都有路，则也包括回路，而树是无回路的，因此c)不是树。
3、连通图G是一棵树 ，当且仅当满足下述条件中哪一个 a)有些边不是割边； b)每条边都是割边； c)无边割边；
d)每条边都不是割边；
答：b)是树，因为在树中，删去任一条边均使图变得不连通，则此边就是割边。
4、一个树有2个4度结点，3个3度结点，其余结点都是叶子，则叶子数是多少
解：设叶子数为n,则根据树的定义和图中总度数是边数的2倍，可列出方程如下：
2×4+3×3+n×1=2×(n+2+3-1) 解之得：n=9
5、画出结点数n≤5的所有不同构的树。 解：如下图：
6、设图G是一棵树，它有n2个2度分枝点，n3个3度分枝点，...nk个k度分枝点，求G中叶结点数。
解：同第4题的解法，设叶结点数为n1，则有： n1+2×n2+3×n3+...knk=2(n1+n2+n3+...+nk-1) 解之得：n1=n3+2n4+3n5+...+knk+2+2
7、某城市拟在六个区之间架设有线电话网，其网点间距离如下面有权图矩阵给出，试给架设线路的最优方案，请画出图，并计算出线路的长度。
|0 1 0 2 9 0 | |1 0 4 0 8 5 | |0 4 0 3 0 10| |2 0 3 0 7 6 | |9 8 0 7 0 0 | |0 5 10 6 0 0|
A=
解：要解本题，实际上是求该网点组成的图的最小生成树，呵呵，这对学过数据结构的同学来说是比较容易的：请看下图：线路的长度为1+2+3+5+7=18
8、求算式((a+(b*c)*d)-e)÷(f+g)+(h*i)*j的树形表示。
解：如图所示：
9、画出下图中的一棵最小生成树，并写出该生成树的关系矩阵。
相关推荐：
loading