確向術

確向術(orientation defined method)是求圖上支撐樹的一種方法，其主旨在於確定一個選邊的先後的原則，使得依此原則每步之前所選出的邊均形成一個樹。例如，深探，其選邊原則為：每到一節點優先選一條其另一端點不與已選出的邊關聯的邊。

基本介紹

• 中文名：確向術
• 外文名：orientation defined method
• 所屬學科：數學（圖論）
• 簡介：求圖上支撐樹的一種方法

基本介紹

確向術的具體過程如下：首先，選擇一個頂點，標它為0，作為根;在所有與0關聯的邊中任取一邊並將它的另一端標為1;每到一個頂點在下面的兩個措施中選擇一個：

1.若這個頂點的所有未取的關聯邊中有一條邊，它的另一個端點尚未標號，則取這條邊並將它的另一端點標以在0，1，2，…，n-1(其中n為圖的階)中未用過數字的最小者。

2.若這個頂點的關聯邊都用過了，或者說它的每一未取關聯邊的另一端均已標號，則沿著過來的邊，回到它的另一端，直到不能進行為止。

這樣得到的就是一棵支撐樹，稱為深探樹、廣探。

確向術的選邊原則

確向術的選邊原則為：每到一個節點選將與此節點關聯但另一端不與已選過的邊關聯的邊，選完再回到此節點處第一次取的邊的另一端點，按此原則繼續這一過程。對於一個圖的任何一個平面浸入，可以有左(右)探，即在每個節點處選擇向左(右)旋第一次遇到的另一端不與任何已選的邊關聯的邊，事實上，左探和右探早在1882年由法國的特萊謀(Tremaux)發表在呂卡(F.-É.-A.Lucas)關於數學遊戲的書的第一卷中，最簡單也是最好的說法為塔里(G.Tarry)於1895年提出的，即人們常稱的迷宮法。

相關分析

支撐樹(spanning tree)亦稱生成樹，是一類特殊的樹。圖G的一個支撐子圖T是一棵樹，則稱T為G的支撐樹，G有支撐樹若且唯若G是連通的。

有向樹是是一類特殊的樹，它是每條邊給予一確定的方向的樹。一個有向樹，若有一個節點，存在由此節點到達任何別的節點的有向路，則稱這個節點為源或根，稱這個樹為出樹或外向樹。入樹定義為這樣的有向樹：有一個節點，從任何一個節點出發都有樹上的一個有向路達到這個節點，這個節點稱為這個入樹的匯，也可以稱為根，出樹和入樹統稱為樹形圖。一個圖G上的一個支撐樹T，若可以將它的邊定向而成為一個外向樹，使得所有對T的上樹的邊都存在一種定向得到一個有向基本圈，則稱這個樹為深探樹，G的具有這種性質的定向的有向圖稱為它的棕圖。事實上，深探樹可以用如下的方式得到：任選G的一個節點作為始節點標號為0，達到它的一個鄰節點。每達到一個節點，若它的相鄰節點均已標號，則沿達到此節點的邊退回它的另一端點;否則，沿一條邊達到一個未標號的節點，標此節點為最大標號加1，並將此邊記錄下來;直到所有節點均已標號，這樣，所有記錄下來的邊就是一個深探樹，這就是深探之由來。若將樹邊定向為由小標號到大標號和上樹邊為從大標號到小標號，則可得一個棕圖.任取G的一個未註銷的已標號節點(開始時，任取G的一節點並假定該點的標號為1)，從最大標號加1起，按自然順序標號該節點的所有未標號鄰節點，並記下該節點與這些節點之間的所有邊，然後將該節點註銷.重複這樣的過程，直到所有的節點都被註銷為止，最終記錄下來的邊形成一棵樹。這樣，所有記錄下來的邊也形成一個樹，稱它為廣探樹。一個有向圖，若其中沒有有向圈，則稱為無迴路圖.如上所述，深探樹和廣探樹均為外向樹。若在圖中它們的上樹邊均定向為由小標號到大標號，則所得的有向圖均為無迴路圖。