本文關鍵詞：完全偶圖的定向圖，由筆耕文化傳播整理發(fā)布。

【摘要】：設G為無向圖,V(G)為頂點集,E(G)為邊集.圖G的定向圖是把圖G的每條邊{x,y}用弧xy或yx代替,得到的有向圖(即定向圖D無二圈和環(huán)).在給無向圖定向的過程中,可使定向圖滿足各種條件,得到具有不同性質的定向圖.國內外讀者均有深入的研究,Buhler等人研究了超立方體的定向圖D,給出了滿足D中的頂點的入度或者為α或者為b的部分充分條件和必要條件.然而,本文研究了完全偶圖的定向圖D,給出了滿足D中的頂點的入度只有兩個的充要條件.本文共分四章.第一章介紹了本文的研究背景,研究現(xiàn)狀,研究內容及意義和主要結論.國內外讀者在定向圖滿足強連通性,強直徑,入度,獨立弧數等方面進行了研究.本文對完全偶圖的定向圖在入度方面進行了研究.第二章介紹了本文將要用到的有關圖的一些基本概念和術語.第三章介紹了本文的主要研究內容,給出了完全偶圖的定向圖的頂點的入度只有兩個的充分必要條件.用[α,b]n表示把Kn,n定向為有向圖D,使得D中頂點的入度或者是α或者是b的一個圖類,并稱kn,n是[α,b]n可實現(xiàn)的,簡稱[α,b]。是可實現(xiàn)的.本文得到的主要結論如下：設n為正整數,α,b∈{0,1,2,…,n},若Kn,n是[a,b]n可實現(xiàn)的當且僅當存在正整數s和t,滿足下面兩個方程：第三章第1節(jié)中,本文證明了結論中的必要條件第2節(jié)中,證明了結論中的充分條件,其中用到了算法思想和分類討論的思想.第四章介紹了本文的創(chuàng)新之處,研究結論和有待進一步研究的問題.本文的創(chuàng)新之處在于,對完全偶圖后得到的定向圖的頂點的入度不是多個,而是只有兩個,使得到的圖類簡單明了.以后,我們還可以研究其他無向圖的定向圖,如星圖,k元n方體等.
【關鍵詞】：完全偶圖 定向 入度 算法
【學位授予單位】：山西大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 中文摘要6-8
• Abstract8-10
• 第一章 引言10-13
• 1.1 研究背景及研究現(xiàn)狀10-11
• 1.2 研究內容及意義11-12
• 1.3 本文的主要結論12-13
• 第二章 預備知識13-15
• 第三章 完全偶圖的定向圖15-33
• 3.1 準備工作及必要條件的證明15-17
• 3.2 充分條件的算法證明17-31
• 3.3 主要結論31-33
• 第四章 總結與展望33-34
• 4.1 主要結論33
• 4.2 本文的創(chuàng)新之處33
• 4.3 有待進一步研究的問題33-34
• 參考文獻34-37
• 攻讀學位期間取得的研究成果37-38
• 致謝38-39
• 個人簡況及聯(lián)系方式39-40
• 承諾書40-41

【共引文獻】

中國碩士學位論文全文數據庫 前1條

1 武艷艷;幾類有向圖的強直徑和強半徑[D];山西大學;2013年

  本文關鍵詞：完全偶圖的定向圖，由筆耕文化傳播整理發(fā)布。

，

本文編號：471480