發(fā)布時間：2017-10-14 13:03

  本文關(guān)鍵詞：圖上關(guān)于點不交子圖的若干結(jié)果

  更多相關(guān)文章： 不交的θ圖 完全獨立生成樹 Ore

【摘要】：圖論是一門近些年飛速發(fā)展的數(shù)學(xué)學(xué)科,它是組合數(shù)學(xué)的一個重要分支.1736年歐拉發(fā)表了圖論的首篇文章解決了著名的哥尼斯堡七橋問題.從19世紀(jì)中葉開始,圖論進入第二個發(fā)展階段,這一時期,圖論問題大量出現(xiàn),如地圖染色的四色問題、由“周游世界”游戲發(fā)展起來的哈密爾頓問題等.進入20世紀(jì),隨著計算機科學(xué)的不斷發(fā)展,圖論在各個領(lǐng)域的廣泛應(yīng)用也越來越受到數(shù)學(xué)界和其他科學(xué)界的重視.本文僅考慮簡單、無向有限圖,這些圖不包含重邊以及環(huán).設(shè)G是一個圖,x和y是G中的兩個相異的頂點,θ圖定義為三條內(nèi)不交的路的集合,這些路有相同的的起點和終點且起點和終點這兩個頂點是互異的.樹指的是連通且不含圈的無向圖,生成樹是指包含了圖G的所有頂點的圖,且該圖是樹.設(shè)T1和T2是G的兩個生成樹,如果對G的任意兩個頂點x和y,T1和T2中的x-y路是內(nèi)不交的,則稱T1和T2是G的兩個完全獨立的生成樹.G的哈密爾頓圈是指包含了G的所有頂點的圈.本文主要考慮了以下幾個問題：兩個完全獨立生成樹存在的度和條件,三個內(nèi)不交的θ圖的極值函數(shù).全文共有四章.第一章介紹了圖的基本概念及所研究問題的歷史背景和發(fā)展情況.第二章主要研究了三個內(nèi)不交的θ圖的極值函數(shù).主要結(jié)論如下：任意頂點數(shù)n≥12,邊數(shù)至少為max{「3n+79/2」,「11n-33/2」}的圖包含三個內(nèi)不交的θΟ圖.第三章主要研究了兩個完全獨立生成樹的度和條件.主要結(jié)論如下：頂點數(shù)n≥7的圖包含兩個完全獨立的生成樹,如果這個圖中的任意兩個不相鄰的頂點的度和至少為n.最后,本文的每章末尾,均提出了一些問題,以待進一步討論和研究.
【關(guān)鍵詞】：不交的θ圖 完全獨立生成樹 Ore's條件 極值函數(shù)
【學(xué)位授予單位】：寧夏大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要4-5
• ABSTRACT (英文摘要)5-7
• 主要符號對照表7-8
• 第一章 引言8-14
• 1.1 基本概念和術(shù)語8-9
• 1.2 問題的研究背景9-10
• 1.3 已有結(jié)論及本文的結(jié)果10-14
• 第二章 存在三個點不交的θ圖的極值函數(shù)14-24
• 2.1 基本概念及術(shù)語14
• 2.2 主要引理及其證明14-17
• 2.3 主要定理1.3.9的證明17-23
• 2.4 可進一步討論的問題23-24
• 第三章 兩個完全獨立生成樹存在的度和條件24-35
• 3.1 預(yù)備知識24
• 3.2 主要引理24-25
• 3.3 主要定理1.3.14的證明25-34
• 3.4 討論34-35
• 參考文獻35-37
• 致謝37-38
• 個人簡介38

【參考文獻】

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 鄒青松;圖包含指定長度的圈和泛弧問題的研究[D];山東大學(xué);2011年

，

本文編號：1031182