《图论复习题》PPT课件

《《图论复习题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章图和子图图的基本概念；常见的特殊图类；二部图及其性质；图的同构；关联矩阵与邻接矩阵；路、圈与连通图；最短路问题。K-方体图是其顶点为0与1的有序k元组,当且仅当它们的一个坐标不相同时,此两个顶点相连以边。证明k-方体图是有2k个顶点k2k-1条边的2-部图。导出子图和图的运算G2G1G2G1由定理1.2可知图(a)所示的图不是二分图，因为它包含一个长为3的圈,图(b)所示的图是一个二分图，它不含长为奇数的圈.定理一个图是二部图当且仅当它不含奇圈。证明：设P=v0v1…vk是G的最长路。因为d(v0)≥3，所以存在两个与v1相异的顶点v′,v"

2、与v0相邻。v′,v"必都在路P上，否则会得到比P更长的路。无妨设v′=vi,v"=vj,(i

3、图G[Vi]为图G的一个连通分支（i=1,2,…,ω）。事实上，假如G不连通，则至少有一个连通分支的顶点数不超过n。在此连通分支中，顶点的度至多是n−1。这与δ(G)≥n矛盾。证毕。例设有2n个电话交换台，每个台与至少n个台有直通线路，则该交换系统中任二台均可实现通话。证明：构造图G如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路。问题化为：已知图G有2n个顶点，且δ(G)≥n，求证G连通。V1112921865129734136971V1V2V3V4V5V6V7V8V9V10240∞∞∞∞∞∞∞∞∞∞应用：最短路问题算法实现－标

4、号法课后习题（a）G是单图且证明G连通.（b）v>1时，找一个不连通的单图G使得证：（a）若G不连通，可分为两个顶点数分别为v1，v2的互不连通子图G1，G2。易知于是这与矛盾！（b）G=Kv-1+K1即为所求的单图。课后习题：证明在任何两个或两个以上人的组内,存在两个人在组内有相同个数的朋友。证：令上述组内人的集合为图G的顶点集合，若两人互相是朋友，则其间连以一边，所得之图G是组内人员的朋友关系图。显然G是单图，图中顶点的度恰表示该人在组内朋友的个数，利用图G，上述问题就抽象成如下的图论问题：在一个单图G中，若v（G）≥2，则在G中存在度相等的两

5、个顶点。用反证法，设G中各点的度均不相等。必有最大度△≥v-1。若△=v-1，必有δ≥1，从而△-δ+1v-1,又与G是单图矛盾。树及其基本性质；最小生成树。第二章定理下列命题等价：（1）G是树；（2）G中无环边且任二顶点之间有且仅有一条路；（3）G中无圈且ε=ν−1；（4）G连通且ε=ν−1;（5）G连通且对任何e∈E(G)，G−e不连通；（6）G无圈且对任何e∈E(G)，G+e恰有一个圈。证明：（1）⇒（2）G是树⇒G连通⇒∀u,v∈V(G)，存在路P(u,v)。逆定理的成立见习题2.1.1若还存在一条路P′(

6、u,v)≠P(u,v)，则必存在w，w是路P与P′除了v之外最后一个公共顶点。P的(w,v)段与P′的(w,v)段构成圈，这与G是树矛盾。故只存在唯一的(u,v)路。ν=1时，ε=0，结论真。假设ν≤k时结论真，我们来证明当ν=k+1时，也有ε=ν−1成立。当ν=k+1时，任取u,v∈V(G)。考虑图G′=G−uv，因G中u、v间只有一条路，即边uv，故G′不（2）⇒（3）若G有圈，则此圈上任二顶点间有两条不同的路，与前提条件矛盾。下面用归纳法证明ε=ν−1。连通且只有两个连通分支，设为G1,G2。注意到G1,G2分别都连通且任二顶点间只有一条路，

7、由归纳法假设，因此归纳法完成。（3）⇒（4）用反证法。若G不连通，设G1,G2,…,Gw是其连通分支（w≥2），则（因Gi是连通无圈图，由已证明的(1)和(2)知，对每个Gi，(3)成立）。这样，，这与矛盾。（4）⇒（5）ε(G−e)=ε(G)−1=ν−2，但每个连通图必满足ε≥ν−1（见下列命题），故图G−e不连通。ν=1,2时，ε≥ν−1显然成立。假设ν≤k的连通图都ε≥ν−1。对于ν=k+1的连通图H，任取v∈V(H)，考虑H−v。若H−v连通，则由归纳假设，ε(H−v)≥ν(H−v)−1=k−1，而命题若图H连通，则ε(H)≥ν(H)−1。

8、证明：对ν做数学归纳法。ε(H)≥ε(H−v)+1≥(k−1)+1=(k+1)−1=ν(H)−1。若H−v不连通，设H1,