Trémaux樹

在圖理論中，一個無向圖的trémaux樹是一種跨越樹的類型，概括了深度優先的搜索樹。它們是由屬性定義的連接樹上的祖先 - 居民對。 Trémaux樹木以19世紀的法國作家Charles PierreTrémaux的名字命名，他以深度優先搜索的形式作為解決迷宮的策略。它們也稱為正常跨越樹，尤其是在無限圖的背景下。

所有深度優先的搜索樹和所有漢密爾頓路徑都是Trémaux樹。在有限的圖中，每個trémaux樹都是一個深度優先的搜索樹，但是儘管深度優先搜索本質上是順序的，但可以通過複雜性類RNC中的隨機平行算法來構造Trémaux樹。它們可用於定義圖的樹深度，作為左右平面測試的一部分，用於測試圖形是否是平面圖。圖形二階邏輯中Trémaux樹的表徵允許使用Courcelle的定理有效地識別涉及方向的圖形屬性。

並非每個無限連接的圖都有一棵trémaux樹，也不是每個無限的trémaux樹都是深度優先的搜索樹。帶有Trémaux樹的圖可以以禁忌的未成年人為特徵。無限的trémaux樹必須在圖的每一端都有一個無限的路徑，而trémaux樹的存在表徵了圖形，其拓撲完成（通過在無窮大的每個端添加一個點）形成的圖形是度量空間。

定義和示例

trémaux樹，用於圖 ，是一棵樹使用屬性，每一個邊緣在 ，兩個端點之一和是對方的祖先。要成為一棵生成樹，它必須只使用 ，並包括每個頂點，每對頂點之間都有獨特的有限路徑。此外，為了定義這棵樹中的祖先 - 居民關係，必須將其一個頂點之一指定為其根。

如果有限的圖具有Hamiltonian路徑，則將該路徑紮根於其兩個端點之一會產生Trémaux樹。對於這樣的路徑，每對頂點都是祖先 - 居民對。

在下面所示的圖中，邊緣1-3、2-3和3–4的樹是植根於頂點1或頂點2的Trémaux樹：圖表的每個邊緣屬於樹，除了邊緣除外1-2， （對於根的這些選擇）連接祖先- 居民對。

但是，在頂點3或頂點4上生根同一樹會產生一個不是trémaux樹的根樹，因為使用該根1和2不再是彼此的祖先和後代。

在有限圖中

存在

每個有限連接的無向圖都有至少一棵trémaux樹。一個人可以通過執行深度優先搜索並將每個頂點（搜索的啟動頂點）連接到從中發現的早期頂點來構造這種樹。以這種方式構建的樹被稱為深度優先搜索樹。如果是圖中的任意邊緣，並且是搜索要達到的兩個頂點的較早，然後必須屬於子樹從在深度優先的搜索樹中，因為搜索必然會發現當它探索這個子樹時，要么是從子樹中的其他頂點之一探索，要么是從直接地。每個有限的trémaux樹都可以作為深度優先的搜索樹生成：如果是有限圖的Trémaux樹，深度優先搜索探索了孩子在探索其他任何頂點之前，每個頂點都必須生成作為深度優先搜索樹。

平行結構

找到由順序深度優先搜索算法找到的Trémaux樹是P-Complete ，其中每個頂點的鄰居按其身份按順序搜索。然而，可以通過隨機平行算法找到不同的Trémaux樹，表明Trémaux樹的結構屬於復雜性類RNC 。該算法基於另一種隨機並行算法，用於在0-1加權圖中找到最小重量的完美匹配。截至1997年，在復雜性類NC中，確定性平行算法是否可以通過確定性並行算法進行Trémaux樹的結構。如果可以在NC中找到匹配，那麼Trémaux樹也可以。

邏輯表達式

可以表達屬性設置具有root頂點的邊緣在圖形的單層二階邏輯中形成了Trémaux樹，更具體地說是以這種邏輯的形式稱為MSO ₂ ，它允許對頂點和邊緣集進行定量。該屬性可以表示為以下屬性的結合：

• 該圖由邊緣連接 。這可以在邏輯上表達為以下陳述，即對於圖形頂點的每個非空正確子集，都存在一個優勢在給定子集中恰好有一個端點。
• 是無環。這可以在邏輯上表達為不存在非空的子集的陳述的對於每個頂點，其入射到零或兩個邊緣 。
• 每個邊緣不在連接一對祖先 - 居民對 。當兩個端點的端點的屬於 。它可以從邏輯上表示為所有邊緣的陳述 ，有一個子集的這樣就是兩個頂點，其中之一 ，事件發生到一個邊緣 ，以及兩個端點至少有一個邊緣 。

一旦以這種方式識別了trémaux樹，可以通過指定從祖先端點到後代終點的一組邊緣來描述給定圖的方向，也可以用monadic二階邏輯。該集合外部的其餘邊緣必須朝另一個方向定向。該技術允許在Monadic二階邏輯中指定涉及方向的圖形屬性，從而可以使用Courcelle的定理在有界樹寬的圖表上有效地測試這些屬性。

相關屬性

如果圖具有Hamiltonian路徑，那麼該路徑（紮根於其端點之一）也是Trémaux樹。每個Trémaux樹具有此形式的無方向圖是循環圖，完整圖和平衡的完整二分圖。

Trémaux樹與樹深度的概念密切相關。圖的樹深度可以定義為最小的數字存在圖 ，帶有Trémaux樹深度 ，這樣是 。在一個圖的家族中，有界的樹深度等同於無法作為家族中圖形的圖形小徑出現的路徑的存在。圖形上的許多硬計算問題都具有算法，當通過其輸入的樹深度參數化時，可以固定參數處理。

Trémaux樹在Fraysseix -Rosenstiehl平面標準中也起著關鍵作用，用於測試給定圖是否是平面。根據此標準，圖如果給定的trémaux樹是平面的 ，剩餘的邊緣可以以一致的方式向左側或右側放置，這要受到阻止邊緣相同位置互相交叉的限制。

在無限圖中

存在

並非每個無限圖都有正常的生成樹。例如，一組不可數的頂點上的完整圖沒有一個：完整圖中的普通跨越樹只能是一條路徑，但是路徑只有可數的頂點。但是，一組可數頂點上的每個圖確實都有一個普通的生成樹。

即使在可數的圖中，深度優先的搜索也可能無法成功探索整個圖，而不是每個正常的跨越樹都可以通過深度優先搜索生成：成為深度優先搜索樹，這是一個可計數的正常跨越樹必須只有一條無限的路徑或一個沒有一個無限的兒童（而不是兩者）的節點。

未成年人

如果無限圖有一個普通的跨越樹，每個連接的圖形的次要的 。得出的是，普通跨越樹的圖具有禁止未成年人的表徵。兩類禁止的未成年人之一是由兩分圖組成的圖，其中兩部分的一側是可計數的，另一側是不可數的，並且每個頂點都有無限程度。另一類禁止的未成年人由源自Aronszajn樹的某些圖組成。

此特徵的細節取決於用於形式化數學的設置理論公理化的選擇。特別是，在Martin公理為真實且連續假設的集合理論模型中，該特徵中的兩部分圖類別可以用單個禁止的小調代替。但是，對於連續假設是正確的模型，此類包含在次要順序中彼此無與倫比的圖形。

結束和衡量性

正常的跨越樹也與無限圖的末端密切相關，無限路徑的等效類別，這些路徑的等效類別以同一方向向無窮大。如果圖具有正常的生成樹，則該樹必須完全具有一個圖形末端的一個無限路徑。

無限圖可以通過將圖形本身視為簡單絡合物，並為圖表的每一端添加一個無窮大的點來形成拓撲空間。使用此拓撲，當且僅當將其一組頂點分解為可數的封閉集合時，圖形就具有正常的生成樹。此外，只有當圖具有正常的生成樹時，就可以用度量空間來表示此拓撲空間。