レベル構造

グラフ理論の数学的な分野において、根付きグラフのレベル構造とは、頂点を与えられた根頂点から同じ距離にある部分集合に分割したものである。 ^[1]

定義と構築

連結グラフ G = ( V , E )において、 Vが頂点の集合、E が辺の集合であり、ルート頂点がrであるとすると、レベル構造は頂点をレベルと呼ばれるサブセットL _iに分割したもので、 rからiの距離にある頂点で構成されます。同様に、このセットはL ₀ = { r }と設定し、次にi > 0 に対して、L _{i を}L _i_{− 1}の頂点に隣接しているが、それ自身はどのレベルにも属さない頂点の集合として定義することによっても定義できます。^[1]

グラフのレベル構造は幅優先探索の変形によって計算できる: ^[2]^:176

アルゴリズムレベルBFS(G, r):
    Q ← {r}
    ℓが0から∞ の場合:
        process(Q, ℓ)   // 集合Qはレベルℓのすべての頂点を保持する
        Q内のすべての頂点を発見済みとしてマークする
        Q' ← {}
        Qのuについて:
            各辺 (u, v) について:
                 v がまだマークされていない場合:
                    Q'にvを加える
        Q'が空の
            場合:返す
        Q ← Q'

プロパティ

レベル構造では、Gの各辺は両方の端点が同じレベル内にあるか、2つの端点が連続したレベルにあります。^[1]

アプリケーション

グラフをレベル構造に分割することは、グラフ帯域幅などのグラフレイアウト問題に対するヒューリスティックとして使用できます。^[1]Cuthill-McKeeアルゴリズムは、各レベル内での追加のソートステップに基づいて、このアイデアを改良したものです。^[3]

レベル構造は疎行列のアルゴリズムにも使用され、^[4]平面グラフのセパレータの構築にも使用されます。^[5]

参考文献

^ abcd ディアス、ジョセップ;プティ、ジョルディ。Serna、Maria (2002)、「グラフレイアウト問題の調査」(PDF)、ACM Computing Surveys、34 (3): 313–356、CiteSeerX 10.1.1.12.4358、doi :10.1145/568522.568523、S2CID 63793863。
^ Mehlhorn, Kurt ; Sanders, Peter (2008). アルゴリズムとデータ構造: 基本ツールボックス(PDF) . Springer.
^ Cuthill, E. ; McKee, J. (1969)、「スパース対称行列の帯域幅の削減」、1969 年第 24 回全国会議 (ACM '69) の議事録、ACM、pp. 157–172、doi :10.1145/800195.805928、S2CID 18143635。
^ George, J. Alan (1977)、「線形方程式系の解法: 有限要素問題に対する直接法」、スパース行列技法 (上級コース、デンマーク工科大学、コペンハーゲン、1976)、ベルリン: Springer、pp. 52–101。数学の講義ノート、第 572 巻、MR 0440883。
^ リプトン、リチャード J. ;タージャン、ロバート E. (1979)、「平面グラフのセパレータ定理」、SIAM Journal on Applied Mathematics、36 (2): 177–189、CiteSeerX 10.1.1.214.417、doi :10.1137/0136016 。

[dps-1] ディアス、ジョセップ;プティ、ジョルディ。Serna、Maria (2002)、「グラフレイアウト問題の調査」(PDF)、ACM Computing Surveys、34 (3): 313–356、CiteSeerX 10.1.1.12.4358、doi :10.1145/568522.568523、S2CID 63793863。

[mehlhorn-2] Mehlhorn, Kurt ; Sanders, Peter (2008). アルゴリズムとデータ構造: 基本ツールボックス(PDF) . Springer.

[3] Cuthill, E. ; McKee, J. (1969)、「スパース対称行列の帯域幅の削減」、1969 年第 24 回全国会議 (ACM '69) の議事録、ACM、pp. 157–172、doi :10.1145/800195.805928、S2CID 18143635。

[4] George, J. Alan (1977)、「線形方程式系の解法: 有限要素問題に対する直接法」、スパース行列技法 (上級コース、デンマーク工科大学、コペンハーゲン、1976)、ベルリン: Springer、pp. 52–101。数学の講義ノート、第 572 巻、MR 0440883。

[5] リプトン、リチャード J. ;タージャン、ロバート E. (1979)、「平面グラフのセパレータ定理」、SIAM Journal on Applied Mathematics、36 (2): 177–189、CiteSeerX 10.1.1.214.417、doi :10.1137/0136016 。