史灵生《离散数学》清华大学-D12Euler.pdfVIP

Discrete Mathematics Lecture 12 Euler’s Formula 1 planar graph 一、平面图 （ ） 定义 如果图G=( V,E) 的所有顶点和边可 以在一个平面上图示出来，而使各边仅 G 在顶点处相交，则图 称为平面图，否 G 则称 为非平面图。 2 有些图形从表面看有几条边是相交的， 但是不能就此肯定它不是平面图，例如， 下面左图表面看有几条边相交，但如把 它画成右图，则可看出它是一个平面图。 3 有些图形不论怎样改画，除去顶点外， 总有边相交。如 图，故它是非平面图。 K3,3 Two drawings of K3,3. 4 二、面(face)和边界(boundary) 定义设 是一连通平面图，由图中的边 G 所包围的区域，在区域内既不包含图的 顶点，也不包含图的边，这样的区域称 为 的一个面，有界的区域称为有界面， G 无界的区域称为无界面。 包围该面的诸边所构成的回路称为这个 面的边界。面 的边界的长度称为该面 F 的度数，记为 。 d( ) F 5 d(r )=3, d(r )=3, d(r )=5, d(r )=4, d(r )=3. 1 2 3 4 5 6 d(r )+d(r )+d(r )+d(r )+d(r )=18. 1 2 3 4 5 7 定理有限平面图面的度数之和为其边数的两倍： ∑d(F)=2|E |。 证明思路：任一条边或者是两个面的共同边界 （贡献2次）,或是一个面的重复边（贡献2次） 如边是两个面的分界线，该边在两个面的度数 中各记 次。 1 如边不是两个面的分界线 称为桥 则该边在该 ( ) 面的度数中重复记了两次，故定理结论成立。 8 3、Euler’s Formula 定理12.1.1 设G为一平面连通图，v为其 顶点数，e为其边数，f 为其面数，那么 Euler公式成立：v – e +f = 2 。 证明：对面数进行归纳。 若f =1,则G为一棵树，且