數(shù)據(jù)結(jié)構(gòu)pascal-資料下載頁(yè)
2025-06-25 07:21本頁(yè)面
【正文】 60。 圖1 V={V1,V2,V3,V4,V5} E={(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)} 下圖是一有向圖（頂點(diǎn)分先后順序） V={V1,V2,V3,V4} E={V1,V2,V2,V4,V1,V3,V3,V4,V4,V1} 完全圖（每一對(duì)不同的頂點(diǎn)都有一條邊相連,n個(gè)頂點(diǎn)的完全圖共有n（n1）/2條邊）頂點(diǎn)的度：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目，有向圖中等于該頂點(diǎn)的入度與出度之和。入度——以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和出度——以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和 度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。[定理1] 圖G中所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。因?yàn)橛?jì)算頂點(diǎn)的度數(shù)時(shí)。每條邊均用到2次。[定理2] 任意一個(gè)圖一定有偶數(shù)個(gè)奇點(diǎn)。練習(xí):假設(shè)我們用d=(a1,a2,…,a5),表示無(wú)向圖G的5個(gè)頂點(diǎn)的度數(shù)，下面給出的哪（些）組d值合理（BE）。A）{5，4，4，3，1}B）{4，2，2，1，1}C）{3，3，3，2，2}D）{5，4，3，2，1}E）{2，2，2，2，2}無(wú)向圖G有16條邊，有3個(gè)4度頂點(diǎn)、4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度均小于3，則G至少____11___個(gè)頂點(diǎn)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1