本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2024-03-12
摘要
準最佳配對圖 (qBMG) 是一類遺傳性的有向、正確頂點著色的圖。它們作為最佳匹配圖的概括在數學系統發生學中自然出現，它形式化了多個物種（頂點顏色）中基因（頂點）的進化最接近相關性的概念。它們可以透過有根樹來解釋，樹的葉子對應於頂點。與 BMG 相比，qBMG 僅代表有限系統發育距離內的最佳匹配。我們提供了 qBMG 的表徵，這些特徵產生了多項式時間識別演算法，並將 BMG 識別為無色沉的 qBMG。此外，雙色 qBMG 的特徵是滿足三個簡單局部條件的有向圖，其中兩個先前已經出現過，即 Das 等人意義上的雙傳遞性。 (2021) 和外部鄰域的類似層次結構，即對任兩個頂點 x 和 y，N(x) n N(y) E {N(x), N(y), 0}。進一步的結果表徵了可以用二元系統發育樹解釋的 qBMG。