Hatena::Grouptopcoder

not's memo

 | 

2014-06-08

グラフ理論用語集

21:04 | はてなブックマーク - グラフ理論用語集 - not's memo

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

(まだ書いてる途中)

グラフ

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

辺(edge)

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

頂点(node)

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

パス

  • 最短経路

閉路

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

集合

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

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

フロー

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

DAG

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