次数（NetworkX）

次数

グラフ理論において、頂点の次数とは、その頂点に接続された辺の本数のことを指します。

グラフ理論では、次数は頂点の重要な特徴量の1つであり、グラフの性質を表すために用いられます。

例えば、無向グラフにおいて全ての頂点の次数が偶数である場合、オイラー路と呼ばれる全ての辺を1度だけ通るパスが存在することが知られています。

問題

以下のグラフの各頂点の次数を求めて下さい。

   1---2---3
      /    |
     /     |
   4-------5

ソースコード

以下のようにPythonコードを書くことができます。

1
2
3
4
5
6
7
8
9
import networkx as nx

# グラフを作成する
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (2, 4), (4, 5), (5, 3)])

# 各頂点の次数を計算する
degrees = dict(G.degree())
print(degrees)

実行すると、以下のような出力が得られます。

[実行結果]
{1: 1, 2: 3, 3: 2, 4: 2, 5: 2}

これは、頂点1の次数が1、頂点2の次数が3、頂点3の次数が2、頂点4の次数が2、頂点5の次数が2であることを示しています。