《離散數(shù)學(xué)》圖論中的各種名詞的解釋表格整理版

1、第一章命題邏輯原式P-Q逆換式Q-P反換式PQ逆反式QP第七章圖論孤立結(jié)點(diǎn)不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)零圖僅由孤立結(jié)點(diǎn)構(gòu)成的圖平凡圖僅由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖鄰接邊關(guān)聯(lián)于同一結(jié)點(diǎn)的兩條邊自回路/環(huán)關(guān)聯(lián)于同一結(jié)點(diǎn)的一條邊度數(shù)與節(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)，成為結(jié)點(diǎn)的度數(shù)多重圖含有平行邊的任何一個(gè)圖簡(jiǎn)單圖由無向圖衍生出,一個(gè)結(jié)點(diǎn)對(duì)有且僅有一條邊。完全圖Kp簡(jiǎn)單圖G二V,E，每一對(duì)結(jié)點(diǎn)間都有邊相連Kn有n個(gè)結(jié)點(diǎn)的無向完全圖補(bǔ)圖給定一個(gè)圖G,由G中所有結(jié)點(diǎn)和所有能使G成為完全圖的添加邊組成的圖，稱為G的相對(duì)于完全圖的補(bǔ)圖。生成子圖若G的子圖包含G的所有結(jié)點(diǎn)，該子圖成為G的生成子圖。相對(duì)補(bǔ)圖設(shè)G=V,E是G=V,E的子圖，

2、若給定另外一個(gè)圖G二V,E使得E二E-E：且V中僅包含E的邊所關(guān)聯(lián)的結(jié)點(diǎn)。則稱G是子圖G的相對(duì)于圖G的補(bǔ)圖。同構(gòu)設(shè)圖G=V,E及圖G-V,E,如果存在對(duì)應(yīng)的映射g：Vi一*且e=(Vj,Vj)(或*“)是G的一條邊，當(dāng)且僅當(dāng)e=(g(vi),g(vj)(或g(vi),g(vj)是G的一條邊，則稱G與G同構(gòu)，記作GG路vOe1v1e2envn稱作聯(lián)結(jié)vo到vn的路回路路中,vO=vn時(shí)，就稱作回路跡/簡(jiǎn)單路徑條路中所有的邊e1,e2,en均不同通路/基本路徑條路中所有的結(jié)點(diǎn)v0,v1,vn均不相同圈閉的通路;除vO=vn外，其余節(jié)點(diǎn)均不相同連通兩節(jié)點(diǎn)之間存在條路連通圖圖G中只有一個(gè)分支點(diǎn)割集設(shè)無

3、向圖G二V,E為連通圖，若有點(diǎn)集V1uV,使圖G刪除了V1的所有結(jié)點(diǎn)后，所得的子集是不連通圖，而刪除了V1的任意真子集后，所得到的圖仍是連通圖，則稱V1是G的一個(gè)點(diǎn)割集。割點(diǎn)若某一個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集，則稱該結(jié)點(diǎn)為割點(diǎn)邊割集設(shè)無向圖G二V,E為連通圖，若有邊集E1uE,使圖G刪除了E1的所有邊后，所得的子集是不連通圖，而刪除了E1的任意真子集后,所得到的圖是不連通圖，則稱E1是G的一個(gè)邊割集。邊/橋某一個(gè)構(gòu)成一個(gè)邊割集的邊k(G)/(點(diǎn))連通度min|V1|V1是G的一個(gè)點(diǎn)割集（平凡圖）久（G）連通度（非平凡圖）min|E1|E1是G的邊割集單側(cè)連通有向圖:任何一對(duì)結(jié)點(diǎn)間，至少有一個(gè)結(jié)點(diǎn)到另一

4、個(gè)結(jié)點(diǎn)是可達(dá)的強(qiáng)連通有向圖:任何一對(duì)結(jié)點(diǎn)，兩者之間是相互可達(dá)的弱連通有向圖:看成無向圖后圖是連通的強(qiáng)分圖有向圖:具有強(qiáng)連通性質(zhì)的最大子圖單側(cè)分圖有向圖:具有單側(cè)連通性質(zhì)的最大子圖弱分圖具有弱連通性質(zhì)的最大分圖連接矩陣書P288adj鄰接nadj不鄰接可達(dá)性矩陣書P291完全關(guān)聯(lián)矩陣無向圖:P294歐拉圖給定孤立結(jié)點(diǎn)圖G,若存在一條路，經(jīng)過圖中每邊一次且僅一次。歐拉回路給定孤立結(jié)點(diǎn)圖G,若存在一條回路，經(jīng)過圖中每邊一次且僅一次。單向歐拉路（回路）有向圖G通過圖中每邊一次且僅一次的一條單向路（回路）漢密爾頓路給定圖G,若存在一條路經(jīng)過圖中的每個(gè)結(jié)點(diǎn)恰好一次漢密爾頓回路若存在一條回路，經(jīng)過圖中的每個(gè)

5、結(jié)點(diǎn)恰好一次漢密爾頓圖具有漢密爾頓回路的圖W(G-S)G-S中連通分支數(shù)平面圖設(shè)G-V,E是個(gè)無向圖，如果能夠把G的所有結(jié)點(diǎn)和邊畫在平面上，且使得任何兩條邊除了端點(diǎn)外沒有其他的父點(diǎn)。面設(shè)G是一連通平面圖.由圖中的邊所包圍的區(qū)域.在區(qū)域內(nèi)不包含圖的結(jié)點(diǎn)，也不包含圖的邊，這樣的區(qū)域稱為G的一個(gè)面。邊界包圍一個(gè)面所構(gòu)成的回路稱為這個(gè)面的邊界無限面不受約束的面面的次數(shù)deg（r）面的邊界的回路長(zhǎng)度ViVj=Vi,j有向圖：Vi,j=Vi+Vj無向圖：Vij=(Vi+Vj)%2閉包C(G)給定圖G二V,E有n個(gè)結(jié)點(diǎn)，若將圖G中度數(shù)之和至少是n的非鄰接節(jié)點(diǎn)連接起來得圖G,對(duì)圖G重復(fù)上述步驟，直到不再有這樣

6、的結(jié)點(diǎn)對(duì)存在為止，所得到的圖，稱為是原圖G的閉包。在2讀節(jié)點(diǎn)內(nèi)同構(gòu)給定兩個(gè)圖G1和G乙如果它們是同構(gòu)的，或者通過反復(fù)插入或除去度數(shù)為2的結(jié)點(diǎn)后，使G1與G2同構(gòu)，則稱該兩圖是在2讀結(jié)點(diǎn)內(nèi)同構(gòu)的。K3,32步圖。上下頂點(diǎn)分別為3.對(duì)偶圖書P318樹個(gè)連通且無回路的無向圖森林的每個(gè)連通分圖無回路且e=v-1連通且e=v-1無回路但增加一條新邊，得到一個(gè)且僅有一個(gè)回路連通，但刪去任一邊后便不連通每一對(duì)結(jié)點(diǎn)之間有一條且僅有一條路樹葉度數(shù)為1的結(jié)點(diǎn)分至點(diǎn)/內(nèi)點(diǎn)度數(shù)大于1的結(jié)點(diǎn)森林一個(gè)無回路的無向圖生成樹若圖G的生成子圖是一棵樹，則稱該樹為G的生成樹樹枝設(shè)圖G有一棵生成樹T,則T中的邊稱作樹枝弦圖G的不在牛成樹的邊補(bǔ)所有弦的集合稱為生成樹T的補(bǔ)樹權(quán)C(T)T的所有邊權(quán)的和最小生成樹在圖G的所有生成樹中，樹權(quán)最小的那棵生成樹有向樹個(gè)有向圖在不考慮邊的方向時(shí)是顆樹根樹棵有向樹，如果恰有一個(gè)結(jié)點(diǎn)的入度為0,其余所有的入度都為1根根樹中入度為0的結(jié)點(diǎn)葉根樹中出度為0的結(jié)點(diǎn)分枝點(diǎn)/內(nèi)點(diǎn)出度不為0的結(jié)點(diǎn)m叉樹在根樹中，若每一個(gè)結(jié)點(diǎn)的出度小于或等于m,則稱這棵樹為m叉樹完全m叉樹如果每一個(gè)結(jié)點(diǎn)的出度恰好等于m或0正則m叉樹完全m叉樹所有樹葉層數(shù)相同二叉樹這則m叉樹當(dāng)m=2時(shí)通路長(zhǎng)度個(gè)結(jié)點(diǎn)的通路長(zhǎng)度，就是從樹根到此結(jié)點(diǎn)的通路中的邊數(shù)內(nèi)部通路長(zhǎng)度分枝點(diǎn)的通路長(zhǎng)度外部通路長(zhǎng)度樹葉的通路長(zhǎng)度帶權(quán)