發(fā)布時間：2020-05-20 06:40

【摘要】：本文所涉及的圖都是簡單的無向連通圖.對任意的點v∈V(G),G|v表示圖G的一個部分控制圖,即G中頂點v已經被控制.設圖G的控制數與博弈控制數分別是γ(G)與γ_g(G).若圖G滿足公式 γ_g(G)= 2γ(G)-1,則這類圖是γ_g-極大圖.若對任意的點v∈ V(G)有γ_g(G)=γ(G|v),則圖G是控制博弈穩(wěn)定的(簡稱γ_g-穩(wěn)定的);若對任意的邊e∈E(G)有γ_g(G-eγ_g(G),則圖G是控制博弈邊-臨界的(簡稱γ_g-邊-臨界的).若G是博弈控制數為k的γ_g-穩(wěn)定圖(或γ_g-邊-臨界圖),則G是k-γ_g-穩(wěn)定圖(或k-γ_g-邊-臨界圖).本文的第一章簡單介紹了文章所涉及的圖的一些基本概念、符號、相關研究背景以及所需要的相關定義.第二章首先在具有支撐控制集的圖中,給出一大類γ_g極大圖.然后在似星樹,即有且只有一個點的度數大于等于3的樹中,刻畫了所有γ_g-極大圖.第三章首先刻畫了當k∈｛1,2｝時的k-γ_g-穩(wěn)定圖,3-γ_g-穩(wěn)定樹,并證明Kneser圖K(n,2)是k-γ_g-穩(wěn)定的,其中n = 5時k= 5;n≥6時k = 3,并確定了所有γ_g-穩(wěn)定的路與圈.其次證明了對任意的正整數k,存在一個k γ_g-穩(wěn)定圖.文章最后描述k∈{1,2 時的所有k-γ_g-邊-臨界圖以及一個3-γ_g-邊-臨界圖的例子,并給出兩個判斷非-γ_g-邊-臨界圖的充分條件.第四章對本論文進行了系統(tǒng)性的總結,并列舉了一些論文中未能解決的問題.
【圖文】：

線段來表示這些事物之間所具有的特定關系.眾所周知，圖論起源于非常經典的柯尼斯堡七橋問題：在柯尼斯堡的普萊格爾河上有七座橋將河中的島與河連接起來，問能否從四塊陸地中的任何一塊開始，通過每一座橋正好一次，最后回到起點？1736 年瑞士數學家歐拉最先用圖論的思想解決了這個問題，由此圖論便與幾何拓撲學一起誕生了，而歐拉也因此被稱為是圖論的創(chuàng)始人.到目前為止，，圖論已經給世人呈現出大量有趣的問題，其中的一個焦點性問題就是圖的染色問題.它起源于著名的“四色猜想”，即用四種顏色就可以對任意一張地圖進行染色.1879 年 Kempe 第一個給出這個猜想的證明，但是后來被證實他的證明方法有誤，直到 1976 年美國數學家 Appel與 Haken 在計算機的幫助下證明了四色猜想是正確的，后來這個猜想被改成了著名的“四色定理”.此外天文學家哈密頓提出了一個非常有趣的問題——哈密頓回路問題，即在一個有多個城市的地圖網絡中，尋找一條從給定起點到給定終點且沿途恰好經過所有其它城市各一次的路.這個問題便形成了大家現在熟知的哈密頓圈 1 .1936年匈牙利的數學家哥尼格發(fā)表了《有限圖與無限圖的理論》，這是第一本關于圖論的著作，也是圖論成為一門獨立學科的標志.圖 1.1 為柯尼斯堡七橋問題的簡化圖及其在圖論中反映的圖形.

g-臨界樹
【學位授予單位】：南京航空航天大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：O157.5;O225

【相似文獻】

相關期刊論文 前10條

1 李中華;吳寶音都仍;安新慧;劉鳳霞;;列表雙臨界圖（英文）[J];新疆大學學報(自然科學版);2018年01期

2 劉慧清;陸玫;章舜哲;;關于3-點臨界圖的一個猜想的證明[J];中國科學:數學;2013年05期

3 林育青;;邊臨界圖[J];南方職業(yè)教育學刊;2011年03期

4 徐蘭;許英;張麗;;獨立控制雙臨界圖(英文)[J];山東大學學報(理學版);2010年10期

5 鄧婷;王春香;;控制圓點臨界圖的若干性質[J];華中師范大學學報(自然科學版);2009年04期

6 江t

本文編號：2672225