在圖論（數學的一個分支）中，一個雙連通圖的三連通分量是一組較小的圖，用來描述該圖中的所有 2-頂點割。SPQR樹是電腦科學中，更精確地說，是圖論演算法中的一種樹狀資料結構，用以表示圖中的所有三連通分量。一個圖的 SPQR 樹可以在線性時間內構造，並且在動態圖演算法與圖繪製中均有若干應用。

SPQR樹背後的基本結構，圖的三連通分量以及這種分解和平面圖平面嵌入之間的關係，最早由 Saunders Mac Lane (1937) 研究，在 Di Battista 與 Tamassia (1989, 1990, 1996) 將其正式形式化為 SPQR 樹之前，已有若干研究者將這些結構用於高效演算法中。

結構
SPQR樹是一棵無根樹，其中每個節點 x 都關聯到一個無向圖或重圖的 G_x。每個節點，以及其對應到的圖，有下列的四種類型之一（即 S、P、Q、R）：

• 在一個 S（Series）節點，對應到的是一個三個頂點以上的環圖。這個類型跟串聯-並聯圖中的「串聯」類似。
• 在一個 P（Parallel）節點，對應到的是一個雙極圖，亦即只有兩個頂點，且兩個頂點中間有三條以上的平行邊的重圖，其為環圖的平面對偶。這個類型跟串聯-並聯圖中的「並聯」類似。
• 在一個 Q 節點，對應到的是一個只有一條實邊的圖。這個類型對於原本的圖只有一條邊的邊界情況有其存在的必要。但在某些使用 SPQR 樹的研究中，這類型的節點並不會出現在多於一條邊的圖中；相對的也有些研究，每條非虛邊的邊都得被 Q 節點用一條實邊和一條虛邊表示，而其他類型節點中的邊則必須是虛邊。
• 在一個 R（Rigid）節點，對應到的是一個不是環也不是雙極的三連通圖。在 SPQR 樹被用於尋找平面圖的平面嵌入時，R 節點對應到的圖有唯一的平面嵌入。

每條 SPQR 樹中連接兩個節點的邊 xy 都被分配到兩條有向虛邊，一條是 G_x 中的邊，而另一條是 G_y 中的邊。每條 G_x 中的邊都可能是 SPQR 樹中的至多一條虛邊。

一個 SPQR 樹 T 代表的是一個雙連通圖 G_T，我們可以用如下的方式還原。當 SPQR 樹中的樹邊 xy 對應到 G_x 中的虛邊 ab 和 G_y 中的虛邊 cd，將 a,c 黏合成一個頂點，將 b,d 黏合成另一個頂點，並刪除兩條虛邊。亦即，我們做的是 G_x,G_y 的 2-團和。對每個 T 中的樹邊重複以上步驟，即可還原 G_T，步驟的順序並不影響結果。每個 G_x 中的頂點可以與唯一一個 G_T 中的頂點對應，也就是合併時黏合出的頂點。

原則上，SPQR樹中並不允許兩個相鄰的 S 節點或兩個相鄰的 P 節點，否則將該兩個節點合併成一個更大的同類型節點即可。根據這個性質，一個圖的 SPQR 樹可以被唯一決定。當一個圖 G 的 SPQR 樹中沒有相鄰的 S 節點或相鄰的 P 節點時，每一個節點對應到的圖 G_x 就是 G 的三連通分量。

構造
一個雙連通圖對應的 SPQR樹可以在線性時間內被構造。

構造一個圖的所有三連通分量問題由 Hopcroft 和 Tarjan (1973) 首先在線性時間內解決。根據這個演算法，Di Battista 和 Tamassia (1996) 認為完整構造 SPQR 樹，而非只是列出所有三連通分量，應當也要能在線性時間內完成。在 GDToolkit 函式庫中實作了一個較慢的 SPQR 樹演算法後，Gutwenger 和 Mutzel (2001) 提供了第一個線性時間實作的演算法。在實作該演算法後，他們也更正了一些早期 Hopcroft 和 Tarjan (1973) 研究中的錯誤。

Gutwenger 和 Mutzel (2001) 的演算法由以下的步驟構成：

將圖中各個邊按照其連接的兩個頂點的頂點編號進行排序，排序運用一個利用兩次桶排序的基數排序變體，兩次排序分別對應到每邊的兩個頂點。在排序後，兩頂點間若有多條平行邊，將會在排列的表中相鄰，於是可以被分解出一個 SPQR 樹中的 P 節點，剩下的圖於是成為簡單圖。

把圖分解成數個分裂分量，分裂分量是透過尋找一對 2-頂點割，把圖由這兩個頂點分解成兩個較小的圖所形成（並加入一對以這兩個頂點為端點，彼此相互對應的虛邊）。重複這個步驟直至沒有 2-頂點割存在。這個步驟尋找到的分裂分量並不唯一，因為該變成 S 節點的部分會被拆分成很多個三角形。

將每個分裂分量標號成 P（只有兩個頂點但多條邊的分裂分量）、S（一個形如三角形的分裂分量）和 R（任何其他分裂分量）。如果有任兩個分裂分量共用同一對虛邊，且它們是兩個相鄰的 S 節點或兩個相鄰的 P 節點，就把他們合併成一個更大的組件並標上同樣的標號。

為了找出分裂分量，Gutwenger 和 Mutzel 使用深度優先搜尋（DFS）去找到一種稱為棕櫚樹的結構：這是一棵 DFS-樹，其中樹邊皆由根往外，指向子孫方向定向；而非樹邊則皆朝向根，指向祖先方向定向。他們隨後找到一個特別的前序編號代表樹中的各個節點，並用這個編號去找出可以將圖分解成更小的組件的點對。當用此法找到一個組件時，一個堆棧的資料結構可以被用於識別哪些邊應該對應到哪些新組件。

用途
找到 2-頂點割
一個代表圖 G 且沒有 Q 節點的 SPQR 樹，我們可以輕易找到每一對頂點 u,v 使得移除它們後將會得到一個不連通圖以及其各個連通分量。

• 點對 u,v 可能是某個 S 節點或 R 節點所關聯圖中一條虛邊的兩個頂點，此時移除 u,v 後得到的兩個部分，可由刪除對應 SPQR 樹邊後形成的兩棵子樹表示。
• 點對 u,v 可能是某個 P 節點所關聯圖中的兩個頂點，且該 P 節點含有兩條以上的虛邊，此時移除 u,v 後形成的各個連通分量，可由 SPQR 樹中的若干子樹表示，每條虛邊對應一棵子樹。
• 點對 u,v 可能是 S 節點中不相鄰，或者以虛邊連接的兩個頂點。如果以虛邊連接，那點對 u,v 也存在於某個 P 或 R 節點，如上所述。若兩頂點不相鄰，則移除 u,v 後的兩個部分，分別由該 S 節點的環圖中 u 與 v 之間的兩條路徑，以及附著在這兩條路徑上的 SPQR 樹節點所表示。

2-頂點割的數量即是 SPQR 樹的樹邊數，加上各個 S 節點中不相鄰的點對數（若為 k 個頂點的環則有 \frac{k(k-3)}{2} 個這樣的點對）。

表示所有平面圖的平面嵌入
若平面圖為三連通的，則除了選哪個面作為外面，以及整個圖可作鏡像翻轉之外，該圖的平面嵌入是唯一的，嵌入的每一個面就是不會分割該圖的環。然而，對於一個非三連通的雙連通圖，就有可能有更多情況。精確地說，任兩個在 SPQR 樹中用一對虛邊連接的兩個節點，可以將其中一個節點相對於另一個節點翻轉，也就是替換成其鏡像。另外，一個 SPQR 樹中的 P 節點，各個連接到 P 節點中虛邊的組件可以被任意排列。但所有平面嵌入都可以被以上述的方式刻畫。

參見

• 塊割樹，一個類似的資料結構用以描述雙連通分量。
• Gomory-Hu樹，一個不同的樹結構用以描述圖中的邊連通度。
• 樹分解，一個推廣（不再唯一）的更大的圖分解。

參考資料
外部連結

• [https://www.ogdf.uni-osnabrueck.de/doc/_s_p_q_r_tree_8h_source.html Open Graph Drawing Framework 中的 SPQR 樹實作]
• [http://code.google.com/p/jbpt/ jBPT 函式庫中的三連通分量樹 Java 實作]