離散數(shù)學(xué)-圖論基礎(chǔ)復(fù)習(xí)

定理1： d(v1)+d(v2)+....d(vn)=2m.
各頂點(diǎn)上邊數(shù)之和==2*圖的邊數(shù)

推論 任何圖(無(wú)向的或有向的)中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)。

定理2：有向圖中:d+(V1)+...d+(Vn)=d-(V1)+...d(Vn)=m.
所有頂點(diǎn)出度之和=所有頂點(diǎn)入度之和=圖邊數(shù)

割點(diǎn)定義：設(shè)無(wú)向圖中，存在頂點(diǎn)集V’,使G刪除V’（將V’中頂點(diǎn)及其關(guān)聯(lián)的邊都刪除）后，所得子圖G-V’的連通分支數(shù)與G的連通分支數(shù)滿足p(G-V’)>p(G),而刪除V’的任何真子集V’’后，p(G-V’’)=p(G),則稱V’為G的一個(gè)點(diǎn)割集。若點(diǎn)割集中只有一個(gè)頂點(diǎn)v，則稱v為割點(diǎn)。

邊割集定義： 若存在邊集子集E’,使G刪除E’(將E’中的邊從G中全部刪除)后，所得子集的連同分支數(shù)與G的連通分支數(shù)滿足p(G-E’’)=p(G),則稱E’是G的一個(gè)邊割集。若邊割集中只有一條邊e,則稱e為割邊或橋。http://www.ardmore-hotel.com/

【離散數(shù)學(xué)-圖論基礎(chǔ)復(fù)習(xí)】相關(guān)文章：

中考語(yǔ)文基礎(chǔ)知識(shí)復(fù)習(xí)試題08-08

《公共基礎(chǔ)知識(shí)》復(fù)習(xí)資料（經(jīng)濟(jì)術(shù)語(yǔ)）03-20

2015公共基礎(chǔ)知識(shí)復(fù)習(xí)資料（4）12-31

2015公共基礎(chǔ)知識(shí)復(fù)習(xí)資料（5）03-26

2015公共基礎(chǔ)知識(shí)復(fù)習(xí)資料（6）03-26

2016電氣工程師考試《專業(yè)基礎(chǔ)》知識(shí)復(fù)習(xí)考點(diǎn)07-20

二年級(jí)下冊(cè)期末基礎(chǔ)知識(shí)復(fù)習(xí)試題07-16

2016自學(xué)考試計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)基礎(chǔ)復(fù)習(xí)題07-23

2017年成人高考《生態(tài)學(xué)基礎(chǔ)》復(fù)習(xí)試題及答案08-09

打好基礎(chǔ)的名言01-10