平面圖的概念與性質(zhì)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院應(yīng)用數(shù)學(xué)系張欣(編輯修改稿)
2025-08-15 00:10 本頁面
【文章內(nèi)容簡介】 G中，頂點(diǎn)和邊都與某個(gè)給定區(qū)域關(guān)聯(lián)的子圖，稱為該面的 邊界 。某面 f 的邊界中含有的邊數(shù) (割邊計(jì)算 2次 )稱為該面 f 的 度數(shù) , 記為 deg ( f )。 平面圖 G f1 f3 f2 f4 在上圖中，綠色邊在 G中的導(dǎo)出子圖為面 f3 的邊界。 1de g( ) 1f ? 2de g( ) 3f ? 3de g( ) 6f ? 4de g( ) 6f ? 平面圖的度數(shù)公式 定理 1 設(shè) G=(n, m)是平面圖，則： de g( ) 2ffm????證明： 對 G的任意一條邊 e, 如果 e是某面割邊，那么由面的次數(shù)定義，該邊給 G的總次數(shù)貢獻(xiàn) 2次；如果 e不是割邊，那么，它必然是兩個(gè)面的公共邊，因此，由面的次數(shù)定義，它也給總次數(shù)貢獻(xiàn) 2次。于是有： de g( ) 2ffm???? 平面圖的歐拉公式 定理 2(歐拉公式 ) 設(shè) G=(n, m)是連通平面圖， ф 是 G的面數(shù)，則： 2nm ?? ? ?證明： 情形 1，如果 G是樹，那么 m=n1, ф=1。在這種情況下，容易驗(yàn)證，定理中的恒等式是成立的。 情形 2， G不是樹的連通平面圖。 假設(shè)在這種情形下，歐拉恒等式不成立。則存在一個(gè)含有最少邊數(shù)的連通平面圖 G, 使得它不滿足歐拉恒等式。設(shè)這個(gè)最少邊數(shù)連通平面圖 G=(n, m), 面數(shù)為 ф，則： 2nm ?? ? ? 因?yàn)?G不是樹，所以存在非割邊 e。顯然， Ge是連通平面圖，邊數(shù)為 m1, 頂點(diǎn)數(shù)為 n, 面數(shù)為 ф1。 由最少性假設(shè)， Ge滿足歐拉等式： 化簡得：
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1