本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2024-03-12
摘要
分區 P 和層次結構 H 或樹狀分割系統 S 是否相容的問題自然會在廣泛的分類問題中出現。在系統發育樹的設定中，我們要問P的集合是否與從樹T中刪除分別代表H或S的一些邊而獲得的連通分量的葉集是否一致。更一般地，我們詢問 T 的細化 T* 是否存在，使得 T* 和 P 在這個意義上是相容的。後者與是否存在與 P 相容的樹的問題密切相關。我們報告了與分區（的系統）相容的層次結構（的細化）和分割系統的幾個特徵。此外，我們提供了一種線性時間演算法來檢查樹的細化和給定分區是否相容。如果考慮分區系統而不是單一分區，則後一個問題將成為 NP 完全問題，但固定參數易於處理。在此背景下，我們也探討了相容性概念與所謂的 Fitch 地圖的密切關係。