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

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

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