特殊なグラフ｜ネットワーク科学

← ネットワーク科学一覧

🎓 レベル：標準　|　重要度：B（推奨）

📎 前提：次数・道・連結成分　|　関連：二部ネットワークと射影・グラフの走査

要点（BLUF）

木：連結で閉路を持たないグラフ。エッジ数はちょうど $n-1$ で、任意の2点間の道が一意。
二部グラフ：ノードを2群に分け、エッジが必ず群をまたぐもの。ユーザー×アイテムなど「2種類の対象」を表す。
完全グラフ $K_n$ ：すべての対が繋がる。エッジ数は $n(n-1)/2$ 。正則グラフ：全ノードの次数が等しい。

概念：制約が型を生む

一般のグラフに条件を課すと、扱いやすく性質の整った「型」が現れます。木・二部・完全・正則は、ネットワーク科学で最も頻出する4つの型。それぞれの制約が、計算の単純さ（木）やモデル化の対象（二部）、比較の基準（完全・正則）を決めます。

数式による定義と性質

木（tree）：連結かつ閉路を持たないグラフ。次の3つは同値です。

\text{木} \iff \text{連結で閉路なし} \iff m = n-1 \text{ かつ連結} \iff \text{任意の2点間の道が一意}

エッジを1本でも足すと閉路ができ、1本でも引くと非連結になる「ギリギリ連結」な構造です。

二部グラフ（bipartite）：ノード集合を $V = X \cup Y$ （ $X \cap Y = \varnothing$ ）に分割でき、すべてのエッジが $X$ と $Y$ をまたぐもの。同値な特徴づけとして「奇数長の閉路を持たない」があります。これは2色で塗り分け可能という性質そのものです。

完全グラフ $K_n$ ：すべての異なる2ノードがエッジで結ばれたグラフ。エッジ数は

m = \binom{n}{2} = \frac{n(n-1)}{2}

密度1の上限ケースで、密度の基準になります。

正則グラフ（regular）：すべてのノードの次数が同じ値 $k$ （ $k$ -正則）。サイクル $C_n$ は2-正則、完全グラフ $K_n$ は $(n-1)$ -正則です。

コードで確認

import networkx as nx

# 木：パスグラフ P5
T = nx.path_graph(5)
print("P5は木か:", nx.is_tree(T),
      " エッジ数:", T.number_of_edges(), "(= n-1 =", T.number_of_nodes()-1, ")")

# 二部：完全二部グラフ K(2,3)
B = nx.complete_bipartite_graph(2, 3)
print("K(2,3)は二部か:", nx.is_bipartite(B), " エッジ数:", B.number_of_edges())

# 完全グラフ K5
K5 = nx.complete_graph(5)
print("K5のエッジ数:", K5.number_of_edges(), "(= n(n-1)/2 =", 5*4//2, ")")

# 正則：サイクル C6（全ノード次数2）
R = nx.cycle_graph(6)
degs = set(dict(R.degree()).values())
print("C6は正則か:", len(degs) == 1, " 次数:", degs)

実行結果：

P5は木か: True  エッジ数: 4 (= n-1 = 4 )
K(2,3)は二部か: True  エッジ数: 6
K5のエッジ数: 10 (= n(n-1)/2 = 10 )
C6は正則か: True  次数: {2}

木はエッジ数が $n-1$ 、完全グラフは $n(n-1)/2$ 、正則グラフは全次数が一致 — 定義どおりの数値が出ています。

4つの型の関係

graph TD
    G["一般のグラフ"] --> T["木<br/>連結・閉路なし・m=n-1"]
    G --> B["二部グラフ<br/>奇数閉路なし・2色で塗れる"]
    G --> C["完全グラフ Kn<br/>全対が隣接・密度1"]
    G --> R["正則グラフ<br/>全次数が等しい"]
    C -.->|"Knは (n-1)-正則"| R

数式の直観的意味

木の $m=n-1$ は「 $n$ 個のモノを過不足なく繋ぐ最小本数」です。 $n$ 人を全員つなぐには最低 $n-1$ 本の握手が要る。これより少ないと誰かが孤立し、多いと無駄な閉路ができる。二部グラフの「奇数閉路なし」は、塗り分けを試みると奇数の輪では必ず同色隣接が生じて破綻することから来ます。

⚠️ よくある誤解・落とし穴

「閉路がなければ木」は誤り：非連結なら森（forest）。木は連結も要求します。
二部グラフ＝完全二部グラフではない：二部は「群をまたぐエッジしかない」だけ。すべての対が繋がる必要はありません。
正則だからといって対称（頂点推移的）とは限らない：次数が揃っていても、ノードの「役割」が同じとは限りません。

対応シミュレーション

本文のコードがそのまま検証用です。二部グラフの射影は二部ネットワークと射影で扱います。