隣接行列電卓

隣接行列、辺リスト、隣接リストの間で相互変換を行います。有向グラフと無向グラフを自動検出し、次数列、密度、連結成分、行列の累乗を計算。インタラクティブな SVG グラフの可視化機能も搭載しています。

隣接行列電卓

クイック例:

無向グラフ (三角形＋末尾) 有向サイクル K4 (隣接リスト) 4×4 行列数値ラベル

↔ エッジリスト ☰ 隣接リスト ▦ 隣接行列

グラフデータ

A-B, A->B, A B, A,B、または行列の行（例: 0 1 1 0）を受け付けます。頂点ラベルには英数字またはアンダースコアを使用してください。

行列ラベル (オプション)

カンマまたはスペースで区切られたラベルを入力してください（各行列の行に対応）。省略した場合は A, B, C… がデフォルトで使用されます。

グラフの種類

Embed 隣接行列電卓 Widget

隣接行列電卓

隣接行列電卓は、グラフ理論における3つの標準的な表現（隣接行列、エッジリスト、隣接リスト）を相互に変換し、次数配列、グラフ密度、連結成分、行列の累乗などの構造解析を付加するツールです。入力内容から有向グラフか無向グラフかを自動検出し、すべての結果とともにライブSVG可視化をレンダリングします。

隣接行列とは何ですか？

頂点数 n のグラフ G = (V, E) において、その隣接行列とは、頂点 i から頂点 j へのエッジがある場合に A[i][j] = 1、それ以外の場合に 0 となる n × n の正方行列 A のことです。

A[i][j] = 1 ( (v_i, v_j) ∈ E の場合 )、 0 ( それ以外 )

無向グラフの場合、隣接行列は常に対称です。すべてのエッジ {u, v} は A[u][v] = 1 と A[v][u] = 1 の両方に寄与します。有向グラフ（ダイグラフ）の場合、行列は非対称になる可能性があり、各アークの方向を反映します。

3つの表現 — 問題に適したものを選択

表現	空間計算量	エッジ検索	隣接ノードのリストアップ	適している用途
隣接行列	Θ(n²)	O(1)	Θ(n)	密なグラフ、行列代数（累乗、固有値）
隣接リスト	Θ(n + m)	O(deg v)	Θ(deg v)	疎なグラフ、BFS/DFSおよび最短経路アルゴリズム
エッジリスト	Θ(m)	Θ(m)	Θ(m)	入出力、クラスカルの最小全域木、エッジ中心のアルゴリズム

計算される主な指標

次数配列

無向グラフの場合、頂点の次数はその頂点に接続するエッジの数です（自己ループは2回カウント）。有向グラフの場合、各頂点には入次数（入ってくるアーク）と出次数（出ていくアーク）があります。次数をソートしたリストは古典的なグラフ不変量であり、グラフの同型性判定やエルデシュ・ガライの定理などで使用されます。

握手補題: Σ deg(v) = 2m (無向) Σ in-deg(v) = Σ out-deg(v) = m (有向)

グラフ密度

密度は、頂点数 n に対して可能な最大エッジ数に対し、実際にエッジがどれだけ「詰まっているか」を測定します。

無向: D = 2m / (n(n−1)) 有向: D = m / (n(n−1))

密度 0 はエッジがないことを、1 はグラフが完全であることを意味します。0.1 未満の値は通常、行列よりも隣接リストの方が空間効率が良い「疎なグラフ」であることを示します。

連結成分

連結成分とは、すべての頂点のペアがパスによって結ばれている極大な頂点の部分集合です。有向グラフの場合、この電卓は弱連結成分（矢印の方向を無視した場合の成分）を報告します。これは、各アークを無向エッジとして扱った場合に得られる部分集合と同じです。

行列の累乗 (A², A³ ... )

代数的グラフ理論の基本定理によれば、A^k の (i, j) 成分は、頂点 i から頂点 j へのちょうど長さ k のウォークの数に等しくなります。その結果として：

A²[i][i] は、頂点 i の次数に等しくなります（無向グラフの場合）。これは i から隣接頂点に行って戻る「2-ウォーク」に相当するためです。
A³ のトレース（対角和）を 6 で割った値は、無向グラフにおける三角形の数をカウントします。
Aⁿ⁻¹ にゼロのエントリがあるかどうかで、グラフが連結しているかどうかがわかります。

サポートされている入力形式

1. エッジリスト

1行に1つのエッジを入力するか、カンマで区切ります。セパレーターとして A-B, A B, A,B, A->B, A--B が使用可能です。明示的に有向グラフとして扱いたい場合は -> を使用してください。

A-B, B-C, C-A, C-D (末尾のある無向4サイクル) A->B, B->C, C->D, D->A (長さ4の有向サイクル)

2. 隣接リスト

1行に1頂点ずつ、頂点: 隣接ノード1, 隣接ノード2, ... の形式で入力します。順序は問いません。隣接リストにのみ登場する頂点も自動的に追加されます。

A: B, C, D B: A, C C: A, B, D D: A, C

3. 隣接行列

1行に1つの行を入力し、0/1 の値をスペースまたはカンマで区切ります。行列は正方行列である必要があります。オプションで「行列ラベル」フィールドにカスタムラベルを入力できます（省略時は A, B, C… が使用されます）。

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

この電卓の使い方

入力形式を選択: タブセレクターを使用して、エッジリスト、隣接リスト、隣接行列のいずれかを選択します。
グラフを入力: テキストエリアにグラフを貼り付けるか入力します。行列入力の場合は、必要に応じてラベルを入力してください。
グラフの種類を選択: 「自動検出」のままにすると、矢印 (->) や行列の対称性から有向・無向が推測されます。上書きしたい場合は明示的に指定してください。
「グラフの変換と解析」をクリック: 結果ページに隣接行列、インタラクティブなSVG可視化、他の2つのテキスト表現、次数統計、連結成分が表示されます（グラフが小さい場合は A²、A³ のウォーク数行列も表示されます）。
行列の行やグラフのノードをホバー: 対応する行/列や接続されているエッジが強調表示されます。これにより、異なる形式が同じ情報をエンコードしていることを視覚的に確認できます。

具体例

頂点 {A, B, C, D} とエッジ AB, BC, CA, CD を持つ無向グラフを考えます。隣接行列は以下の通りです：

A B C D A [ 0 1 1 0 ] B [ 1 0 1 0 ] C [ 1 1 0 1 ] D [ 0 0 1 0 ]

電卓が導き出す主な事実：

対称か？ はい — 無向であることを確認。
次数配列: (3, 2, 2, 1) — 頂点 C がハブ（中心）です。
密度: 2·4 / (4·3) = 0.667 — 中程度の密度のグラフ。
連結か？ はい、1つの成分のみ。
三角形: ちょうど1つ (A–B–C)。これは tr(A³) = 6 から確認されます。

一般的な用途

ソーシャルネットワーク分析 — 友人関係/フォロワーグラフ、中心性の測定。
ウェブおよび引用グラフ — PageRank や HITS は A および A^T 上で直接動作します。
ルーティングとネットワーク — 最短経路、最小カット、最大流。
化学 — 原子を頂点、結合をエッジとした分子グラフ。
スケジューリングと依存関係 — ビルドシステムにおける有向非巡回グラフ (DAG)。
マルコフ連鎖 — グラフから派生した行確率行列による遷移確率のエンコード。

よくある質問

隣接行列とは何ですか？

隣接行列は、有限グラフを表すために使用される n × n の正方行列です。各セル A[i][j] は、頂点 i から頂点 j へのエッジがある場合は 1、そうでない場合は 0 になります。無向グラフの場合、行列は対称になるため A[i][j] = A[j][i] となります。この行列を使用すると、2つの頂点が接続されているかどうかを一定時間で簡単に確認でき、行列の累乗は頂点間のウォークの数をエンコードします。

隣接行列からグラフが有向かどうかをどうやって判断しますか？

隣接行列が対称である場合、つまりすべてのインデックスのペアに対して A[i][j] が A[j][i] と等しい場合、グラフは無向です。A[i][j] が A[j][i] と異なるペアが少なくとも1つある場合、グラフは有向です。この電卓では、「自動検出」オプションを選択すると、その対称性チェックを自動的に実行します。

行列のk乗は何を表していますか？

行列 A^k の成分 (i, j) は、頂点 i から頂点 j へのちょうど長さ k のウォークの数をカウントします。例えば、A²[i][j] は2ステップのパスの数であり、無向グラフでは i と j の間の共通の隣接頂点の数に等しくなります。この特性は、三角形のカウント、到達可能性、PageRank スタイルの計算などのアルゴリズムで使用されます。

グラフ密度とは何ですか？

グラフ密度は、存在するエッジの数と、可能な最大エッジ数の比率です。n 個の頂点を持つ無向単純グラフの場合、密度 = 2m / (n(n-1)) です。有向グラフの場合、密度 = m / (n(n-1)) です。密度が 0 に近い場合は疎なグラフを意味し、密度が 1 の場合は完全グラフを意味します。

隣接行列と隣接リストの違いは何ですか？

隣接行列は、n² ビットを使用してすべての頂点のペアの接続性を保存するため、隣接ノードの検索は O(1) ですが、メモリ使用量は O(n²) になります。隣接リストは各頂点の実際の隣接ノードのみを保存するため、メモリは O(n + m) となり、疎なグラフでははるかに小さくなりますが、隣接ノードの検索には線形スキャンが必要です。行列は密なグラフや行列代数演算に適しており、リストは疎なグラフや BFS/DFS などの探索アルゴリズムに適しています。