一筆畫(huà)問(wèn)題及解決策略(編輯修改稿)
2025-04-20 05:37 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 引理：在任一網(wǎng)絡(luò)圖中決不能只有一個(gè)奇頂點(diǎn)。由于任一頂點(diǎn)的指數(shù)是指相交于這一頂點(diǎn)處的弧數(shù)，所以網(wǎng)絡(luò)中所有頂點(diǎn)的指數(shù)之和等于相交于每個(gè)頂點(diǎn)處的弧數(shù)的總和，從而等于網(wǎng)絡(luò)圖總數(shù)的2倍，故任一網(wǎng)絡(luò)圖中所有頂點(diǎn)的指數(shù)之和一定是偶數(shù)。而若某個(gè)網(wǎng)絡(luò)中只有一個(gè)奇頂點(diǎn)，那么除該頂點(diǎn)的指數(shù)是奇數(shù)外，其余任一頂點(diǎn)的指數(shù)均為偶數(shù)，所以該網(wǎng)絡(luò)中所有頂點(diǎn)的指數(shù)之和就是奇數(shù)。矛盾。所以任一網(wǎng)絡(luò)中都不可能只有一個(gè)奇頂點(diǎn)。設(shè)一個(gè)連通網(wǎng)絡(luò)中奇頂點(diǎn)個(gè)數(shù)是2或0，那么該網(wǎng)絡(luò)圖可以一筆畫(huà)。分兩種情形來(lái)討論：、（1） 若連通網(wǎng)絡(luò)的奇頂點(diǎn)個(gè)數(shù)是0個(gè)，則該網(wǎng)絡(luò)中每個(gè)頂點(diǎn)都是偶頂點(diǎn)。如圖，取任一頂點(diǎn)A和以為起點(diǎn)的一條弧AB。在網(wǎng)絡(luò)中去掉弧AB,于是減少1，頂點(diǎn)數(shù)不變，A和B變?yōu)槠骓旤c(diǎn)，其余頂點(diǎn)仍然是偶頂點(diǎn)。此時(shí)，剩下的網(wǎng)絡(luò)圖仍然是連通的，這是因?yàn)?，如果去掉弧AB后網(wǎng)絡(luò)分離為沒(méi)有聯(lián)系的兩個(gè)連通分支，那么頂點(diǎn)A和B就分別在兩個(gè)不同的分支中，其中任一連通分支都只有一個(gè)奇頂點(diǎn)，這由引理可知是絕不可能的。所以，該網(wǎng)絡(luò)去掉弧AB后剩下的網(wǎng)絡(luò)一定是奇頂點(diǎn)個(gè)數(shù)為2的連通圖，且比原網(wǎng)絡(luò)減少一條弧。（2） 若連通網(wǎng)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1