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