Loading article…
数学、特にグラフ理論において、根付きグラフとは、1つの頂点が根として区別されているグラフのことである。 [ 1 ] [ 2 ]根付きグラフの有向バージョンと無向バージョンの 両方が研究されており、複数の根を許容する変形定義も存在する。
ルート付きグラフは、（用途によっては）ポイント付きグラフやフローグラフとも呼ばれる。これらのグラフの用途によっては、ルート頂点からグラフ全体に到達可能であるという追加要件が課される場合がある。
位相グラフ理論では、根付きグラフの概念は、複数の頂点または複数の辺を根として考えるように拡張できます。前者は、この文脈で辺根付きグラフと区別するために、頂点根付きグラフと呼ばれることがあります。[ 3 ]複数のノードが根として指定されているグラフは、組み合わせ論のランダムグラフの分野でも興味深いものです。[ 4 ]これらのグラフは、多重根付きグラフとも呼ばれます。[ 5 ]
根付き有向グラフまたは根付きダイグラフという用語も定義にばらつきが見られます。明らかな移植は、特定のノードを根として識別することによって根付きダイグラフを考えることです。[ 6 ] [ 7 ]しかし、コンピュータサイエンスでは、これらの用語は一般的に、より狭い概念を指します。つまり、根付き有向グラフとは、 rからr以外の任意のノードへの有向パスが存在するような、特別なノードrを持つダイグラフです。[ 8 ] [ 9 ] [ 10 ] [ 11 ]より一般的な定義を与える著者は、より狭い定義を満たすグラフを、連結根付きダイグラフ[ 6 ]またはアクセス可能な根付きグラフ（§集合論を参照）と呼ぶことがあります。
『コンピュータプログラミングの技法』では、有向グラフをもう少し広い意味で定義しており、有向グラフは、他のすべてのノードに到達できるノードが少なくとも1つある場合に有向グラフと呼ばれます。クヌースは、このように定義された概念は、強連結有向グラフと連結有向グラフの概念の中間のようなものだと述べています。 [ 12 ]
コンピュータサイエンスでは、ルート頂点が他のすべての頂点に到達できるルート付きグラフは、フローグラフまたはフローグラフと呼ばれます。[ 13 ]フローグラフには単一の出口（シンク）頂点が必要であるという追加の制約が加えられることもあります。[ 14 ]
フローグラフは、フローチャートの抽象化であり、非構造要素（ノードの内容と型）が削除されていると考えることができます。 [ 15 ] [ 16 ]おそらく最もよく知られているフローグラフのサブクラスは、コンパイラやプログラム解析で使用される制御フローグラフです。任意のフローグラフは、ソースからの唯一の出力エッジであり、ターゲットへの唯一の入力エッジであるすべてのエッジに対してエッジ縮約を実行することによって、制御フローグラフに変換できます。 [ 17 ]一般的に使用されるもう1つのタイプのフローグラフは、ノードがサブルーチン全体に対応するコールグラフです。[ 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 ]
この文脈では、根付き有向グラフ Δ = (
V
、
E
、
r
) は、根からすべての頂点への有向パスが存在する場合に
連結
（または
1-連結
）と呼ばれます。
特に 307ページを参照のこと。
根付き部分有向グラフ
F
は
、
根頂点 ∗ が
F
に含まれ、
F
のすべての頂点
v
に対して、 ∗ から
vへの一意の有向パスが
F
に存在する場合、根付き樹状構造である
。したがって、有向グラフの根付き樹状構造は、無向グラフの根付き木に対応する。
根付き
有向グラフ
または
フローグラフ
G
= (
V
,
A
,
r) は、特別な頂点
r
を持つ有向グラフであり、
Gには
r
から
V
−
r
の
すべての頂点
v
への有向パスが存在する
。
特に 122ページを参照。
根付き有向グラフは
、(
V
∪ {
r
} ,
E ) が
有向グラフであり、
r が
ルートと呼ばれる特定の頂点であり、r から
V
のすべての頂点への
パスが存在するような、
3つ組
G
= (
V
,
E
,
r
)である
。
特に 524ページを参照。
根付き
有向グラフとは、
単一の根ノードを持ち、その根ノードが有向グラフ内の他のすべてのノードの祖先となる連結有向グラフのことです。
少なくとも１つの根、すなわち、
すべての
V
≠
Rに対して
Vから
R
への
向き付けられたパスが存在するような少なくとも１つの頂点
R が存在する場合、それは根付きであると言われます
。