您当前位置:www.6534.com > www.6534.com >

www.6534.comClass teacher

3中有6个结点9条边

2019-09-06  admin  阅读:

 

 

  4-6 平面图 沉点:控制欧拉及其证明。 一、平面图 1、定义4-6.1 若是无向图G=V,E的所有结点和 边能够正在一个平面上图示出来,而使各边仅正在极点 处订交。无向图G称为平面图,不然称G为非平面 图。 有些图形从概况看有几条边是订交的,可是不 能就此必定它不是平面图,例如,下面左图概况看 有几条边订交,但如把它画成左图,则可看出它是 一个平面图。 有些图形非论如何改画,除去结点外, 总有边订交。故平面图。 2、面、鸿沟 定义4-6.2:设G是连续通平面图,由图中的边所 包抄的区域,正在区域内既不包含图的结点,也不包含 图的边,如许的区域称为G的一个面,包抄该面的诸 边所形成的回称为这个面的鸿沟。面r的鸿沟的长度 称为该面的次数,记为deg(r)。 定义4-6.3 设图G=V,E是连续通平面图,由图中 各边所界定的区域称为平面图的面(regions)。有界的 区域称为有界面,的区域称为面。界定各面 的闭的径称为面的鸿沟(boundary),面r的鸿沟长 度称为面r的度(degree)记为deg (r) ,又称为面r的 次数 。 例如图 deg(r1)=3 deg(r2)=3 deg(r3)=5 deg(r4)=4 deg(r5)=3 deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5) =18 3.4-6.1 设G为一无限平面图,面的次数之 和等于其边数的两倍。 ? 证明思:任一条边或者是两个面的配合鸿沟 (贡献2次),或者是一个面的反复边(贡献2次) ? 如边是两个面的分界线,该边正在两个面的度数中 各记1次。如边不是两个面的分界线(称为割边)则该边 正在该面的度数中反复记了两次,故结论成立。 4、欧拉 4-6.2(欧拉) 式成立 v–e+r=2 证明 设G为一平面连通图, v为其极点数,e为其边数,r 为其面数,那么欧拉公 (1)若G为一个孤立结点,则v=1,e=0,r=1, 故 v-e+r=2成立。 (2)若G为一个边,即v=2,e=1,r=1, 则 v-e+r=2成立。 (3)设G为k条边时,欧拉公式成立,即 vk-ek+rk=2。 调查的环境。 由于正在k条边的连通图上添加一条边,使它仍为连通图, 只要下述两种环境: ①加上一个新结点b,b取图上的一点a相 连,此时vk和ek两者都添加1,而面数rk没 变,故 ( vk +1)-( ek +1)+ rk = vk-ek+rk=2。 ②用一条边毗连图上的已知两点,此时ek 和rk都添加1,结点数vk没变,故 vk -(ek +1)+(rk +1)=vk-ek+rk=2。 例:已知一个平面图中结点数v=10,每个面均由 4条边围成,求该平面图的边数和面数。 解:因每个面的次数均为4,则2e=4r,即e=2r, 又v=10,代入欧拉公式v-e+r=2有10-2r+r=2解得 r=8,则e=2r=16。 5.4-6.3 设G为一简单连通平面图,其极点数 v≥3,其边数为e,那么 e≤3v – 6 ? 证明思:设G的面数为r,当v=3,e=2时上式成立, 若e=3,则每一面的次数不小于3,各面次数之和不小于 2e,因而 2e≥3r, r≤2e/3 代入欧拉公式: 2=v-e+r≤v-e+ 2e/3 拾掇后得: e≤3v – 6 ? 本的用处:鉴定某图平面图。 申明:这是简单 图是平面图的必 要前提。 例如:K5中e=10,v=5,3v-6=9,从而e3v-6, 所以K5不是平面图。 4.6.3的前提不是充实的。如K3,3图满 脚4-6.3的前提(v=6,e=9,3v-6=12, e≤3v-6成立),但K3,3不是平面图。 证明K3,3图不是平面图。 证明 假设K3,3图是平面图。 正在K3,3中任取三个结点,此中必有两个结点不 邻接,故每个面的次数都不小于4, 由4r≤2e,r≤e/2,即 v-e+e/2≥v-e+r=2, v-e/2≥2, 2v- e ≥ 4, 2v-4≥e。 正在K3,3中有6个结点9条边, 2v-4=2×6-4=89,取 2v-4≥e 矛盾, 故 K3,3不是平面图。