《图论及其应用》大作业。
第一题（讲过）
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是一条路。
满足题设。假设当k=t时，结论成立。接下来考虑k=t + 1时的情况。
在g中一个分支中取两个叶子点u与v，令p是连接该两个顶点的唯一路。
由于p上除u，v以外的点均被p经过两次，即g-p后除u，v以外的点奇偶性不变。
则g–p是有2t个奇度顶点的森林。
由归纳假设知，g–p可以分解为t条边不重合的路之并，即e(g-p)=e(p1) e(p2e(pt)。
则g可分解为t+1条边不重合的路之并，即e(g)=e(p1) e(p2e(pt) e(p)。
即证。第二题（讲过）
2.4.4证明：若e是kn的边，则τ（kn-e）=（n-2）nn-3
证明：由定理2.9：τ（kn）=nn-2
由于τ（kn-e）=τkn）-τ含有e的生成树棵树）
现在需要求含有e的生成树棵树，（含有e的生成树棵树）==2nn-3
（kn-e）=τkn）-τ含有e的生成树棵树）=（n-2）nn-3
第三题（讲过）
3.2.4证明：不是块的连通图至少有两个块，其中每个恰有一个割点。
证明：设g为不是块的连通图，由于g连通且不是块。
g有割点。当g只有1个割点v时，延割点分开，g1，g2内无割点，且连通，由块的定义知g1,g2是块，且分别含一个割点v。
当g含有2个及2个以上割点时，取相距距离最远的两个割点u和v，此时分g为三部分g1,g2,g3。
由于u，v是相距最远的两割点g1和g3不含割点。
又由于g连通，g1,g3为g的一部分故g1,g3连通。
g1，g3内无割点，且连通。
g1，g3是块，且分别含割点u，v。
即证。第四题。
5.2.2（a）证明：偶图g有完美对集当且仅当对所有sv有。
（b）举例说明：舍弃g是偶图这个条件之后，上述语句就不再成立。
a）证明：必要性。
偶图g有完美对集msg由于。
即证。充分性。
偶图g对所有sg有。将g分为偶图的两部分x和y。取。
又。同样，取。同理，由定理5.2，偶图g对所有sx有，则g为含有饱和x每个顶点的对集。又因为x，y的对称性。
偶图g有完美对集。
b）证明：例：当g为时，满足对所有sv有，但没有完美对集。即上述语句不再成立。
第五题。5.3.3证明一棵树g有完美对集当且仅当对于所有成立。
证明：必要性。
一棵树g有完美对集m，由定理5.4，由于g是完美对集，则。
且由于g是完美对集，则为偶数为奇数。
即证。充分性。
由于对所有的有，即存在中唯一的奇分支c0(v),令c0(v)与v的关联边为e（v）=uv。
此时v与e（v）存在一一对应关系，且e（u）=uv。由于v选择的任意性，于是。m为g的一个完美匹配。
第六题。6.1.6证明：若g是偶图，且，则g有一个边着色，使得所有种颜色都在每个顶点上表现。
证明：（反证法）
假设g是偶图，且，但是无法使得所有种颜色都在每个顶点上表现。
即g存在一个最优边着色，满足。
d（v）（v上表现的不同颜色数目）
由于引理6.1.2（g存在一个最优边着色，对于g中的一个顶点u和颜色i，j，使得i不在u上表现，而j在u上至少表现两次，则g中包含u的那个分支是奇圈。）
g中包含奇圈。
g不是偶图，导出矛盾。
原命题成立。
第七题。7.1.1（a）证明：g是偶图当且仅当对g的每个子图h均有。
b）证明：g是偶图当且仅当对g的每个适合的子图h均有。
证明：必要性。
由于g是偶图，g含有二分类（x，y）。由于h是g的子图，h也为含有二分类（x，y）的偶图。令， ,即得，。
必要性得证。
充分性。反证法）
假设g非偶图，则g必含有奇圈h，由于奇圈的性质。
与题设矛盾，充分性得证。
b)证明：必要性。
由于g是偶图，g含有二分类（x，y）。由于h是g的子图，h也为含有二分类（x，y）的偶图。故对于子图h，。
此时满足定理7.3的条件。
必要性得证。
充分性。反证法）
假设g非偶图，则g必含有奇圈h，由于奇圈的性质，有。
与题设不符。即假设为否。
充分性得证。
第八题（外找：图论的应用）
在平面上有n个点s＝，其中任两个点之间的距离至少是1，证明在这n个点中距离为1的点对数不超过3n。
证明：首先，将本题叙述转化为图的形式：将平面上s中两点之间距离。
d（u，v）恰好等于1的点对相连。得到图g（v,e），其中e，每条边连接的都是距离为1的点。
分析任一个顶点，设在图g中与u相连的点数为v1，v2，v3...vk。
由于题意：s中任两个点之间的距离至少是1，所以，以u为圆心画半径为1的圆，圆上最多。
有6个点。即。
每个s中顶点的度数。
由握手定理（定理1.1）
即。即证明这n个点中距离为1的点对数不超过3n。
第九题（外找：补图）
若图g是不连通的，则g的补图是连通的。
证明：设g=（v，e）不连通，其连通分支为g1，g2，…gs，其相应的节点集为v1，v2，…vs，任取中的两个节点u，v∈v，若u，v分属于g中不同的连通分支，则(u,v)∈，因此u，v在中连通。
若u，v分属于g中同一个连通分支，则从另一连通分支中任取一结点w，则(u,w)∈，v,w)∈，于是在中存在一条道路uwv，使得u，v连通。
综上所述，对于中任意2个结点，u，v总有路相连，故是连通的。
第十题（外找：欧拉公式的应用）
设g是有11个或更多结点的图，证明g或（补图）是非平面图。
证明：反证法）
设g和都是平面图，设g和的顶点数分别为n和，边数分别为m和，则。
n=，m+=（1/2）n(n-1)（补图的性质）
由欧拉定理可知，m3n-6， 3n-6（推论9.5.2）
1/2）n(n-1)= m+3n-6+3n-6=6n-12
即 n2-13n+240
从而得出n<11，与n11相矛盾，故g和不可能同时为平面图，即n11时，g或（补图）是非平面图。
第十一题（外找：连通图）
证明在n阶连通图中至少有n-1条边。
证明 ：先证明d(v)均 2的情形。
若对 v v(g),有d(v) 2,则由定理1.1：
2m= d(v) 2n
m n n-1,即证。
现证有一度顶点情况。
若g中有1度顶点，对顶点数n作数学归纳。
当n=2时，g显然至少有一条边，结论成立。
设当n=k时，结论成立，当n=k+1时，设d(v)=1，则g-v是k阶连通图，因此至少有k-1条边，所以g至少有k条边。
即证。第十二题（外找：连通度）
和δ是简单图g的最大度和最小度，则δ≤2m / n≤△。
证明：第十三题（外找：连通度）
证明：若δ≥2，则g包含圈。
证明：只就连通图证明即可。
设v(g)=｛v1,v2,…,vn｝,对于g中的路v1v2…vk,若vk与v1邻接，则构成一个圈。
若vi1，vi2，…vin是一条路，由于 2，因此，对vin，存在点vik与之邻接，则vik vin，vik构成一个圈 。
第十四题（外找：对偶图）
a）证明图是可平面图的充要条件是它的每一块均是可平面的。
b）推导极小非可平面图（即任意真子图均为可平面图）是一个单块。证明：a）
必要性。由定义可得。
充分性。使用数学归纳法。
假设g连通，对块数n使用归纳法。
当n=1时，结论成立。
假设n设v是g的割点，且g -v=g1+g2，显然g1,g2的块数均小于k。由归纳法设g1,g2均是可平面图，再有定理9.3
得到g的一个平面嵌入。
充分性得证。
b）若g是极小非可平面图，g应是单图。
又若g不是单块，于是g中存在割点，将g分解为g1,g2,g3...
由（a）知，这些块中必有非可平面块，这与g是极小非可平面图矛盾。
即证明g是一个单块。
第十五题（外找：对偶图）
9.2.4设g是平面图，证明：g**g的充要条件是g是连通的。
证明：必要性。
由于g是平面图，g中的点和边将g所在的平面划分成内点不相交的闭区域。这些面中的任意两面均可通过有公共边的面相连，故连通。从而g** 连通，又因为g**g，所以g连通。
必要性得证。
充分性。由对偶图的定义，g和g*嵌入在同一平面上，当g连通时g*的无界面f仅含g的唯一顶点v，除v外，g中的其他顶点u均与g*中相应的边一一对应。
于是g中顶点和g*中顶点一一对应，且邻接关系不变。
故g**g充分性得证。
图论建模作业
图论介绍及应用。图论是运筹学的一个分支，广泛应用于物理学 现代控制理论 信息论 管理科学 计算机技术等诸多领域。利用图论的理论和方法能够提供有力的数学模型是问题得到解决。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线...
图论1班作业
姚玉锦 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 生成树 包含了图中所有节点，且是不含回路的连通图。树枝数 m 1 与余树边 n m 1 之和等于边数n，由n m 1条余数弦形成n m 1个基本回路。9 基本关联矩阵的特征表示 矩阵内每行的非零元素表示与相应节点关联的分支，1表示流出该节点的分支，1为流入节点的分支。矩阵每列仅有 1和1组成，分...