图论第三章
离散数学第八章一些特殊的图知识点总结
图论部分 第八章、一些特殊的图 8.1 二部图 二部图：定义设无向图G=
设M为G中一个匹配 v i与v j被M匹配: (v i,v j)∈M v为M饱和点: M中有边与v关联 v为M非饱和点: M中没有边与v关联 M为完美匹配: G的每个顶点都是M饱和点 定理(Hall定理) 设二部图G=
Hall定理中的条件称为“相异性条件”, 第二个定理中的条件称为t 条件. 满足t 条件的二部图一定满足相异性条件. 8.2 欧拉图 欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路. 欧拉图: 有欧拉回路的图. 半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明： 上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图的欧拉性.
图论与抽象代数复习
2013-2014二学期图论与抽象代数复习 第一部分 1.第三篇总复习题1，2，3题 2.第四篇总复习题1，4，6题 3.习题9 9.1题 4. *运算如下表所示，哪个能使({a,b},*)成为单元半群？（） 5. Q 是有理集，（Q，*）（其中*为普通乘法）不能构成（）。 A．群B．单元半群C．半群D．交换半群 6.设Z 是整数集，＋，·分别是普通加法和乘法，则（Z，＋，·）是（）。 A．域B．整环和域C．整环D．含零因子环 7. 在代数系统中，整环和域的关系为（）。 A．整环一定是域B．域不一定是整环 C．域一定是整环D．域一定不是整环 8. 设D =< V,E >为有向图，V = {a, b, c, d, e, f }，E = {( a,b),(b,c),(a, d), ( d, e),(f, e)}是（）。A．强连通图B．单向连通图C．弱连通图D．不连通图 9. 在有n 个结点的连通图中，其边数（）。 A．最多有n?1 条B．至少有n?1 条 C．最多有n 条D．至少有n 条 10设G = (n,m)为无向简单图，可构成邻接矩阵的数目为（）。 A．n! B．m! C．D． 11. 欧拉回路是（）。 A．通路B．简单回路 C．既是基本回路也是简单回路D．既非基本回路也非简单回路 12. 哈密尔顿回路是（）。 A．通路B．简单回路 C．既是基本回路也是简单回路D．既非基本回路也非简单回路 13. 下面哪一种图不一定是树?（） A．无回路的连通图B．有n 个结点n ?1条边的连通图 C．每对结点间都有通路的图D．连通但删去一条边则不连通的图 下述偏序集（见下图）中能构成格的是（） 下述偏序集中哪一个不构成格？（）
图论讲义第7章-平面图
第七章 平面图 §7.1 平面图的概念 定义7.1.1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S 。若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。 例如，下面是三个平面图及其平面嵌入。 根据定义，下列定理是显然的。 定理7.1.1 若图G 是平面图，则G 的任何子图都是平面图。 定理7.1.2 若图G 是非平面图，则G 的任何母图都是非平面图。 定理7.1.3 若图G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。 注：由以上定理知 (1) K n ( n ≤4 ) 和 K 1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图G 是简单图。 定义7.1.2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg (R )。 定理7.1.4 平面图G 中所有面的次数之和等于G 的边数的两倍，即 其中R 1, R 2, … , R r 是G 的所有面。 证明： 对G 的任何一条边e ，若e 是两个面 R i 和 R j 的公共边界，则在计算R i 和 R j 的次数时，e 各提供了1；若e 只是某一个面的边界，则在计算该面的次数时，e 提供了2。可见每条边在计算总次数时，都提供2。因而结论成立。 1 deg()2().r i i R G ε==∑
图论习题答案1
图论习题课作业1，3，6，8，10 By jgy
?作业1：第一章：1,2,4,12,20,29,35 ?作业3：第二章：14,28,30第三章：1,5,7,8?作业6：第五章：18,33 ?作业8：第六章：6,12,17 ?作业10：第七章10 第八章5,6,8
作业1 |E(G)|,2|E(G)|2G υυ?? ≤ ??? ?? ??? 1.1 举出两个可以化成图论模型的实际问题略 1.2 证明其中是单图 证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。
?1.20证明每顶皆二次的连通图是圈 ?证明：（思路）易证每顶皆二次的连通图中有圈。设图中最大圈为H，假设除H外还有其他顶点集U，任取u k，因为连通，u k 与H中任意顶均有一条道路，存在H中一顶h j与u k相邻，则h j为三次。 ?1.29 证明二分图的子图是二分图 ?方法一： ?定理1.2 图G是二分图当且仅当G中无奇圈 ?反证：设二分图为G，子图为S，假设S非二分图，由定理1.2知S中有 奇圈，则G中有奇圈，这与G是二分图矛盾。 ?方法二： ?（思路）定义：V(G) = X U Y, X n Y=空, 且X中任二顶不相邻，且Y中任二 顶不相邻。
?证明： ?(a)第一个序列考虑度数7,第二个序列考虑6,6,2 ?(b)将顶点v分成两部分v’和v’’ ?v’ = {v|v= vi , 1≤ i≤ k}, ?v’’ = {v|v= vi , k< I ≤ n} ?以v’点为顶的原图的导出子图度数之和小于 ?然后考虑剩下的点贡献给这k个点的度数之和最大可能为
图论教案
第六章图论(Graph Theory) ◎知识目标：掌握图的方法与原理；图的基本概念；最小树、最短路、最大流的概念、计算与应用；了解中国邮路问题与解法。 ◎能力目标：通过学习，使学生掌握图的方法与原理，提高分析问题和解决问题的能力。 ◎本章重点：最小树、最短路、最大流的计算与应用 ◎本章难点：最短路的应用、最大流的计算 引例：哥尼斯堡七桥问题 18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？欧拉于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。 有关图论研究的热点问题。18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来。当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥。这就是哥尼斯堡七桥问题。L.欧拉用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。他不仅解决了此问题，且给出了连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2。 当Euler在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动。Konigsberg城中有一条名叫Preg el的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。 Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。 后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。 七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成. 欧拉的这个考虑非常重要，也非常巧妙，它正表明了数学家处理实际问题的独特之处——把一个实际问题抽象成合适的“数学模型”。这种研究方法就是“数学模型方法”。这并不需要运用多么深奥的理论，但想到这一点，却是解决难题的关键。 接下来，欧拉运用网络中的一笔画定理为判断准则，很快地就判断出要一次不重复走遍哥尼斯堡的7座桥是不可能的。也就是说，多少年来，人们费脑费力寻找的那种不重复的路线，根本就不存在。一个曾难住了那么多人的问题，竟是这么一个出人意料的答案！
第六章 图论
第六章图论 §8.1 图论发展史 第一阶段：瑞士数学家欧拉（E. Euler）在1736年发表了一篇题为“依据几何位置的解题方法”的论文，有效地解决了哥尼斯城堡“七桥难题”，从此开创了图论的历史新纪元；所谓“七桥难题”是指：18世纪的哥尼斯堡城中流过一条河，河上有七座桥连接着河的两岸和河中的两个小岛，如图8-1所示：一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点；没有人想出这种走法，又无法说明走法不存在。欧拉将这个问题归结为如图8-2 所示的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点出发，能否通过每条边一次且仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。 图8-1 图8-2 第二阶段：1847年，数学家基尔霍夫（Kirchhoff）运用图论解决了电路理论中的求解联立方程的问题，他引入了“树”的概念，可惜由于他的思想超出了时代的发展而长期未被重视；到1857年，英国数学家凯莱（Cayley）又从化学的角度进一步扩展了“树”的概念，从此图论又有了新的发展。 第三阶段：1857年，英国数学家哈密尔顿（Hamilton）发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。 第四个阶段：20世纪以后，随着计算机的不断发展，图论也有了突飞猛进的进展，广泛应用于各科领域：如物理、化学、信息论，博弈论，计算机网络，等等；目前图论已经发展成完整的一个数学分支，并且越来越多的数学爱好者倾向于研究图论。