頂点の入次数と出力次数を理解するには、まず頂点の次数の概念について学ぶ必要があります。その後、頂点の入次数と出次数を簡単に理解できるようになります。入次数と出次数は有向グラフでのみ決定できることを知っておく必要があります。無向グラフを利用して頂点の次数を計算できます。無向グラフでは、頂点の入次数と出力次数を計算できません。
頂点の次数
グラフ内の各頂点の次数を見つけたい場合、この場合、特定の頂点と他の頂点によって確立される関係の数を数えなければなりません。言い換えれば、頂点に接続するエッジの数を計算することで、頂点の次数を決定できます。頂点の次数は deg(v) を使用して示されます。 n 個の頂点を含む単純なグラフがある場合、この場合、任意の頂点の次数は次のようになります。
Deg(v) = n-1 ∀ v ∈ G
頂点には、それ自体を除くグラフ内の他のすべての頂点とともにエッジを形成する機能があります。したがって、単純なグラフでは、頂点の次数はグラフ内の頂点の数から 1 を引いた値でわかります。ここでは、それ自体がループを作らないため、自己頂点に 1 が使用されます。グラフに自己ループを持つ頂点が含まれる場合、そのタイプのグラフは単純なグラフではなくなります。
例：
この例では、6 つの頂点 (a、b、c、d、e、f) を持つグラフがあります。頂点 'a' は次数 5 を持ち、他のすべての頂点は次数 1 を持ちます。頂点の次数が 1 である場合、そのタイプの頂点は '終了頂点' として知られます。
頂点の次数を考慮できるグラフには 2 つのケースがあり、次のように説明されます。
- 無向グラフ
- 有向グラフ
ここでは、有向グラフの頂点の次数と無向グラフの頂点の次数について詳しく学習していきます。
無向グラフの頂点の次数
無向グラフがある場合、このタイプのグラフには有向エッジは存在しません。無向グラフの頂点の次数を決定する例を以下に示します。
例 1: この例では、無向グラフを考えます。次に、そのグラフの各頂点の次数を調べます。
解決： 上記の無向グラフには、頂点の数が a、b、c、d、e の合計 5 つあります。各頂点の次数は次のように説明されます。
- 上のグラフには、頂点 'a' で交わる 2 つのエッジが含まれています。したがって、Deg(a) = 2
- このグラフには 3 つのエッジが含まれており、頂点 'b' で交わります。したがって、Deg(b) = 3
- 上のグラフには 1 つのエッジが含まれており、頂点 'c' で交わります。したがって、Deg(c) = 1 となります。頂点 c はペンダント頂点とも呼ばれます。
- 上のグラフには 2 つのエッジが含まれており、頂点 'd' で交わります。したがって、Deg(d) = 2 となります。
- 上のグラフには、頂点 'e' で交わるエッジが 0 つ含まれています。したがって、Deg(a) = 0 となります。頂点 e は、孤立頂点とも呼ばれます。
例 2: この例では、無向グラフを考えます。次に、そのグラフの各頂点の次数を調べます。
解決： 上記の無向グラフには、頂点の数が a、b、c、d、e の合計 5 つあります。各頂点の次数は次のように説明されます。
頂点の次数 a = deg(a) = 2
頂点の次数 b = deg(b) = 2
頂点の次数 c = deg(c) = 2
頂点の次数 d = deg(d) = 2
頂点の次数 e = deg(e) = 0
このグラフにはペンダント頂点はなく、頂点 'e' は孤立した頂点です。
有向グラフの頂点の次数
グラフが有向グラフの場合、このグラフの各頂点には入次数と出力次数が必要です。有向グラフがあるとします。このグラフでは、次の手順を使用して、頂点の入次数、出次数、および次数を見つけることができます。
頂点の次数
頂点の入次数は、v を含むエッジの数として記述できます。v は終端頂点を示すために使用されます。言い換えれば、頂点に来る多数のエッジとして説明できます。 deg 構文の助けを借りて-(v)、頂点の入次数を書くことができます。頂点の入次数を決定したい場合は、頂点で終わるエッジの数をカウントする必要があります。
頂点の出次数
頂点の出次数は、v を持つエッジの数として記述できます。ここで、v は最初の頂点を示すために使用されます。換言すれば、頂点から出てくる多数のエッジと表現できます。 deg 構文の助けを借りて+(v)、頂点の出次数を書くことができます。頂点の出次数を決定したい場合は、頂点から始まるエッジの数をカウントする必要があります。
頂点の次数
頂点の次数は deg(v) を使用して示されます。これは、頂点の次数と頂点の次数を加算したものと等しくなります。頂点の次数の記号表現は次のように説明されます。
Deg(v) = deg-(v) + deg+(v)
例 1: この例では、グラフがあり、各頂点の次数を決定する必要があります。
解決： このために、最初に頂点の次数、頂点の入次数、次に頂点の出力次数を調べます。
Javaリストノード
上のグラフには、合計 6 つの頂点 (v1、v2、v3、v4、v5、v6) が含まれていることがわかります。
インディグリー:
頂点の次数 v1 = deg(v1) = 1
頂点の次数 v2 = deg(v2) = 1
頂点の次数 v3 = deg(v3) = 1
頂点の次数 v4 = deg(v4) = 5
頂点の次数 v5 = deg(v5) = 1
頂点の次数 v6 = deg(v6) = 0
出次数:
頂点の出次数 v1 = deg(v1) = 2
頂点の出次数 v2 = deg(v2) = 3
頂点の出次数 v3 = deg(v3) = 2
頂点の出次数 v4 = deg(v4) = 0
頂点の出次数 v5 = deg(v5) = 2
頂点の出次数 v6 = deg(v6) = 0
頂点の次数
上で説明した定義の助けを借りて、頂点の次数 Deg(v) = deg であることがわかります。-(v) + あなた+(v)。次に、この式を使用して次のように計算します。
頂点の次数 v1 = deg(v1) = 1+2 = 3
頂点の次数 v2 = deg(v2) = 1+3 = 4
頂点の次数 v3 = deg(v3) = 1+2 = 3
頂点の次数 v4 = deg(v4) = 5+0 = 5
頂点の次数 v5 = deg(v5) = 1+2 = 3
頂点の次数 v6 = deg(v6) = 0+0 = 0
例 2:
この例では、7 つの頂点を持つ有向グラフがあります。頂点 'a' には、外側に向かう 2 つのエッジ、つまり 'ad' と 'ab' が含まれています。したがって、頂点 'a' には出力次数 2 が含まれます。同様に、頂点 'a' にもエッジ 'ga' があり、この頂点 'a' に向かって近づいています。したがって、頂点 'a' には次数 1 が含まれます。
リソース割り当てグラフ
解決： 上記のすべての頂点の入次数と出力次数は次のように説明されます。
インディグリー:
頂点の次数 a = deg(a) = 1
頂点の次数 b = deg(b) = 2
頂点の次数 c = deg(c) = 2
頂点の次数 d = deg(d) = 1
頂点の次数 e = deg(e) = 1
頂点の次数 f = deg(f) = 1
頂点の次数 g = deg(g) = 0
出次数:
頂点の出次数 a = deg(a) = 2
頂点の出次数 b = deg(b) = 0
頂点の出次数 c = deg(c) = 1
頂点の出次数 d = deg(d) = 1
頂点の出次数 e = deg(e) = 1
頂点の出次数 f = deg(f) = 1
頂点の出次数 g = deg(g) = 2
JavaScript 演算子
各頂点の次数:
頂点の次数 Deg(v) = deg であることがわかっています。-(v) + あなた+(v)。次に、この式を使用して次のように計算します。
頂点の次数 a = deg(a) = 1+2 = 3
頂点の次数 b = deg(b) = 2+0 = 2
頂点の次数 c = deg(c) = 2+1 = 3
頂点の次数 d = deg(d) = 1+1 = 2
頂点の次数 e = deg(e) = 1+1 = 2
頂点の次数 f = deg(f) = 1+1 = 2
頂点の次数 g = deg(g) = 0+2 = 2
例 3: この例では、5 つの頂点を持つ有向グラフがあります。頂点 'a' には、外側に向かう 1 つのエッジ、つまり 'ae' が含まれています。したがって、頂点 'a' には 1 の出次数が含まれます。同様に、頂点 'a' にもエッジ 'ba' があり、この頂点 'a' に向かって近づいています。したがって、頂点 'a' には次数 1 が含まれます。
解決： 上記のすべての頂点の入次数と出力次数は次のように説明されます。
学位内
頂点の次数 a = deg(a) = 1
頂点の次数 b = deg(b) = 0
頂点の次数 c = deg(c) = 2
頂点の次数 d = deg(d) = 1
頂点の次数 e = deg(e) = 1
出次数:
頂点の出次数 a = deg(a) = 1
頂点の出次数 b = deg(b) = 2
頂点の出次数 c = deg(c) = 0
頂点の出次数 d = deg(d) = 1
頂点の出次数 e = deg(e) = 1
各頂点の次数:
頂点の次数 Deg(v) = deg であることがわかっています。-(v) + あなた+(v)。次に、この式を使用して次のように計算します。
頂点の次数 a = deg(a) = 1+1 = 2
頂点の次数 b = deg(b) = 0+2 = 2
頂点の次数 c = deg(c) = 2+0 = 2
頂点の次数 d = deg(d) = 1+1 = 2
頂点の次数 e = deg(e) = 1+1 = 2
例 4: この例では、グラフがあり、各頂点の次数、入次数、および出次数を決定する必要があります。
解決： このために、最初に頂点の入次数を見つけてから、頂点の出次数を見つけます。
Javaの同等のインターフェース
上のグラフには、合計 8 つの頂点 (0、1、2、3、4、5、6) が含まれていることがわかります。
インディグリー:
頂点の次数 0 = deg(0) = 1
頂点の次数 1 = deg(1) = 2
頂点の次数 2 = deg(2) = 2
頂点の次数 3 = deg(3) = 2
頂点の次数 4 = deg(4) = 2
頂点の次数 5 = deg(5) = 2
頂点の次数 6 = deg(6) = 2
出次数:
頂点の出次数 0 = deg(0) = 2
頂点の出次数 1 = deg(1) = 1
頂点の出次数 2 = deg(2) = 3
頂点の出次数 3 = deg(3) = 2
頂点の出次数 4 = deg(4) = 2
頂点の出次数 5 = deg(5) = 2
頂点の出次数 6 = deg(6) = 1
各頂点の次数:
頂点の次数 Deg(v) = deg であることがわかっています。-(v) + あなた+(v)。次に、この式を使用して次のように計算します。
頂点の次数 0 = 度(0) = 1+2 = 3
頂点の次数 1 = 度(1) = 2+1 = 3
頂点の次数 2 = deg(2) = 2+3 = 5
頂点の次数 3 = deg(3) = 2+2 = 4
頂点の次数 4 = deg(4) = 2+2 = 4
頂点の次数 5 = deg(5) = 2+2 = 4
頂点の次数 6 = deg(5) = 2+1 = 3
グラフの次数シーケンス
グラフの次数シーケンスを決定するには、まずグラフ内の各頂点の次数を決定する必要があります。その後、これらの度を昇順に書いていきます。この順序/順序は、グラフの次数順序と呼ぶことができます。
例えば： この例では、頂点が 3、4、5 ある 3 つのグラフがあり、すべてのグラフの次数シーケンスは 3 です。
上のグラフには頂点が 3 つあります。このグラフの系列の次数は次のように記述されます。
上のグラフには頂点が 4 つあります。このグラフの次数シーケンスは次のように説明されます。
上のグラフには頂点が 5 つあります。このグラフの次数シーケンスは次のように説明されます。