5.1习题参考答案
1、阮允准同学提供答案:解：设度数小于3的结点有x个，则有 3×4＋4×3＋2x≥2×16 解得：x≥4所以度数小于3的结点至少有4个所以G至少有11个结点 2、阮允准同学答案：证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。 若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。 若度数为5的结点数为6,8个，结论显然成立。 由上可知，G中至少有5个6度点或至少有6个5度点。 3、晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n.
给汶川小朋友的一封信4 \阮同学给出证明如下：
证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。
5、试证明下图中两个图不同构。
晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。 6、画出所有5个结点3条边，以及5个结点7条边的简单图。
解：如下图所示： (晓津与阮同学答案一致)
7、证明：下图中的图是同构的。
证明如下：
在两图中我们可以看到有
a→e,b→h,c→f,d→g
两图中存在结点与边的一一对应关系，并保持关联关系。
8、证明：下面两图是同构的。
阮同学给出证明如下：
证明：出对应关系：a---q, b----r, c-----s, d----t, e-----u,
f------v, g-----w, h----x
9、证明：三次正则图必有偶数个结点。
阮同学证明如下：
由题意可知每个结点度数都是3度，即每个结点均为奇结点，根据有偶数个奇结点可知，三次正则图必有偶数个奇结点。
5.2习题参考答案
1、
解：从A到F的初级路有：
ABCF、ABEF、ADEF、ABECF、ABCEF、ADECF、ADEBCF
2、晓津认为图中少了一个箭头：从V1到V2有一箭头。
从V2出发的初级回路有：V2V4V1V2、V2V3V4V1V2.
3、 解：若G为无向连通图，有n个结点，则G中至少有n-1条边。因为在n个结点的图中，任取一个结点为起始点，若要连通其他每个结点，则其他每个结点至少应有1度,此结点则有n-1度。因此总的度数至少为2n-2度，而度数为边的2倍，可算得边数为n-1.
对于有向图，若是弱连通，则与无向图一样至少为n-1,若是单侧连通也是如此，而强连通边数至少为n。(此题根据阮允准同学的答案更正)
4、 解： G-E'的连通分支数一定是2，而G-V'的连通分支数就不是定数了。有可能大于2.
5、答：可以。设七个人为图中的7个结点，以他们之间有共同语言为条件画边，可以看出，七个人的结点在图中是连通的，因此这七个人间可以通过相互翻译任意交谈。
6、证明如下：
必要性：如果图中的任何一个回路都不能包含所有结点,则可知未被包含在回路内的结点不能与其他结点中的某一结点连通。这与本图是强连通的相矛盾。因此必有这样一个路它至少包含每个结点一次。
充分性：当G中有一个回路，它至少包含每个结点一次时，可以知道，任一结点可达其他所有结点，因此它是强连通的。
7、若有简单图至多有2n个结点，每个结点度数至少为n，G是连通图。
又若简单图G至多有2n个结点，每个结点度数至少为n-1，那么G是连通图吗？为什么？
答：G不再是连通图，假若n=1时，G中至多可有2个结点，而每个结点度数至少可以为0，显然这两个结点不能连通。
以下是阮同学的答案：
方法一：设v1、v2是这个简单图的任意两个结点，由已知可得，v1、v2的度数至少为n，
（1）若v1、v2之间有边，则显然v1、v2是连通的。
（2）若v1、v2无边，则v1和剩下的结点中的n个结点有边相连，v2也和剩下的结点中的狐狸和乌鸦教学设计n个结点有边相连。因为剩下的结点最多只有2n-2个，由抽屉原理可得，至少存在一个结点，它和v1、v2都有边相连，此时v1和v2也是连通的。
由（1）（2）可知，结论成立
方法二：显然这个图中任意的一对结点的度数之和大于等于2n，所以这个图是汉密尔顿图，所以这个图是连通的。
8、证明如下：n个结点的简单无向图，连通的最低条件是有n-1条边。而e>0.5(n-1)(n-2)
可得e≥n-1，因此G是连通的。
上面的答案是错误的，阮允准同学纠正如下：因为一个连通图至少要有n-1条边，但并不是说至少有n-1条边的图一定是连通图。并且容易验证这个结论不成立。
证明如下：
在图G中，它的结点数为n，设v祓禊谣是G中任一结点，若把v去掉后，其它n-1结点，每个结点度数最多有n-1度，因此n-1个结点之间最多只有0.5（n-1)(n-2)条边，而e＞0.5(n-1)(n-2),所以至少有一条边连接摩托罗拉e375v和其它结点。
下面我用数学归纳法进一步证明：
（1）容易证明当n=1,2时，结论成立
（2）假设当n=k时，结论成立，即若e＞0.5（k-1)(k-2)时结论成立
（3）当n=k+1时，若此时每个结点度数为k，则结论显然成立，否则必存在一个结点v度数至多只有k-1度，即这个结点最多只有k-1条边和它相连。因为此时总的边数e>0.5k(k-1),则其它k个结点之间的边数e'＞0.5k(k-1)-(k-1)=0.5(k-1)(k-2)。根据归纳假设，显然这k个结点之间是连通的，而根据上面我们知道，至少有一条边使v和其它结点相连，所以此时这个图是连通的。
根据（1）（2）（3）可知结论成立。
5.3习题参考答案
1、设图 G=<V,E>,V={v1,v2,v3,v4}的邻接矩阵吉林建筑工程学院设计院
A(G)= | 0 1 0 1
1 0 1 1
1 1 0 0
1 0 0 0 |
| |
解：1、v1的入度是3.
v4的出度是1，
因为
A2(G)= | 2 0 1 1
2 2 0 1
1 1 1 2
0 1 0 1 |
| |
所以从v1到v4长度为2的路有1条。
2、 答：长度为4的路径总数为15条，其中3条是回路。从v3到v4的迹有3条。
3、 解:邻接矩阵如图：(按字母顺序)
M（G）＝ | 0 0 1 0 0
1 0 1 0 0
0 0 0 1 1
0 0 1 1 0
0 1 0 0 0 |
| |
a的出度是1，入度为1
b的出度是1，入度为1
c的出度是2，入度为3
d的出度是2，入度为2
e的出度是1，入度为1
晓津补充一下：出度就可以数该行的非零个数，入度则可数该列的非零个数
从结点c出发长度为3的回路有：c-e-b-c , c-d-d-c
4、给定G如图所示，
a)写出邻接矩阵
b)G中长度为4的路有几条？
c)G中有几条回路？
解：(晓津有疑问，v2、v3间没有箭头，则此图有错，暂且理解为双向连通吧)
a)M（G）＝ | 0 0 0 0 1
1 0 1 0 0
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0 |
| |
中国养老金发展报告2012
b) 有52条
c)无数条
(看到这里，晓津以为v2、v3间的箭头应向右更符合其本意，因为图中有某种对应的关系。)
5、
答：不连通
晓津补充一下：原矩阵为：
M(G)= | 1 0 0 1
0 0 0 0
0 1 0 1
0 0 0 0 |
| |
由此矩阵得到的路径矩阵为：
M4(G)= | 1 0 0 1
0 0 0 0
0 1 0 1
0 0 0 0 |
| |
可以发现图中些结点间没有路径存在。
6、
解：邻接矩阵为：
M(G)= | 0 1 0 1
0 0 1 1
0 1 0 1
0 1 0 0 |
| |
其余答案略，用阮同学的话说就是："太麻烦了，自己算一算吧":)
7、证明：必要性：设e是G某一连通分支的一条边。
假设e包含在G的某一回路中，若把e去掉后，显然该连通分支仍是连通的， 所以W（G－e）＝W（G）。这和e是G的割边矛盾。
充分性：设e是连接vi,vj的一条边，假设e不是割边。则把e去掉后，该连通分支仍是连通的
vi到vj必有路，不妨设此路为vi......vj,则必有vi.....vjevi,这和e不包含在G的任一回路中相矛盾，所以e是割边。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议