资源描述：
《离散数学 第2版 教学课件 作者 王元元 离散第22讲 平面图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机专业基础课程授课人：王元元单位：计算机理论教研室理工大学指挥自动化学院PowerPointTemplate_Sub1二分图2平面图3树2第22讲平面图平面图《离散数学》第22讲Page134to139问题的提出原料库1原料库2原料库3施工点A施工点C施工点B4第22讲平面图问题的提出K3,3能否在一个平面上图示出来，使得各边仅在顶点处相交，在其他地方都不相交5第22讲平面图平面图的概念定义：无向图G称为平面图，如果G可以在一个平面上图示出来，而使各边仅在顶点处相交。否则称G为非平面图。6第22讲平面图非平面图完全二分图K3,3K57第22讲平面
2、图平面图的面定义：平面连通图中各边所界定的区域称为平面图的面。界定各面的闭的拟路径称为面的边界，它的长度称为面的度。分类：有界的区域称为有界面，无界的区域称为无界面。8第22讲平面图r1r2r3示例界定面的闭的拟路径：r1：(v1,v2,v5,v1)，度为3r2：(v2,v3,v4,v5,v2)，度为4r3：(v1,v2,v3,v4,v5,v1)，度为5v1v2v3v4v5V2V1r1r2界定面的闭的拟路径：r1：(v2,v2)，度为1r2：(v1,v2,v2,v1)，度为39第22讲平面图示例v6v7v8v5v4v3v2v110第22讲平面图示例界
3、定面的闭的拟路径：r1：(v1,v1)，度为1r2：(v2,v3,v2)，度为2r3：(v4,v5,v8,v4)，度为3r4：(v5,v6,v7,v6,v8,v5)，度为5r5：(v1,v1,v2,v3,v4,v5,v6,v8,v4,v3,v2,v1)，度为11v6v7v8v5v4v3v2v1r5r1r2r3r411第22讲平面图极大平面图定义：给定平面简单图G，如果在G中添加任一边(该边既不是环，也不是重边)后所得的图均不是平面图，则称G为极大平面图。12第22讲平面图极大平面图性质定理9-3：极大平面图所有有界面都是三度的面，无界面也是三度的。即
4、所有面的边界均为K3。证：反设极大平面图有4度的面，其边界为(v1,v2,v3,v4,v1)。若该面为无界面，那么可在无界面内联结(v2,v4)；若该面为有界面，那么可在有界面内联结(v2,v4)。联结后所产生的图均仍为平面图，这与平面图的极大性冲突。例如：v1v2v3v413第22讲平面图极大平面图性质证：设v是极大平面图G的任一顶点。考虑G-v。G-v是一平面图，v原在G-v的一个面内。由于G为一简单图，G-v的这个面的边界上至少有3个顶点。由G的极大平面性，v与这些顶点之间都有边关联，因此v至少是3度的顶点。定理9.4：顶点个数n≥4的极大平面
5、图中，顶点的最小度数不少于3。14第22讲平面图欧拉公式定理9.5：设G为一平面连通图，n为顶点数，m为其边数，r为其面数，那么n–m+r=2。（欧拉公式）例：n=4m=6r=4n–m+r=2。15第22讲平面图欧拉公式--证明证明：对边数m归纳。当m=0时G为一孤立顶点，n=1，m=0，r=1，从而n–m+r=2。设边数小于m的平面连通图均满足欧拉公式，现考虑G(边数m>0)，在G中任意去掉一边e得到图G’。下面对e的情况分别进行讨论欧拉公式证明G’eG1G2eG’(1)e为一环，那么G’的顶点数、边数、面数分别是n’=n,m’=m–1,r’=r–
6、1据归纳假设，n’–m’+r’=2。因而n–(m-1)+r–1=2即n–m+r=216第22讲平面图欧拉公式--证明证明：对边数m归纳。当m=0时G为一孤立顶点，n=1，m=0，r=1，从而n–m+r=2。设边数小于m的平面连通图均满足欧拉公式，现考虑G(边数m>0)，在G中任意去掉一边e得到图G’。下面对e的情况分别进行讨论欧拉公式证明G’eG1G2eG’(2){e}为割集，不妨设G’有两个连通分支G1，G2。显然n1+n2=n’=n，m1+m2=m’=m–1，r1+r2=r’+1=r+1据归纳假设n1–m1+r1=2，n2–m2+r2=2从而(n
7、1+n2)–(m1+m2)+(r1+r2)=4，n–(m-1)+r+1=4即n–m+r=217第22讲平面图欧拉公式--证明证明：对边数m归纳。当m=0时G为一孤立顶点，n=1，m=0，r=1，从而n–m+r=2。设边数小于m的平面连通图均满足欧拉公式，现考虑G(边数m>0)，在G中任意去掉一边e得到图G’。下面对e的情况分别进行讨论欧拉公式证明G’eG1G2eG’(3)e关联G中两个顶点但{e}非割集，那么G’的顶点数、边数和面数分别是n’=n,m’=m–1,r’=r–1据归纳假设n’–m’+r’=2，从而n–(m–1)+r–1=2即n–m+r=2
8、。归纳完成，定理得证。18第22讲平面图欧拉公式推论定理9.6：如果平面连通图G的每个面的边界都具有长度l(
