圖的邊覆蓋染色.pdf

1、山東大學(xué)博士學(xué)位論文圖的邊覆蓋染色姓名：苗蓮英申請學(xué)位級別：博士專業(yè)：運籌學(xué)與控制論指導(dǎo)教師：周鴻興劉桂真2000.3.1第一章基本概念，圖的邊染色理論的歷史本章第一節(jié)介紹一些常用的圖論術(shù)語，其它的圖論術(shù)語在必要時再予以闡述。第二節(jié)介紹圖的邊染色理論的歷史及發(fā)展?fàn)顩r。第11節(jié)基本概念若s是一個有限集，我們用㈣表示s中元索的個數(shù)。對于實數(shù)。，用㈦或M表示不小于z的最小整數(shù)，用H表示不大于z的最大整數(shù)。一個圖G是一個有序?qū)?y(G)，E(G

2、))，其中y(G)是一個有限集合，E(G)是礦(G)的不同元素的無序?qū)Φ募?。y(G)的元素叫圖G的頂點，E(G)的元素叫圖G的邊。y(G)和E(G)分別稱為G的點集和邊集。圖G的階是y(G)的元素個數(shù)Iy(G)1，圖G的邊數(shù)是E(G)的元素個數(shù)lE(G)l。我們通常用n表示G的階，用m表示G的邊數(shù)。對于圖G的頂點t‘和”，若邊e=t‘u∈E，則稱u，v相鄰，u和”互為鄰點，且稱u一是e的端點，“，v分別與e關(guān)聯(lián)。若G的邊e和，有一個公

3、共的端點，則稱e和，相鄰。頂點u的相鄰點的全體叫做u的鄰域，記為ⅣG(u)。頂點u的度為fⅣG(u)，記為dG(u)。圖G中度數(shù)為女的頂點稱為t一度點。G的頂點度中最大者稱為G的最大度，記為△(G)最小者稱為最小度，記為6(G)。度數(shù)為零的頂點稱為孤立點。度數(shù)為l的點稱為懸掛點，與懸掛點相關(guān)聯(lián)的邊稱為懸掛邊。G的度數(shù)最大的點稱為主頂點，其余稱為次頂點。在不會產(chǎn)生混淆的情況下，y(G)，IE(G)，ⅣG(u)，dG(u)，△(G)和d(G