计算机问题求解（PPT讲稿）图论中的其它专题

计算机问题求解-论题314 图论中的其它专题 2018年12月11日

计算机问题求解 – 论题3-14 - 图论中的其它专题 2018年12月11日

平面图 sa (b)H: y 2 2 问题1: 个图是香为平面图与其 如何画法有关吗?

平面图

Theorem 9. 1(The Euler Identity) If G is a commected plane graph of order n, size m and having r regions, then n-m+r=2. 证明要点: 1,树是满足欧拉公式 2,反证法:如果除树外,欧拉公式不成立 21找一个边最少的图 如果我们用归纳 2.11必定存在回路 法证明该定理, 22去除回路上一条边,构造新图 该如何归纳? 221新图有n个点,m-1条边,「-1个区域 23新图满足欧拉公式(原图是最小的) 231n-m-1)+(r-1)=2 2.32n-m+r=2 24矛盾 3,欧拉公式满足

证明要点： 1，树是满足欧拉公式 2，反证法：如果除树外，欧拉公式不成立 2.1 找一个边最少的图 2.1.1 必定存在回路 2.2 去除回路上一条边，构造新图 2.2.1 新图有n个点，m-1条边，r-1个区域 2.3 新图满足欧拉公式（原图是最小的） 2.3.1 n-(m-1)+(r-1) = 2 2.3.2 n-m+r=2 2.4 矛盾 3，欧拉公式满足 如果我们用归纳 法证明该定理， 该如何归纳？

间题2 你是否在哪里里还见过“这个” 欧拉公式?

问题3 必要条件可以判断什么? 欧拉公式在实际判断平面 图时有用吗?

简单连通平面图的必要条件 欧拉公式的推论:若G是简单连通平面图(m≥3),则 m<3n-6。 g证明:至少3个顶点的简单图G中,面的最小边数是3, 3r<2m,根据欧拉公式:3r=3m+6-3n,:3m+6-3n<m,即 m<3n-6。 aK不是平面图:在K,中,n=5,m=10,3n-6=9。 平面图中,边数是有上限的。请问,这个界是否紧致?

简单连通平面图的必要条件 ◼ 欧拉公式的推论：若G是简单连通平面图(n3), 则 m3n-6。 ❑ 证明：至少3个顶点的简单图G中，面的最小边数是3， 3r2m, 根据欧拉公式：3r=3m+6-3n, 3m+6-3n2m, 即： m3n-6。 ◼ K5不是平面图：在K5中，n=5,m=10, 3n-6=9。 平面图中，边数是有上限的。请问，这个界是否紧致？

问题4 上述推论不能证明K3是非平面图, 你能推出一个类似的推论用于K3吗? 二部图的一个区 域至少多少条边?

二部图的一个区 域至少多少条边？

同胚图 基本动作: g二次顶点的插入和消去 如果图G和G经过反复的插入和消去二次顶点,可达到同构,则G和 G是同胚图

同胚图 ◼ 基本动作： ❑ 二次顶点的插入和消去 ◼ 如果图G1和G2经过反复的插入和消去二次顶点，可达到同构，则G1和 G2是同胚图。 u u v v w

图的收缩 基本动作: (u, v) n图的收缩

图的收缩 ◼ 基本动作： ◼ 图的收缩 u v u v e w (u,v)

平面图的充分必要条件 Kuratowski定理 口图G是平面图当且仅当G中不含与K或者K3同胚的子图,也不含可以 收缩到K或者K3的子图

平面图的充分必要条件 ◼ Kuratowsky定理 ❑ 图G是平面图当且仅当G中不含与K5或者K3,3同胚的子图,也不含可以 收缩到K5或者K3,3的子图