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

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

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