含某些指定邊的生成樹的生成與計數(shù).pdf

1、以經(jīng)典的生成樹的生成與計數(shù)問題為研究背景，運用圖的矩陣表示和破圈理論研究了連通圖含某些指定邊的生成樹的生成與計數(shù)問題。
　　第一，提出并討論了連通圖含某些指定邊的生成樹的環(huán)和矩陣生成法.在給出環(huán)補關聯(lián)矩陣與環(huán)和矩陣等定義的基礎上，給出并證明了連通圖含某些指定邊的生成樹的生成方法——環(huán)和矩陣法.
　　第二，介紹了一種求圖的含某些指定邊的生成樹的按類生成法.首先選取圖的含所有指定邊的任意一棵參考生成樹，利用其它含所有指定邊的生成

2、樹與參考生成樹的距離，把除參考生成樹之外的所有含所有指定邊的生成樹最多分成d類.然后給出并證明了這種分類生成樹與基本可破圈及基本可破圈的環(huán)和的關系.從而證明了這種按類生成法能夠生成圖的含所有指定邊的全部互異的生成樹。
　　第三，討論了連通圖含某些指定邊或含指定邊中一條且僅一條邊的全部生成樹的計數(shù)問題.給出了一個連通圖含k-爪或含k-爪中一條且僅一條邊的全部生成樹的數(shù)目公式.并例示了應用公式求一個連通圖含k-爪或含k-爪中一條且僅一