インシデントエッジとは何ですか？

1. 概要

このチュートリアルでは、インシデントエッジとは何か、およびそれが有向グラフと無向グラフでどのように検出されるかについて説明します。

一般に、 2つのエッジは、共通の頂点を共有している場合、「インシデント」です。

エッジだけでなく、頂点もエッジに入射する可能性があります。 頂点がエッジの端点の1つである場合、頂点はエッジに入射します。

したがって、2つのエッジとがあります。さらに、エッジに共通の端点頂点があると仮定します。この場合、エッジと言うことができ、偶然です。

あるいは、エッジが2つの頂点を接続している場合、そのエッジは頂点とに入射していると言われます。

前の例では、頂点がエッジとの両方の一部であることに注意してください。このような場合、頂点はエッジとに入射していると言えます。

このセクションでは、サンプルの有向グラフと無向グラフからいくつかの入射エッジを見つけてみましょう。

最初に無向グラフを取り上げます。

この無向グラフには、頂点セットとエッジセットがあります。このグラフから、エッジと頂点の間の入射関係のいくつかを見つけましょう。

同様に、グラフでエッジと頂点の間の他の入射関係を見つけることができます。

ここで有向グラフについて話しましょう：

ここで、頂点セットとエッジセットを使用した有向グラフを作成しました。エッジと頂点の間の入射関係を次のように定義することを目指しています。

基本的に、有向グラフと無向グラフの頂点とエッジの間の入射関係は同じままです。唯一の違いは、有向グラフの場合、エッジに方向があるため、別の頂点から頂点に入射することです。

グラフ理論では、頂点の次数を計算する場合、頂点に入射するエッジの数をカウントします。頂点に入射するエッジの総数は、その特定の頂点の次数です。したがって、入射エッジの概念は、頂点の次数を見つけるために使用されます。

入射エッジの概念は、グラフ理論のエッジ彩色問題で使用されます。エッジの彩色では、2つの入射エッジが同じ色にならないように、すべてのエッジを色で塗りつぶす必要があります。

入射エッジの概念のもう1つの用途は、エッジカバーの問題です。エッジカバーはエッジのセットで構成され、グラフの各頂点は、エッジカバーセットのエッジの少なくとも1つに入射する必要があります。

このチュートリアルでは、有向グラフと無向グラフの両方で入射エッジと頂点について説明しました。

さらに、いくつかの例を示し、いくつかのアプリケーションについても説明しました。