隣接行列電卓

隣接行列電卓

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

一目でわかる

隣接行列電卓は、グラフを隣接行列、辺のリスト、隣接リストの形式の間で変換します。有向グラフか無向グラフかを判定し、次数、密度、連結成分、行列の累乗を表示します。

隣接行列電卓の機能一覧

機能	できること	向いている用途
3つの入力形式	A-BやA->Bのような辺のリスト、A: B, Cのような隣接リスト、またはラベル付きの場合もある0/1の正方行列を貼り付けます。	グラフを教科書の形式とプログラムの形式の間で移すとき
有向か無向か	自動判定は矢印と行列の対称性を使います。または有向・無向を指定して固定できます。	行列が有向グラフを表しているかを確認するとき
次数の分析	次数の列を表示します。有向グラフでは入次数と出次数も示します。	グラフ理論の宿題や次数に基づく確認
密度と成分	グラフの密度、完全グラフか、正則か、連結かを表示し、弱連結成分も示します。	ネットワークがどれだけ疎か、または連結しているかを判断するとき
行列の累乗	A²とA³を表示します。各要素は、2つの頂点の間のその長さの歩道の数を数えます。	歩道や三角形を数えるとき
グラフの描画	インタラクティブな図で、ホバーすると対応する行、列、辺が強調されます。各表現はコピーできます。	3つの形式が同じグラフを表していることを確認するとき
サイズの上限	最大40頂点、600辺までのグラフに対応しています。	小中規模の授業用や例のグラフ

隣接行列とは何ですか？

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

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

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

計算される主な指標

次数配列

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

グラフ密度

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

密度 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 が使用可能です。明示的に有向グラフとして扱いたい場合は -> を使用してください。

2. 隣接リスト

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

3. 隣接行列

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

この電卓の使い方

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

具体例

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

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

• 対称か？ はい — 無向であることを確認。
• 次数配列: (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 などの探索アルゴリズムに適しています。

このツールは重み付きグラフを処理できますか？

現在の電卓は、0/1 エントリを持つ重みなしの隣接行列に焦点を当てています。ゼロ以外の数値の重みを持つ行列を貼り付けた場合、構造解析のためにゼロ以外のすべてのセルは 1 として扱われます。最短経路などの重み付きグラフの計算については、専用の重み付きグラフツールを検討してください。

高度な数学操作:

• 隣接行列電卓 新しい
• antilog電卓
• ベータ関数電卓
• 二項係数電卓
• 二項確率分布電卓
• ビットに基づいての電卓
• ブール代数簡略化ツール 人気
• 中心極限定理電卓
• 中国剰余定理電卓
• 組み合わせ電卓
• 相補誤差関数電卓
• 複素数電卓 人気
• 連分数電卓 人気
• 完全順列 サブファクトリアル電卓 人気
• ダイクストラ最短経路電卓
• エントロピー電卓
• 誤差関数電卓
• オイラーのトーシェント関数電卓
• 指数減衰電卓（高精度）
• 指数成長電卓 高精度
• 指数積分電卓
• 指数計算 人気
• 拡張ユークリッドアルゴリズム電卓
• 階乗電卓 人気
• ガンマ関数電卓
• 黄金比電卓
• グラフ彩色電卓 新しい
• グラフ次数列バリデーター
• 群論の位数電卓 新しい
• 半減期電卓
• ハミルトン路チェッカー 新しい
• 包除原理電卓 新しい
• カルノー図 (K-Map) ソルバー 新しい
• 線形計画法ソルバー 新しい
• マルコフ連鎖定常分布電卓
• 最小全域木電卓
• モジュラー冪乗計算機 新しい
• モジュラー乗法逆数電卓
• 負の二項分布電卓 新しい
• ネットワークフロー電卓最大フロー 新しい
• パーセント成長率電卓 人気
• 順列電卓
• 重複順列電卓 新しい
• 鳩の巣原理電卓
• 平面グラフ判定 新しい
• ポアソン分布電卓
• 多項式の根電卓と詳細なステップ
• 原始根電卓
• 確率電卓
• 確率分布電卓
• 比例式計算機
• 二次式電卓
• 環と体の電卓 新しい
• 四捨五入電卓 新しい
• 関数電卓 人気
• 科学表記法電卓
• 集合論電卓
• 有効数字電卓 新しい
• 安定結婚問題ソルバー 新しい
• スターリング数電卓
• 立方和電卓
• 正の整数の電卓
• 平方和の計算
• トポロジカルソート電卓 新しい
• 巡回セールスマン問題ソルバー TSP 新しい
• 真理値表ジェネレーター
• ベン図ジェネレーター3集合