次数
グラフ理論において、頂点の次数とは、その頂点に接続された辺の本数のことを指します。
グラフ理論では、次数は頂点の重要な特徴量の1つであり、グラフの性質を表すために用いられます。
例えば、無向グラフにおいて全ての頂点の次数が偶数である場合、オイラー路と呼ばれる全ての辺を1度だけ通るパスが存在することが知られています。
問題
以下のグラフの各頂点の次数を求めて下さい。
1---2---3 / | / | 4-------5
ソースコード
以下のようにPythonコードを書くことができます。
1 | import networkx as nx |
実行すると、以下のような出力が得られます。
[実行結果]
{1: 1, 2: 3, 3: 2, 4: 2, 5: 2}
これは、頂点1の次数が1、頂点2の次数が3、頂点3の次数が2、頂点4の次数が2、頂点5の次数が2であることを示しています。