根付きグラフ

数学、特にグラフ理論において、根付きグラフとは、1つの頂点が根として区別されているグラフのことである。 [1] [2]根付きグラフの有向バージョンと無向バージョンの 両方が研究されており、複数の根を許容する異型の定義もある。

いくつかのバリエーションを持つ根付きグラフの例。根が配置され、各頂点から根に向かう経路が1つだけ存在する有向グラフは、樹状グラフと呼ばれます。

ルート付きグラフは、用途に応じて、ポイントグラフまたはフローグラフとも呼ばれます。これらのグラフの用途によっては、ルート頂点から グラフ全体に到達可能であるという追加の要件が課せられる場合があります。

バリエーション

位相グラフ理論において、根付きグラフの概念は、複数の頂点または複数の辺を根として考えるように拡張されることがある。前者は、この文脈において辺根付きグラフと区別するために、頂点根付きグラフと呼ばれることもある。[3]複数のノードを根として持つグラフは、組合せ論、特にランダムグラフの分野でも興味深い。[4]これらのグラフは多重根付きグラフとも呼ばれる。[5]

ルート付き有向グラフやルート付き有向グラフという用語も定義が様々です。わかりやすい移植としては、特定のノードをルートとして識別することでルート付き有向グラフを考えることです。[6] [7]しかし、コンピュータサイエンスでは、これらの用語は一般的に、より狭い概念を指します。つまり、ルート付き有向グラフとは、 rからr以外の任意のノードへの有向パスが存在する、特定のノードrを持つ有向グラフです。[8] [9] [10] [11]より一般的な定義を与える著者は、より狭い定義を満たすグラフを、接続ルート付き有向グラフ[6]またはアクセス可能なルート付きグラフ (§ 集合論を参照) と呼ぶ場合があります。

『The Art of Computer Programming』では、根付き有向グラフをもう少し広く定義しています。つまり、有向グラフは、他のすべてのノードに到達できるノードが少なくとも1つある場合、根付きと呼ばれます。クヌースは、このように定義された概念は、強連結有向グラフと連結有向グラフの概念の中間のようなものだと指摘しています。 [12]

アプリケーション

フローグラフ

コンピュータサイエンスでは、ルート頂点が他のすべての頂点に到達できるルート付きグラフをフローグラフまたはフローグラフと呼びます。[13]フローグラフには出口（シンク）頂点が1つだけなければならないという追加の制約が加えられることもあります。[14]

フローグラフは、フローチャートから非構造的要素（ノードの内容や型）を取り除いた抽象化として捉えることができる。 [15] [16]フローグラフの最もよく知られたサブクラスは、コンパイラやプログラム解析で用いられる制御フローグラフであろう。任意のフローグラフは、そのソースから唯一の出力エッジであり、かつそのターゲットへの唯一の入力エッジであるすべてのエッジに対してエッジ縮約を実行することで、制御フローグラフに変換することができる。 [17]よく使われる別のタイプのフローグラフは、ノードがサブルーチン全体に対応するコールグラフである。[18]

フローグラフの一般的な概念はプログラムグラフと呼ばれてきましたが[19]、同じ用語は制御フローグラフのみを指すためにも使われてきました。[20]フローグラフはラベルなしフローグラフ[21]や適切なフローグラフ[15]とも呼ばれてきました。これらのグラフはソフトウェアテストで使われることがあります。[15] [18]

フローグラフは、単一の出口が必要な場合、一般的な有向グラフにはない2つの特性があります。フローグラフはネストすることができ、これはサブルーチン呼び出しと同等です（ただし、パラメータを渡すという概念はありません）。また、フローグラフはシーケンス化することができ、これは2つのコードの連続実行と同等です。[22] プライムフローグラフは、構造化プログラミングのプリミティブなどの選択されたサブグラフパターンを使用したネストまたはシーケンスによって分解できないフローグラフとして定義されます。[23]選択されたグラフセットが与えられた場合に、例えばプライムフローグラフの割合を決定することに関する理論的研究が行われてきました。[24]

集合論

ピーター・アツェルは、すべてのノードがルートから到達可能であるルート付き有向グラフ（彼はこれをアクセス可能な尖ったグラフと呼ぶ）を用いて、非整基礎集合論におけるアツェルの反基礎公理を定式化した。この文脈では、アクセス可能な尖ったグラフの各頂点は、アツェルの（非整基礎）集合論における（非整基礎）集合をモデル化し、頂点vから頂点wへの弧は、 vがwの要素であることをモデル化する。アツェルの反基礎公理は、すべてのアクセス可能な尖ったグラフがこのようにして（非整基礎）集合の族をモデル化すると述べている。[25]

組み合わせゲーム理論

任意の組み合わせ ゲームは、頂点がゲームの位置、辺が動き、根がゲームの開始位置である根付き有向グラフに関連付けられます。このグラフは、ゲームの複雑性の研究において重要であり、状態空間複雑性はグラフの頂点数です。

組み合わせ列挙

1、2、... ノードのルート付き無向グラフの数は、1、2、6、20、90、544、... です ( OEISのシーケンスA000666 )。

興味深い特別な例として、根付き木、すなわち明確な根頂点を持つ木が挙げられます。根付き有向グラフにおける根からの有向路がさらに一意となるように制限されている場合、得られる概念は（根付き）樹状突起、つまり根付き木の有向グラフ版です。[7]根付きグラフに同じ根を持つ樹状突起が含まれるのは、その根からグラフ全体に到達できる場合に限られます。コンピュータ科学者は、最適な樹状突起を見つけるアルゴリズム問題を研究してきました。[26]

ルート付きグラフはグラフのルート積を使って組み合わせることができる。[27]

参照

参考文献

  1. ^ ズウィリンガー、ダニエル（2011）、CRC標準数学表と公式、第32版、CRCプレス、p.150、ISBN 978-1-4398-3550-0
  2. ^ Harary, Frank (1955)、「線形グラフ、有向グラフ、根付きグラフ、連結グラフの数」、アメリカ数学会誌、78 (2): 445– 463、doi : 10.1090/S0002-9947-1955-0068198-2、MR  0068198454ページ参照。
  3. ^ グロス、ジョナサン・L.、イエレン、ジェイ、チャン・ピン（2013年）、グラフ理論ハンドブック（第2版）、CRCプレス、pp.  764– 765、ISBN 978-1-4398-8018-0
  4. ^ スペンサー、ジョエル（2001）、ランダムグラフの奇妙な論理、シュプリンガーサイエンス＆ビジネスメディア、第4章、ISBN 978-3-540-41654-8
  5. ^ ハラリー（1955年、455ページ）。
  6. ^ ab Björner, Anders ; Ziegler, Günter M. (1992)、「8. グリードイド入門」(PDF)、White, Neil (ed.)『マトロイド応用』、Encyclopedia of Mathematics and its Applications、第40巻、ケンブリッジ: ケンブリッジ大学出版局、pp. 284–357、doi :10.1017/CBO9780511662041.009、ISBN 0-521-38165-7, MR  1165537, Zbl  0772.05026,この文脈では、根付き有向グラフ Δ = ( V、E、r ) は、根からすべての頂点への有向パスがある場合、連結(または1-連結)であると呼ばれます。特に307ページを参照してください。
  7. ^ ab Gordon, Gary; McMahon, Elizabeth (1989年2月)、「根付き樹状突起を区別するグリードイド多項式」(PDF)、米国数学会紀要、107 (2): 287、CiteSeerX 10.1.1.308.2526、doi : 10.1090/s0002-9939-1989-0967486-0、根付き部分有向グラフFが根付き樹状突起であるとは、根頂点 ∗ がFに含まれ、Fのすべての頂点vに対して、 ∗ からvへの唯一の有向路がFに存在する場合である。したがって、有向グラフの根付き樹状突起は、無向グラフの根付き木に対応する。 
  8. ^ ラマチャンドラン、ヴィジャヤ（1988年）、「可縮フローグラフのための高速並列アルゴリズム」、同時計算：117-138、doi：10.1007/978-1-4684-5511-3_8、ISBN 978-1-4684-5513-7ルート付き有向グラフまたはフローグラフG = ( V、A、r ) は、特定の頂点rを持つ有向グラフであり、 GにはrからV − r内のすべての頂点vへの有向パスがあります。 特に122ページを参照してください。
  9. ^ 岡本 善夫; 中村 正孝 (2003)、「根付き有向グラフの線探索反マトロイドの禁じられたマイナー特徴付け」(PDF)、離散応用数学、131 (2): 523– 533、doi : 10.1016/S0166-218X(02)00471-7、根付き有向グラフは、3つ組G =( V、E、r ) で、 ( V ∪ { r }, E ) は有向グラフ、rはルートと呼ばれる指定された頂点で、 rからVのすべての頂点へのパスが存在するものです。特に524ページを参照してください。
  10. ^ Jain, Abhinandan (2010)、「ロボットとマルチボディダイナミクス：分析とアルゴリズム」、Springer Science & Business Media、p. 136、ISBN 978-1-4419-7267-5ルート付き有向グラフは、有向グラフ内の他のすべてのノードの祖先となる単一のルート ノードを持つ接続された有向グラフです。
  11. ^ Chen, Xujin; Zang, Wenan (2006)、「可約フローグラフにおける最大サイクルパッキングを見つけるための効率的なアルゴリズム」、Algorithmica、44 (3): 195– 211、doi :10.1007/s00453-005-1174-x、hdl : 10722/48600、MR  2199991、S2CID  5235131
  12. ^ Knuth, Donald (1997)、「2.3.4.2. 有向木」、The Art of Computer Programming、第1巻（第3版）、Pearson Education、372ページ、ISBN 0-201-89683-4少なくとも 1 つの根、つまり、すべてのV ≠ Rに対してVからRへの有向パスが存在するような頂点Rが少なくとも 1 つある場合、その頂点は根付きであると言われます。
  13. ^ グロス、イエレン、チャン（2013年、1372頁）。
  14. ^ フェントン、ノーマン・エリオット; ヒル、ジリアン・A. (1993)、『システム構築と分析：数学的・論理的枠組み』、マグロウヒル、319ページ、ISBN 978-0-07-707431-9。
  15. ^ abc Zuse、Horst (1998)、ソフトウェア測定のフレームワーク、Walter de Gruyter、 32–33ページ 、ISBN 978-3-11-080730-1
  16. ^ Samaroo, Angelina; Thompson, Geoff; Williams, Peter (2010)、「ソフトウェアテスト：ISTQB-ISEB Foundationガイド」、BCS、The Chartered Institute、p. 108、ISBN 978-1-906124-76-2
  17. ^ Tarr, Peri L.; Wolf, Alexander L. (2011)、「ソフトウェアのエンジニアリング：Leon J. Osterweilの継続的な貢献」、Springer Science & Business Media、p. 58、ISBN 978-3-642-19823-6
  18. ^ ab Jalote, Pankaj (1997),ソフトウェア工学への統合アプローチ、Springer Science & Business Media、p. 372、ISBN 978-0-387-94899-7
  19. ^ Thulasiraman, K.; Swamy, MNS (1992)、『グラフ：理論とアルゴリズム』、John Wiley & Sons、361ページ、ISBN 978-0-471-51356-8
  20. ^ Cechich, Alejandra; Piattini, Mario; Vallecillo, Antonio (2003), Component-Based Software Quality: Methods and Techniques , Springer Science & Business Media, p. 105, ISBN 978-3-540-40503-0
  21. ^ Beineke, Lowell W.; Wilson, Robin J. (1997), Graph Connections: Relationships Between Graph Theory and Other Areas of Mathematics, Clarendon Press, p. 237, ISBN 978-0-19-851497-8
  22. ^ フェントン＆ヒル（1993年、323ページ）。
  23. ^ フェントン＆ヒル（1993年、339ページ）。
  24. ^ Cooper, C. (2008)、「述語結合フローグラフの漸近的列挙」、組合せ論、確率、計算、5 (3): 215– 226、doi :10.1017/S0963548300001991、S2CID  10313545
  25. ^ Aczel, Peter (1988), Non-well-founded sets (PDF) , CSLI Lecture Notes, vol. 14, スタンフォード大学言語情報研究センター, ISBN 0-937073-22-9LCCN  87-17857、MR 0940014 、 2015年3月26日時点の オリジナル（PDF）からアーカイブ
  26. ^ Drescher, Matthew; Vetta, Adrian (2010)、「最大葉面積樹木問題に対する近似アルゴリズム」、ACM Trans. Algorithms、6 (3): 46:1–46:18、doi :10.1145/1798596.1798599、S2CID  13987985。
  27. ^ Godsil, CD ; McKay, BD (1978)、「新しいグラフ積とそのスペクトル」(PDF)、Bull. Austral. Math. Soc.、18 (1): 21– 28、doi : 10.1017/S0004972700007760、MR  0494910

さらに読む

  • マクマホン、エリザベス W. (1993)、「根付きグラフと根付き有向グラフのグリードイド多項式について」、グラフ理論ジャーナル、17 (3): 433– 442、doi :10.1002/jgt.3190170316
  • ゴードン、ゲイリー（2001）「根付きグラフと根付き有向グラフの特性多項式」、離散数学、232（1-3）：19-33、doi：10.1016/S0012-365X（00）00186-2
「https://en.wikipedia.org/w/index.php?title=Rooted_graph&oldid=1270507126」より取得