9.平面图(new).ppt

17-,如果能将G的所有结点和边都画在一个平面上,且使得任何两条边除了端点外没有其它交点,则称G是个平面图。画出的没有边交叉出现的图,称为G的平图。一个图表面上是个非平面图,如果通过改变边的位置就变成平面图,称此图是可平面化的。(new)(new):K5和K3,3注:v5v4v2v3v1v5v4v2v3v1v5v4v2v3v1v5v4v2v3351624afbecdafbec(new)(new)二、、边界及面的次数设G是个平面图,图中边围成的区域,其内部不含有结点,也不含有边,:围成一个面f的所有边构成的回路,,称之为面f的度数,记作d(f).注1:在计算面的度时,割边被计算两次。注2:每个平面图恰有一个无界的面----(G):(G)=|F(G)|----(new)(new)(偶图)的定义:给定平面图G=<V,E>,可以定义另一个图G*=<V*,E*>,如下:,都有G*的顶点f*,都有G*的边e**中的点f*与g*被边e*相连*(new)(new)*是唯一的,且G**,则(G*)*=(G*)=m(G),n(G*)=r(G),d(v*)=d(f).,S*是G*中与C的各边ei对应的G*的边集合,则S*是G*:∵C把G的域分成两部分,∴E(G*)-S*把G*(new)(new),则证:设G*是G的对偶图,(new)(new)---关于点,,设n、m、r分别表示G中结点数、边数、面数,则有n-m+r=:(对面数r归纳证明)⑴当r=1时,,故G是树.(无圈连通),所以总是有m=n-1,于是n-m+r=n-(n-1)+1=2结论成立.⑵假设当G有r≤k-1个面时,结论成立.⑶当G有r=k个面且是连通图时,当k≥2时,至少有一个回路,所以去掉此回路中的一条边后得到子图G’,G’中有k-1个面,结点数同G中结点数,由⑵得n-(m-1)+(k-1)=2整理得n-m+k=2即n-m+r=2定理得证.(new)(new)Euler公式的推广形式定理:对任意p(p≥1)个连通分支的平面图G,有n-m+r=p+1。推论:对任意平面图G,有n-m+r≥2。(new)(new)推论1:若G是n≥3的简单连通平面图,则m3n-:设G是n≥3的简单连通平面图,则对fF,d(f)≥3成立,所以又由于,所以2m≥3r,由Euler公式n-m+r=2,得m≤3n-6。 (new)(new),则≤:当n=1,2时,≥3,由推论1,有∴≤***(new)(new)