樹多項式是一類特殊的圖。沒有圈的連通圖稱為樹。若T是圖G的一支撐子圖，且是樹，則稱T的對於G的補圖T為上樹，而稱T為G的支撐樹。G的上樹T的每一條邊都稱為T的弦。每一條弦與T恰形成一個圈，稱這種圈為基本圈。G的支撐樹T的每一條邊稱為T的權。
基本介紹
- 中文名：樹多項式
- 領域：數學
- 學科：圖論
- 性質：一種特殊的圖
概念,樹,圖,圖論,
概念
樹多項式是一類特殊的圖。沒有圈的連通圖稱為樹。若T是圖G的一支撐子圖，且是樹，則稱T的對於G的補圖T為上樹，而稱T為G的支撐樹。G的上樹T的每一條邊都稱為T的弦。每一條弦與T恰形成一個圈，稱這種圈為基本圈。G的支撐樹T的每一條邊稱為T的權。每一條權與T恰形成一個上圈，稱之為基本上圈。沒有圈的圖稱為森或林。自然，連通的森就是樹。以一個連通圖G的各個支撐樹的所有邊的積為項，G的樹多項式(一個形式多項式)就是所有這些項的和，常記為P(T(G))。凱萊公式是計算帶號完全圖的不同帶號樹的數目的公式：n階帶號完全圖K，的不同帶號支撐樹的數目為n-zn一個帶號圖中不同的帶號支撐樹的數目稱為這個圖的複雜度。設T是一個樹，v是T上的一個節點。T上以v為懸掛點的邊數最多的子樹的階稱為T上v的點權。以v為懸掛點的T的極大子樹，即這樣的子樹，它不是任何其他子樹的真子樹，稱它為v處的枝。可見，v的點權就是以v為懸掛點的最大子樹的階數，或者說v處含邊數最多的枝的階。連通圖G的樹圖是從G派生出的一個圖：G的每一支撐樹作為一個節點，兩個節點有一條邊相連，若且唯若它們所對應的支撐樹各有一條邊不是另一個樹的邊。
樹
樹是連通的無迴路的無向圖。樹中度數為1的點稱為樹葉，度數大於1的點稱為分支點。無迴路的無向圖稱為(森)林，它的每個連通分支都是樹。
定理：任意n(≥2)點的樹至少有兩片樹葉。
定理：設圖T有n個點，m條邊，則以下幾個條件互相等價：
①T連通無迴路，即T是樹；
②T無迴路，且m=n-1；
③T連通，且m=n-1；
④T無迴路，但任意增加一邊，則得到一條且僅一條迴路；
⑤T連通，但刪去任一邊後不連通；
⑥T的每一對點之間有一條且僅一條路。
這裡，條件④指出樹是邊數最多的無迴路的圖；而⑤指出樹是邊數最少的連通圖。
若圖G= 〈V，E〉的生成子圖T是樹，則T稱為G的生成樹。圖G有生成樹若且唯若G是連通圖。
利用“破迴路法”可求給定連通圖的生成樹。這僅需每次刪去一條迴路上的一條邊(保留端點)，直到不再含有迴路為止，就得到一棵生成樹。
利用“破迴路法”可求給定連通圖的生成樹。只需從任一邊開始，每次增加一邊，但要求加進來的邊與已選好的邊不構成迴路，直到包含所有點為止。
對連通賦權圖G來說，若T是生成樹，T的所有邊的權的和，稱為T的樹權，記做W (T).在G中的樹權最小的生成樹，稱為G的最小生成樹。
例如，點表示城市，邊表示城市間的電話線，邊的權為電路的造價。則選取最小生成樹有重要經濟意義。用克魯斯卡爾算法產生最小生成樹：
①選取G的最小權邊e1(有多條時，任選一條)；
②設已選好e1，e2，…，ei，在G中選取不同於e1，e2，…，ei的邊ei+1，使得e1，e2，…，ei，ei+1不構成迴路，並且ei+1是滿足此條件的最小權邊(有多條時，任選一條)；
③i=n-1 (n為G的點數)時，算法終止。
圖
圖是圖論的研究對象。一個圖是一個集合上的一種二元關係。這個集合的元素稱為圖的節點，若兩節點之間有這種確定的二元關係，則稱有一條邊連這兩個節點。一個圖的節點的數目稱為這個圖的階；圖的邊的數目稱為它的度。在文獻中，總是將一般的圖記為G=(V，E)，其中，V=V(G)和E=E(G)分別表示G的節點集和邊集。
若有一條邊連一個圖的某兩個節點，則稱這兩個節點相鄰，並稱這兩個節點為這條邊的端點。若某一節點是某一條邊的端點，則稱這個節點和這條邊關聯。若兩條邊和同一節點關聯，則稱這兩條邊相鄰，兩個端點是同一個節點的邊稱為環。若某條邊的兩個端點不是同一個節點，且只有一條邊連這兩個節點，則稱這條邊為桿。
只有一個節點而沒有邊的圖稱為平凡圖;沒有邊的圖稱為孤立圖。以某兩節點為端點的邊可能不止一條，這時稱連這兩個節點的邊為重邊。既可以有環，也可以有重邊的圖稱為準圖；沒有環而可能有重邊的圖稱為帶重圖；沒有重邊而可能有環的圖稱為帶環圖；既沒有重邊也沒有環的圖稱為簡單圖。若一個圖的階是有限的，則稱這個圖為有限圖，否則稱這個圖為無限圖。每兩個節點都相鄰的簡單圖稱為完全圖。若一個n階圖的節點用1，2，…，n來代表，則稱它為標定圖。若在圖的每一條邊上賦以一個實數或者對於每個節點賦以一個實數，則稱它為賦權圖。
圖論
近年來比較活躍的數學分支之一。圖論是研究各種圖的性質和特徵的一門理論，主要包括圖與子圖、圖的連通性、可平面性、正則圖、樹、著色問題、圖的矩陣以及網路等內容。圖論的發展已有200多年的歷史。早在18世紀中葉就已出現有關圖的文字記載。這時的圖論尚處於萌芽階段，多數問題是圍繞著遊戲而產生的，最有代表性的是著名的哥尼斯堡七橋問題(相當於我國的一筆畫問題)。19世紀中葉到20世紀中葉，圖論問題大量出現，諸如哈密爾頓“繞行世界”問題，關於地圖著色的四色問題以及與之有關聯的圖的可平面性等等。在這個階段，也出現了以圖為工具去解決其他領域中一些問題的成果，例如，凱萊把圖論套用到有機化學中關於同分異構物的計數問題，克希霍夫套用樹研究電網路的分析問題等等。20世紀中葉以後，由於生產管理、軍事、交通運輸、計算機網路等方面提出的實際問題的需要，特別是許多離散性問題的出現，以及由於有了大型超高速計算機，而使大規模問題的求解成為可能，圖論及其套用的研究得到了飛速發展。這個階段的開創性工作是以福特和福克遜建立的網路流理論為代表的。圖論和線性規劃、動態規劃等最佳化理論和方法的相互滲透，促進了組合最最佳化理論和算法的研究以及圖論對實際問題的套用，與此同時也豐富了圖論的內容，使圖論的發展更加充滿活力。
