有向グラフのエッジの最大数を決定する

1. 概要

このチュートリアルでは、有向グラフのエッジの最大数を計算する方法について説明します。

グラフ理論では、グラフは一般に有向グラフまたは無向グラフに分類できます。このセクションでは、有向グラフに焦点を当てて説明します。

簡単な定義から始めましょう。グラフのすべてのエッジに方向がある場合、グラフは有向グラフです。の頂点とエッジを接続する必要があり、すべてのエッジが特定の頂点から別の頂点に向けられます。

有向グラフと無向グラフの主な違いは、到達可能性です。このステートメントを例を挙げて説明しましょう。

グラフを取りました。頂点セットには、次の5つの頂点が含まれています。のエッジセットには、次の6つのエッジが含まれています。

ここで説明したように、有向グラフでは、すべてのエッジに特定の方向があります。たとえば、エッジは頂点からにのみ移動できます。無向グラフとは異なり、エッジを介して頂点に到達することはできません。

したがって、有向グラフでは、到達可能性が制限され、ユーザーは要件に従ってエッジの方向を指定できます。

このセクションでは、最大数のエッジを含めるために有向グラフが保持する必要のあるいくつかの条件について説明します。

まず、特定の頂点から別の頂点へのエッジは最大で1つである必要があります。これにより、すべての頂点が接続され、グラフに最大数のエッジが含まれるようになります。 要するに、 有向グラフは、最大数のエッジを含むために完全グラフである必要があります。

グラフ理論では、有向グラフには多くのバリエーションがあります。簡単にするために、標準の有向グラフを検討しています。 したがって、有向グラフでは、自己ループや平行エッジは考慮しません。

このセクションでは、有向グラフに含めることができるエッジの最大数を計算するための一般式を示します。

頂点を持つ無向グラフを想定しましょう。さらに、グラフには最大数のエッジがあることも前提としています。このような場合、開始頂点からグラフにエッジを描画できます。このように続けて、次の頂点からエッジを描画できます。

したがって、無向グラフのエッジの最大数は次のとおりです。

これで、無向グラフでは、すべてのエッジが双方向になります。各エッジを2つの有向エッジに置き換えることで、無向グラフを有向グラフに変換できます。 したがって、有向グラフのエッジの最大数の式が改訂されました：

このセクションでは、有向グラフを使用して、導出した式に従ってエッジの最大数を計算します。

ここで、最大数のエッジが含まれるように、有向グラフのいくつかの条件と仮定についてすでに説明しました。まず、このグラフに最大数のエッジが含まれているかどうかを確認しましょう。

まず、完全有向グラフかどうかを確認しましょう。完全有向グラフでは、すべての頂点が互いに到達可能です。上のグラフでは、すべての頂点が互いに到達可能であることがわかります。

第二に、有向グラフでは、平行なエッジや自己ループがあってはなりません。この有向グラフの例もこの条件を満たす。それでは、エッジの計算に進みましょう。ここでの各エッジは双方向であることに注意してください。したがって、各エッジは2つの独立した有向エッジとしてカウントされます。

エッジの最大数=上記のグラフには、含めることができるすべてのエッジが含まれています。

別のグラフを見てみましょう：

このグラフには最大数のエッジが含まれていますか？確認しよう。

これを確認するには、すべての頂点が互いに到達できるかどうかを確認する必要があります。グラフで深いループをとると、単一のエッジを介して多くの頂点が互いに到達できないことがわかります。

したがって、与えられた有向グラフには最大数のエッジが含まれていないと結論付けることができます。私たちの公式によれば、このグラフには最大のエッジを含む能力があります。ただし、この例では、グラフに16個のエッジがあります。

このチュートリアルでは、有向グラフのエッジの最大数を計算する方法について説明しました。

有向グラフのエッジの最大数を計算するための一般的な式を示し、いくつかの例を使用して式を検証しました。