導入
| まとめ ： | – |
|---|
もっている
- 非循環(グラフ): 循環を含まないグラフ。
- 隣接関係 (リスト) : i 番目の要素がi番目の頂点の近傍のリストに対応する配列で構成されるデータ構造。
- 隣接関係 (行列) : インデックスiとjの頂点を端に持つエッジの数に対応する要素a i jの行列。
- 隣接関係 (関係) : 同じエッジによって接続される 2 つの頂点のプロパティ (隣接する頂点と呼びます)、または共通の端を持つ 2 つのエッジのプロパティ (隣接するエッジと呼びます)。同義語：隣人関係。
- 随伴(グラフ):折れ線グラフと同義。
- アドミタンス:ラプラシアン行列の別名。
- ランダム(グラフ): グラフの構築に確率が含まれるとすぐに、グラフはランダム、つまり非決定的になります。
- ツリー: 循環のない接続されたグラフ。 n 個の頂点とn − 1 個のエッジを持つ接続されたグラフと同等です。
- 根付きツリーまたは樹枝状:有向非巡回グラフ。ここでは、入力次数0 のルートと、他のすべての頂点が入力次数 1 であることが区別されます。
- Arc : 有向グラフのエッジ。別の定式化: 無向グラフのエッジによって接続された頂点のペア (2 つの要素の順序付きセット)。
- 円弧推移(グラフ): 自己同型群がすべての円弧に対して推移的に作用する場合、グラフG は円弧推移であると言います。 2 つのエッジが与えられた場合$$ {e_1 = u_1v_1, e_2 = u_2v_2 \in G} $$、2つの自己同型があります$$ {(f_V,f_E) : G \rightarrow G} $$そして$$ {(g_V,g_E) : G \rightarrow G} $$f E ( e 1 ) = e 2 、 g E ( e 1 ) = e 2 、およびf V ( u 1 ) = u 2 、 f V ( v 1 ) = v 2 、 g V ( u 1 ) = v 2 、 g V ( v 1 ) = u 2 。
- エッジ: 2 つの頂点AとB の間の接続。有向グラフの場合、円弧について話します。 「エッジ」という用語は、2 つの円弧( A , B ) (つまりAからBへ) と( B , A ) (つまりBからAへ向かう) のセットを指定するために使用されます。
- 複数のエッジ: 頂点のペアに関連する平行なエッジのセット。
- 平行エッジ: 端が別のエッジと同じ頂点を持つエッジ。平行エッジ sについて話します。
- エッジ推移(グラフ): グラフの自己同型群がすべてのエッジで推移的に作用する場合、グラフはエッジ推移であると言います。条件の別の定式化: エッジの任意のペアについて、少なくとも 1 つの自己同型性が最初のコンポーネントを2 番目のコンポーネントに送信します。すべてのエッジはグラフ内でまったく同じ役割を果たします。例:完全なグラフ。
- 自己同型性: グラフ自体の同型性。各グラフには少なくとも 1 つの自己同型性、つまり恒等性があります。グラフの自己同型性の集合はグループを形成します。
C
- パス: グラフG = ( V , E )としましょう。パスP = ( S , A )は、 S = { s 0 ,…, s k } 、 A = { s 0 s 1 ,…, s k − 1 s k }によって定義されます。 $$ {S \subset V} $$、$$ {A \subset E} $$。言い換えれば、パスは無向グラフ内の連続したエッジのシーケンスです。有向グラフ、または無向グラフ内の一連のエッジの場合、 「チェーン」と呼ばれます。別の定義は、2 つの葉 (チェーンの両端) を持つ木の定義です。パスの長さはエッジの数、つまり |A| です。パスが再度頂点を通過しない場合、そのパスは基本パスであると言われます。通常、基本パスの場合を暗黙的に考慮します。
- 円周: 最大周期の長さ。
- Clique : 完全な誘導サブグラフ、つまり、それぞれが他のすべてに接続されている頂点のサブセット。クリークは、相補グラフの独立した (または安定した) セットです。
- Coloring : 隣接する 2 つの頂点が異なる色を持つように、任意の頂点をcolorに関連付ける関数 (つまり、頂点を独立したセットに分割します)。グラフGの最小色の数は、 χ( G )で示される色数です。
- k -coloring : k 個の異なる色でグラフを色付けします。
- Complementary : 相補的 (または逆相、または相補的) $$ {\bar{G}} $$単純なグラフのG = ( V , E )は、 Gと同じ頂点を持ち、元のグラフで接続されていない場合にのみ接続された単純なグラフです。$$ {\bar{G} = (V, [V]^2 \backslash E)} $$。
- Complete : 完全なグラフでは、各頂点が他のすべての頂点に接続されます。 n個の頂点を持つ完全なグラフをK nで表します。
- コンポーネント: グラフのコンポーネントは、最大接続サブグラフです。
- 関連: 頂点のペアの間にパスがある場合、グラフは接続されています。有向グラフの接続性について話すときは、このグラフではなく、対応する無向グラフを考慮します。これは、たとえば深度トラバーサル アルゴリズムを使用して決定できます。有向グラフは、グラフの頂点のペア(u,v)について、 uからvおよびvからuへのパスが存在する場合、強く接続されていると言われます。
- k -edge-connected : k 個のエッジを削除した場合にのみグラフが接続されなくなる場合、グラフは k-edge-connected になります。これは、各頂点間にk 個の互いに素なチェーン (エッジを共有していない) が存在することによって確認できます。
- k -vertex-connected (またはk -connected ): k個の頂点を削除したときにのみグラフが接続されなくなる場合、グラフはk -vertex-connected になります。
- Contain : HがGの誘導部分グラフである場合、グラフGはH を含むと言われます。
- 縮小: グラフの 2 つの端を結合することにより、グラフからエッジを削除します。つまり、頂点xにおけるエッジe x yの縮小G / eにより、頂点x はyの前に隣接するすべての頂点に隣接します。
- Chord : サイクルの隣接しない 2 つの頂点を接続するエッジ
- 共スペクトル: 2 つのグラフが同じスペクトルを持つ場合、それらのグラフは共スペクトルになります。このスペクトルはいくつかの行列に基づくことができ、隣接行列のスペクトルには A 共スペクトルを指定し、ラプラシアン行列のスペクトルには L 共スペクトルを指定できます。
- Cubic : 3 つの正則グラフ。
- Cycle : 開始頂点と終了頂点が同じパス。言い換えると、エッジがE = { s 0 s 1 ,…, s k − 2 s k − 1 }であるパスを考えてみましょう。サイクルは次のように定義されます。 $$ {E \cup \{s_{k-1}s_k\}} $$。
- サイクロマティック: グラフG = ( V , E )のサイクロマティック数はM = | E | − | V | + P 、ここでPは連結成分の数です。それはサイクル空間の次元でもあります。
| まとめ ： | – |
|---|
