本文關鍵詞：兩類有向圖的匹配數(shù)研究

  更多相關文章： 復雜網(wǎng)絡 有向樹 有向三角形樹 匹配 Hosoya指標

【摘要】：隨著計算設備的日益強大和迅猛發(fā)展的Internet,人們能夠收集和處理種類不同且規(guī)模巨大的實際網(wǎng)絡數(shù)據(jù).并且希望可以通過一些措施對復雜網(wǎng)絡進行有效的控制,使其朝著對人們的生產(chǎn)、生活有利的方向發(fā)展.劉和Barabasi等人提出:有向網(wǎng)絡的可控節(jié)點數(shù)等于有向網(wǎng)絡的頂點數(shù)減去最大匹配包含的邊數(shù).說明有向網(wǎng)絡的可控性與有向網(wǎng)絡的匹配數(shù)有著密切的聯(lián)系.因此,研究有向網(wǎng)絡的所有匹配數(shù)目具有一定的應用意義.本文主要研究有向樹及一類有向三角形樹的所有匹配數(shù)的計數(shù)問題和極值問題.首先,介紹復雜網(wǎng)絡的研究背景、復雜網(wǎng)絡可控性的研究背景、匹配數(shù)的發(fā)展背景.第二章介紹了一些無向圖、有向圖及有向樹的基本知識.第三章給出了含n個節(jié)點有向樹的匹配數(shù)的計算方法、表達式及其相關性質(zhì),確定了具有n個節(jié)點的有向樹匹配數(shù)的上下界和達到上下界的有向樹.第四章研究了一類有向三角形樹匹配數(shù)的計數(shù)問題,給出含n個三角形的有向三角形樹的匹配數(shù)的計算方法,給出有向三角形樹匹配數(shù)的上下界和相應的結構.最后一章對本文進行了總結,給出了一些有待解決的問題.
【關鍵詞】：復雜網(wǎng)絡 有向樹 有向三角形樹 匹配 Hosoya指標
【學位授予單位】：青海師范大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 中文摘要3-4
• 英文摘要4-7
• 第一 章引言7-15
• 1.1 復雜網(wǎng)絡的研究背景7-10
• 1.2 復雜網(wǎng)絡可控性的研究背景10-13
• 1.3 匹配數(shù)的研究背景13-14
• 1.4 本文的主要研究工作14-15
• 第二 章基本知識15-18
• 2.1 無向圖的基本概念15
• 2.2 有向圖的基本概念15-18
• 第三 章有向樹的匹配數(shù)18-25
• 3.1 有向樹的基本定義18-19
• 3.2 有向樹匹配數(shù)的計算方法19-23
• 3.3 有向樹匹配數(shù)的算法23-24
• 3.4 小結24-25
• 第四 章一類有向三角形樹的匹配數(shù)25-34
• 4.1 有向三角形樹的基本定義25-26
• 4.2 一類有向三角形樹匹配數(shù)的計算方法26-32
• 4.3 有向三角形樹匹配數(shù)的算法32-33
• 4.4 小結33-34
• 第五 章總結與展望34-36
• 5.1 總結34
• 5.2 有待研究的問題34-36
• 參考文獻36-39
• 致謝39-40
• 個人簡介40
• 學習經(jīng)歷40
• 研究成果40-41
• 研究生期間參與的項目和獲得的科研成果41

，

本文編號：617871