本文選題：區(qū)間邊著色 + 收縮圖　； 參考：《新疆大學(xué)》2017年碩士論文

【摘要】：圖論作為數(shù)學(xué)的一個(gè)分支,近年來得到了較快發(fā)展和廣泛應(yīng)用,已廣泛應(yīng)用于運(yùn)籌學(xué),控制論,信息論和計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域.一般說來,圖的著色問題最早起源于著名的”四色問題”.由于圖的著色問題反映了廣泛而深刻的實(shí)際背景,它的研究帶動了整個(gè)圖論的發(fā)展.如今圖著色理論被廣泛應(yīng)用于化學(xué)品的貯藏,考試日程和安排會議等許多實(shí)際問題上.圖G的一個(gè)用了顏色1,2,...,t的邊著色稱為區(qū)間t-著色,如果所有t種顏色都被用到,并且關(guān)聯(lián)于G的同一個(gè)頂點(diǎn)的邊上的顏色是各不相同的且這些顏色構(gòu)成了一個(gè)連續(xù)的整數(shù)區(qū)間.G稱作是可區(qū)間著色的,如果對某個(gè)正整數(shù)t,G有一個(gè)區(qū)間t-著色.所有可區(qū)間著色的圖構(gòu)成的集合記作N.對圖G∈N,使得G有一個(gè)區(qū)間t-著色的t的最小值和最大值分別記作w(G)和W(G).本文中,我們給出了圖的區(qū)間著色的收縮圖方法.利用此方法我們對雙圈圖G∈N,證明了w(G)=?(G)或?(G)+1,并且完全確定了w(G)=?(G)及w(G)=?(G)+1的雙圈圖類.全文共分為三章.第一章首先介紹了圖著色的研究背景及相關(guān)應(yīng)用,以及圖的區(qū)間邊著色的刻畫問題;其次介紹了基本概念及術(shù)語;最后列出了圖的區(qū)間邊著色研究的一些已有結(jié)果.第二章給出了收縮圖方法.第三章主要利用前面的方法給出了雙圈圖區(qū)間邊著色的下界.第三章分為三個(gè)小節(jié).第一節(jié)中給出了雙圈圖G∈β∞的區(qū)間邊著色的下界w(G);第二節(jié)中給出了雙圈圖G∈βθ的區(qū)間邊著色的下界w(G);第三節(jié)中給出了雙圈圖G∈β的區(qū)間著色的下界w(G).
[Abstract]:As a branch of mathematics, graph theory has been rapidly developed and widely used in recent years. It has been widely used in the fields of operational research, cybernetics, information theory and computer science. Generally speaking, the coloring problem of graphs originated from the famous four-color problem. Because the coloring problem of graphs reflects a wide and profound practical background, its research has driven the development of the whole graph theory. Graph coloring theory is widely used in many practical problems such as chemical storage, examination schedule and meeting scheduling. One of the edges of the graph G is called interval t- coloring, if all the t colors are used. And the colors on the edges of the same vertex associated with G are different and these colors form a continuous integer interval. G is called interval colored if there is an interval t-coloring for a positive integer t G. The set of all interval-coloring graphs is denoted as N. For a graph G 鈭，

本文編號：1952645