姚玉锦 201621050124 光电信息学院图论1班。
习题一。4.证明图1-28中的两图是同构的。
图 1-28
证明：作映射f : vi ui (i=1,2….10)
容易证明，对vi v j e ((a)),有f (vi vj,),ui , uj ,,e,((b))
1<=i <=10, 1<=j <=10）由图的同构定义知，图（a）和图（b）是同构的。
5.证明：四个顶点的非同构简单图有11个。
证明：按边的条数采取枚举法，如下表所示：
四个顶点的简单图至多只能有6条边，因此上表已穷举了所有情况，因此四个顶点的非同构简单图只有11个，原题得证。
11. 证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。
证明：①对于第一个序列（7,6,5,4,3,3,2），考察非负整数组。
显然 п2不是图序列，因此序列（7,6,5,4,3,3,2）不是图序列；
对于第二个序列（6,6,5,4,3,3,1），考察非负整数组。
由于п不是图序列，因此原序列（6,6,5,4,3,3,1）也不是图序列。
17. 证明：若g不连通，则g的补图是连通的。
证明：对u,v∈v ，若u与v属于g的不同连通分支，显然u与v在的补图中连通；若u与v属于g的同一连通分支，设w为g的另一个连通分支中的一个顶点，则u与w，v与w分别在u与v在g的补图中是连通的。
18. 证明：若∈ ，则。
证明：若e是g的割边，则ω e =ω1 ，若e是g的非割边，则。
e =ω所以，若e∈e ，则有ω ≤e ≤ω1 。
习题二。1. 证明：非平凡树的最长路的起点和终点均是1度的。
证明：若非平凡树中的（u, v）路的起点或终点的度大于1，这时因树无圈，易知（u, v）路可继续延长。故对非平凡树种的最长路的端点和终点度必须为1。
9. 证明：顶点度数为偶数的连通图本身可构成一个包含所有边的回路。
证明：当且仅当g是连通图且g中每个顶点的度数均为偶数时，g是欧拉图，则由欧拉图的定义可知，g中含欧拉回路，有欧拉回路是包含图中每条边的简单回路，因此顶点度数为偶数的连通图本身可构成一个包含所有边的回路。
16. kruskal算法能否用来求：
赋权连通图中的最大权树？
赋权图中的最小权的最大森林？
如果可以，怎样实现？
解：⑴ 可以用kruskal算法，只需把kruskal算法中的“小”字换为“大”字。
即可； 可以用kruskal算法，只需对g的每一分支施行kruskal算法。
习题三。1. 证明：e是连通图g的割边当且当可划分为两个子集和 ，使对∈及∈ ，g中的（u, v）路必含e。
证明：对于任意的u∈v1，v∈v2，如果点e不在某一条(u, v)路上，那么该路也是连接g-e中的u与v的路，这与u,v处于g-v的不同分支矛盾；
若e不是图g的割点，那么g-v连通，因此在g-v中存在(u, v)路，当然也是g种一条没有经过点e的(u, v)路，矛盾。
3 设g是阶大于2的连通图，证明下列命题等价：
g是块；g无环且任意一个点和任意一条边都位于同一个圈上；
g无环且任意三个不同点都位于同一条路上。
证明：⑴g是阶大于2的连通图当且仅当g连通、无割点且至少含有三个点， 由块的定义可知g是块和g是阶大于2的连通图是等价命题；
⑵令u是任意一顶点，vw是任一边，则存在包含u,v的圈c。若w∈c,则c 中含u的（v, w）段+vw构成的圈c′,即为所求；若w不属于c，则v 不是g的割点，故存在不过v点的（u, w）路p，设x由w出沿p前进、与c相交的第一个顶点，则c中含u的（v, x）段+p中的（w, x） 段+vw构成圈c′，即为所求。
设u,v是任意两个顶点，w是任意第三个顶点，e是w的关联边， 由前可知存在过e的（u, v）路，显然此路必过w。
7. 证明：若v是简单图g的一个割点，则v不是补图的割点。
证明：v是单图g的割点，则g-v至少两个连通分支。现在任取。
x,y∈vv,如果x,y在g-v的同一分支中，令u是与x,y处于不同分支的点，那么，通过u，可说明，x与y在g-v的补图中连通。若x,y在g-v的不同分支中，则他们在g-v的补图中邻接。所以，若v是g的割点，则v不是其补图的割点。
12. 对于3-20给出的图和，求其连通度和边连通度，给出相应的最小点割和最小边割。
由于在g1中，w(g113)w(g1)，所以连通度为2，最小点割为；
w(g11434)w(g1)，边连通度为2，所以最小边割为。
在g2中，w(g2137)w(g2)，所以所以连通度为3，最小点割为。
1,3,7}；w(g2122327)w(g2)，边连通度为3，所以最小边割为。
注由于g2的轮换对称性，类似的点和边都满足条件）
13.设h是连通图g的子图，举例说明：有可能k（h）> k（g）。
解：如下图所示，h是g的子图，k(h)=3>k(g)=1gh
图论大作业
图论及其应用 大作业。第一题 讲过 2.1.9证明 若g是森林且恰有2k个奇点，则在g中有k条边不重的路p1,p2.pk,使得e g e p1 e p2e pk 证明 对奇点数k使用数学归纳法。当k 1时，g是森林，且有且只有2个奇点。g只能为一颗树，且g的所有奇度顶点为两个1度顶点。g是一条路。满...
图论建模作业
图论介绍及应用。图论是运筹学的一个分支，广泛应用于物理学 现代控制理论 信息论 管理科学 计算机技术等诸多领域。利用图论的理论和方法能够提供有力的数学模型是问题得到解决。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线...
图论第二章作业
5 生成树 包含了图中所有节点，且是不含回路的连通图。树枝数 m 1 与余树边 n m 1 之和等于边数n，由n m 1条余数弦形成n m 1个基本回路。9 基本关联矩阵的特征表示 矩阵内每行的非零元素表示与相应节点关联的分支，1表示流出该节点的分支，1为流入节点的分支。矩阵每列仅有 1和1组成，分...