兩類有向圖的匹配數(shù)研究.pdf

1、隨著計算設(shè)備的日益強大和迅猛發(fā)展的Internet,人們能夠收集和處理種類不同且規(guī)模巨大的實際網(wǎng)絡(luò)數(shù)據(jù).并且希望可以通過一些措施對復(fù)雜網(wǎng)絡(luò)進行有效的控制,使其朝著對人們的生產(chǎn)、生活有利的方向發(fā)展.劉和Barabasi等人提出:有向網(wǎng)絡(luò)的可控節(jié)點數(shù)等于有向網(wǎng)絡(luò)的頂點數(shù)減去最大匹配包含的邊數(shù).說明有向網(wǎng)絡(luò)的可控性與有向網(wǎng)絡(luò)的匹配數(shù)有著密切的聯(lián)系.因此,研究有向網(wǎng)絡(luò)的所有匹配數(shù)目具有一定的應(yīng)用意義.
　　本文主要研究有向樹及一類有向三角

2、形樹的所有匹配數(shù)的計數(shù)問題和極值問題.首先,介紹復(fù)雜網(wǎng)絡(luò)的研究背景、復(fù)雜網(wǎng)絡(luò)可控性的研究背景、匹配數(shù)的發(fā)展背景.第二章介紹了一些無向圖、有向圖及有向樹的基本知識.第三章給出了含n個節(jié)點有向樹的匹配數(shù)的計算方法、表達式及其相關(guān)性質(zhì),確定了具有n個節(jié)點的有向樹匹配數(shù)的上下界和達到上下界的有向樹.第四章研究了一類有向三角形樹匹配數(shù)的計數(shù)問題,給出含n個三角形的有向三角形樹的匹配數(shù)的計算方法，給出有向三角形樹匹配數(shù)的上下界和相應(yīng)的結(jié)構(gòu).最后一章