グラフ¶
グラフの種類¶
- 完全グラフ
- スター
- 2部グラフ
- K正則グラフ
- 隣接行列がブロック行列的なやつ
- m個頂点で1つの頂点とみなし(倍化)、辺はすべての頂点同士をつなぐ
- (ハイパーグラフ？)
- 名称のあるグラフのギャラリー(wikipedia)
ラベルあり/ラベルなし¶
- ラベルありグラフ
- https://oeis.org/A006125 (ラベルありグラフの数)
- 各辺についてあるかないかなので、2^(N*(N-1)/2)
- https://oeis.org/A001187 (連結な場合)
- N個のラベルあり頂点を持つ木の個数は、n^(n-2)
- Cayley's formula
- プリューファ列が一対一対応する
- https://kyopro.hateblo.jp/entry/2019/01/16/200456
- https://oeis.org/A006125 (ラベルありグラフの数)
- ラベルなしグラフ
- https://oeis.org/A000088 (ラベルなしグラフの数)
- https://oeis.org/A004251 (次数列の場合。N=5から同じになってしまうものができてしまう)
ラベルなしグラフの生成(enumeration of unlabeled graphs)¶
- N-1頂点のラベルなしグラフに1頂点を追加するような感じで生成すると、N=8,9あたりで分や時間オーダーになってしまう
ラベルなしグラフの同型判定¶
- ラベルの付け方N!通りについて、辺の有無をチェック O(N! N^2)
- https://atcoder.jp/contests/abc232/tasks/abc232_c
- (N=8,9ぐらいが限界)
- VF2アルゴリズム
連結判定、連結を保って〜¶
- UnionFind、BFS
- 関節点(LowLink)
- 木構造で、ある2頂点をつないで、その頂点からDFSでサイクルを見つけて、サイクル上の任意の1辺を削除すると別の木構造が得られる
燃やす埋める¶
- https://www.slideshare.net/shindannin/project-selection-problem
- https://koyumeishi.hatenablog.com/entry/2021/01/14/052223
最大クリーク¶
- MaxCliqueSearch
- A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
- A Much Faster Algorithm for Finding a Maximum Clique with Computational Expertiments
次数列からグラフ生成¶
- Havel-Hakimi algorithm
- https://kopricky.github.io/code/Academic/random_graph_generator.html
- Efficient and simple generation of random simple connected graphs with prescribed degree sequence
- https://twitter.com/komora71_/status/1594278415850356737
- https://kopricky.github.io/code/Academic/random_graph_generator.html