Question

离散数学第五版：第六章知识点概要

Answer 1

        第六章为特殊的图，主要讲了主要讲了二部图，欧拉图，哈密顿图和平面图。

        第一节为二部图，介绍风格和往常一样，先介绍了很多概念，比如二部图（偶图），互补顶点子集，和一些匹配的相关概念，大面上来说，二部图就是能把顶点分为两部分的图，且要求每一个部分中的顶点之间不存在边。匹配指的是不相邻的边的集合，这当中分了极大和最大的概念，极大指的是边不能再多的一个匹配，最大指的是所有匹配中边数最多的。

        第二节为欧拉图，说到欧拉图最早应该追溯十八世纪的一个哥尼斯堡七桥问题，讲的是在四个岛七座桥之间，是否存在经过且只经过一次每一条边的回路，欧拉发现了解决这个问题的方法，因此也有了欧拉回路这种东西。而存在欧拉回路的图，可以称之为欧拉图。

        第三节为哈密尔顿图，这个就很有意思了，刚刚好和欧拉回路形成了对应。哈密尔顿回路指的是经过图中每一个节点且只经过一次的回路。其主要的火力点为节点而不是边，满足哈密尔顿回路的图则称为哈密尔顿图。

        第四节为平面图，看到这里总感觉这一章很搞笑，不管是二部图、欧拉图还是哈密尔顿图，都是那种一看名字一头雾水，但实际上理解起来简单到爆炸的概念，平面图不偏不倚，刚刚好的反其道而行之。它是指通过不同的画法，能否使得边与边除了在顶点处汇集外不交，如果可以，这个图就是平面图，你实现的画法，称为它的一个平面嵌入。后面有涉及平面图的充分必要条件之类的，用时再深入理解即可。