not's memo

グラフ理論用語集

21:04 |

競技プログラミングはじめた頃に「グラフ理論の用語わからんのじゃ」ってなった記憶があるのでまとめてみた

（まだ書いてる途中）

グラフ

• 完全グラフ
• 二部グラフ
• 平面グラフ
• 補グラフ
• 星
• 彩色数
• オイラーツアー
• 森

辺(edge)

• 有効辺
• 無向辺
• 多重辺
• 隣接行列
• 隣接リスト

頂点(node)

• 根
• 葉
• 次数
• 入次数
• 出次数
• 孤立点

パス

• 最短経路

閉路

• 負閉路
• ハミルトン閉路

集合

• クリーク
• 連結
• 非連結
• 最大マッチング
• 最小辺カバー
• 最大独立集合
• 最小点カバー

木

• 最小全域木
• シュタイナー木
• 最小祖先

フロー

• 最大流
• 最小費用流
• 逆辺
• 二部マッチング
• 最小カット

DAG

• トポロジカルソート
• 最小パス被覆
• 強連結成分分解

ツイートする