風何圖論中的若干問題.pdf

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

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

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

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