Graph-theory-connectivity
グラフ理論-接続性
グラフをある頂点から別の頂点に移動できるかどうかは、グラフの接続方法によって決まります。 接続性は、グラフ理論の基本概念です。 接続性は、グラフが接続されているか切断されているかを定義します。 エッジの接続性と頂点の接続性として知られる、エッジと頂点に基づくサブトピックがあります。 それらについて詳しく説明しましょう。
接続性
グラフは、頂点のすべてのペア間にパスがある場合、接続されていると言われます。 すべての頂点から他の頂点まで、横断するパスが必要です。 これは、グラフの接続性と呼ばれます。 複数の切断された頂点とエッジを持つグラフは切断されていると言われます。
例1
次のグラフでは、1つの頂点から他の頂点に移動できます。 たとえば、パス「a-b-e」を使用して、頂点「a」から頂点「e」に移動できます。
例2
次の例では、頂点「a」から頂点「f」への移動は、それらの間に直接または間接にパスがないため不可能です。 したがって、これは切断されたグラフです。
頂点をカット
「G」を接続グラフとします。 頂点V∈Gは、「G-V」（「G」から「V」を削除）が切断されたグラフになる場合、「G」のカット頂点と呼ばれます。 カットされた頂点をグラフから削除すると、2つ以上のグラフに分割されます。
注意-カットされた頂点を削除すると、グラフが切断される場合があります。
接続されたグラフ「G」には、最大（n–2）個のカット頂点があります。
例
次のグラフでは、頂点「e」と「c」がカットされた頂点です。
「e」または「c」を削除すると、グラフは切断されたグラフになります。
「g」がないと、頂点「c」と頂点「h」などの間にパスがありません。 したがって、これは切断された頂点が「e」の非接続グラフです。 同様に、「c」も上のグラフのカット頂点です。
カットエッジ（ブリッジ）
「G」を接続グラフとします。 「G-e」が切断されたグラフになる場合、エッジ「e」∈Gはカットエッジと呼ばれます。
グラフのエッジを削除すると、2つ以上のグラフが作成される場合、そのエッジはカットエッジと呼ばれます。
例
次のグラフでは、カットエッジは[（c、e）]です
グラフからエッジ（c、e）を削除すると、切断されたグラフになります。
上のグラフで、エッジ（c、e）を削除すると、グラフは2つに分割されますが、これは切断されたグラフにすぎません。 したがって、エッジ（c、e）はグラフのカットエッジです。
注-「G」を「n」個の頂点を持つ接続グラフとし、
- エッジ 'e’がGのサイクルの一部でない場合にのみ、カットエッジe∈G
- 可能なカットエッジの最大数は「n-1」です。
- カットエッジが存在する場合は常に、カットエッジの少なくとも1つの頂点がカット頂点であるため、カット頂点も存在します。
- カット頂点が存在する場合、カットエッジが存在する場合と存在しない場合があります。
グラフのカットセット
「G」=（V、E）を接続グラフとします。 EのサブセットE 'は、GからE’のすべてのエッジを削除するとGが切断される場合、Gのカットセットと呼ばれます。
グラフから特定の数のエッジを削除すると切断される場合、それらの削除されたエッジはグラフのカットセットと呼ばれます。
例
次のグラフをご覧ください。 そのカットセットはE1 = \ {e1、e3、e5、e8}です。
グラフからカットセットE1を削除した後、次のように表示されます-
同様に、グラフを切断できる他のカットセットがあります-
- E3 = \ {e9} –グラフの最小カットセット。
- E4 = \ {e3、e4、e5}
エッジ接続
「G」を接続グラフとします。 削除によって「G」が切断されるエッジの最小数は、Gのエッジ接続と呼ばれます。
表記-λ（G）
言い換えれば、Gの最小カットセットの*エッジの数は、Gのエッジ接続性と呼ばれます。
「G」にカットエッジがある場合、_λ（G）_は1です。 （Gのエッジ接続。）
例
次のグラフをご覧ください。 2つの最小エッジを削除すると、接続されたグラフは切断されます。 したがって、エッジの接続性（λ（G））は2です。
ここに2つのエッジを削除してグラフを切断する4つの方法があります-
頂点接続
「G」を接続グラフとします。 削除によって「G」が切断されるか、「G」が単純なグラフに減少する頂点の最小数は、その頂点接続性と呼ばれます。
表記-K（G）
例
上のグラフで、頂点「e」と「i」を削除すると、グラフが切断されます。
Gにカット頂点がある場合、K（G）= 1。
表記-接続されたグラフGの場合、
K（G）≤λ（G）≤δ（G）
頂点接続（K（G））、エッジ接続（λ（G））、G（δ（G））の最小次数。
例
次のグラフのλ（G）とK（G）を計算します-
溶液
グラフから、
δ（G）= 3
K（G）≤λ（G）≤δ（G）= 3（1）
K（G）≥2（2）
エッジ\ {d、e}および\ {b、h}を削除すると、Gを切断できます。
したがって、
λ（G）= 2
2≤λ（G）≤δ（G）= 2（3）
（2）および（3）から、頂点接続性K（G）= 2
