風(fēng)何圖論中的若干問(wèn)題.pdf

1、幾何圖論討論由于幾何關(guān)系而產(chǎn)生的圖結(jié)構(gòu)以及圖的幾何表示和相關(guān)問(wèn)題.本文研究競(jìng)爭(zhēng)圖和雙競(jìng)爭(zhēng)圖，尤其是平面點(diǎn)集的雙競(jìng)爭(zhēng)圖，以及兩個(gè)平面圖同時(shí)嵌入的交叉數(shù)問(wèn)題.
　　 第一部分是競(jìng)爭(zhēng)圖問(wèn)題.給定有向圖D=(V(D)，A(D)).它的競(jìng)爭(zhēng)圖C(D)以V(D)為頂點(diǎn)集，以{uv∈(V(D)2)：()w∈V(D)，(uw)，(uw)∈A(D))為邊集；而它的雙競(jìng)爭(zhēng)圖DC(D)以V(D)為頂點(diǎn)集，以{uv∈(V(D)2)：()w1，w2∈V(

2、D)，(uw1)，(vw1)，(w2u)，(w2v)，∈A(D)}為邊集.競(jìng)爭(zhēng)圖的概念是1968年著名生物學(xué)家Cohen在研究生態(tài)系統(tǒng)時(shí)提出的，后來(lái)衍生出雙競(jìng)爭(zhēng)圖等概念.除了在生物上的應(yīng)用，競(jìng)爭(zhēng)圖在編碼理論，噪聲信道通訊研究，無(wú)線電廣播研究及復(fù)雜經(jīng)濟(jì)與能量問(wèn)題的建模方面有廣泛的應(yīng)用.偏序集作為無(wú)圈且具有可遷性的有向圖，也可以定義其競(jìng)爭(zhēng)圖和雙競(jìng)爭(zhēng)圖.維數(shù)不超過(guò)2的偏序集以平面R2上的點(diǎn)作為頂點(diǎn)，有向弧從點(diǎn)(x1，y1)指向點(diǎn)(x2，y2)

3、當(dāng)且僅當(dāng)x1>x2且y1>y2.我們把維數(shù)不超過(guò)2的偏序集的(雙)競(jìng)爭(zhēng)圖稱為平面點(diǎn)集的(雙)競(jìng)爭(zhēng)圖.本文前四章對(duì)有向圖和偏序集的競(jìng)爭(zhēng)圖和雙競(jìng)爭(zhēng)圖，特別是對(duì)平面點(diǎn)集的競(jìng)爭(zhēng)圖和雙競(jìng)爭(zhēng)圖，進(jìn)行了討論.
　　 第一章主要講述了競(jìng)爭(zhēng)圖的研究背景和發(fā)展現(xiàn)狀.
　　 第二章首先總結(jié)了競(jìng)爭(zhēng)圖判定以及競(jìng)爭(zhēng)數(shù)的已有結(jié)果.然后給出了偏序集競(jìng)爭(zhēng)圖的刻劃，并且揭示了圖的偏序集(雙)競(jìng)爭(zhēng)數(shù)與其(雙)相交數(shù)之間的關(guān)系.
　　 第三章主要討論平

4、面點(diǎn)集的競(jìng)爭(zhēng)圖.我們證明了圖G是平面點(diǎn)集的競(jìng)爭(zhēng)圖當(dāng)且僅當(dāng)G是區(qū)間圖而且G的極大團(tuán)中至少有一半是孤立點(diǎn).這一結(jié)果回答了Cho和Kim提出的公開(kāi)問(wèn)題.
　　 第四章主要討論平面點(diǎn)集的雙競(jìng)爭(zhēng)圖.這種雙競(jìng)爭(zhēng)圖的集合我們記為().我們首先證明了()為梯形圖的真子類，這一結(jié)果推廣了Kim，Kim和Rho的結(jié)論，同時(shí)給出了判定某個(gè)圖在圖類D中的一些必要條件；然后找出D的兩個(gè)極小禁用子圖；最后討論了D與梯形圖子類及容忍圖子類之間的關(guān)系.