パズルから定理証明まで、無料で学べるグラフ理論の教科書
Start Doing Graph Theory
『Start Doing Graph Theory』は、パズルを解いたり定理を証明したりと、幅広い目的にグラフ理論を活用するための入門教科書。Creative Commonsライセンスの下で無料公開されており、オンラインでもPDFでも読める。第1章から読み始められる。
『Start Doing Graph Theory』は、パズルを解き、定理を証明し、その間のあらゆることにグラフ理論を使うための入門教科書です。
HNでの議論
103- gortok
1年前には想像すらしなかった問題は、本が人間によって書かれたかどうかということだ。
この著者はそのような精査を受ける理由は何もしていないが、オンラインで比較的短い歴史（このテキストの最も早いバージョンは2026年春）を持つ新しい本を見ると、それが「AI強化」なのかAIが書いたのか確信が持てないため、警戒しなければならないという感覚から逃れられない。
この感覚は好きではないし、かつてこのようなものに興奮していた気持ちを削いでしまう。
それはさておき、もし著者がAIなしで自分で書いたのなら、彼らとその成果に賛辞を送りたい！
- mcv
ここ数年、グラフを使った仕事をたくさんしてきた。基本的にはneo4jを使い始めてからだが、すべてが直接neo4jに関わるわけではない。いくつか本当に面白いグラフアルゴリズムを開発したが、グラフ理論の知識があまり役立たないことにいつも少しがっかりする。ハミルトンパスが必要だったことも、頂点の次数で何かをする必要もなかった。すべては論理と直感だけだ。
しかし、現在の仕事に応用できるものがあるかどうか、これを読んでみるべきかもしれない。
- basil
私は何年もプロとしてグラフ理論を使ってきた。グラフ理論の実用的な使用例の良い例は、あらゆるルーティングソフトウェアだ。基本的にすべてがグラフでできている。
まず、街路ネットワーク全体が有向グラフとして表現される。最も広く使われているアルゴリズムは由緒あるA*で、グラフの頂点を通る経路を見つける。必ずしも最短距離ではなく、定義したヒューリスティックに基づいて望むすべてのトレードオフを考慮した最適距離を見つける。A*には多くのバリエーションがあり、今日のほとんどの実装はその高速な従兄弟である双方向A*を使い、ポイントツーポイントの計算を両端から同時に攻める。
次に、フラッド探索に使われるダイクストラ法がある。たとえば、各頂点から家に戻る最良のコストを返し、探索予算がある場合にいつ探索を打ち切るべきかがわかる。
メンガーの定理は、ループバックを作成できるかどうかを判断するために使った。基本的には外側に探索し、その後同じエッジを訪れずに戻る探索をする。
Tarjanは、すべてのサブネットワークを特定し、より広いネットワークに参加する方法のない孤立した頂点の島で行き詰まらないようにするために使う。
これらのアルゴリズムの多くは数十年前に考案され、今でも現代のルーティングソフトウェアのバックボーンだ。
常に頭の片隅にあるのは、ルーティングは高度に決定論的な問題空間なので、LLMがこれを引き継ぐことができるとは思えないということだ。これはLLMが […] の良い例のように思える。
- elxr
美しいウェブサイトで、こうした教科書によくあるgitbook/vitepressの典型的なスタイルと比べて新鮮な空気だ。
- armcat
グラフは素晴らしい - Google検索を支えた（今もある程度は支えている）PageRank[1]、抽出型テキスト要約のためのTextRank[2]、近傍検出のためのLouvain[3]はすべてグラフを使っているし、他にも信念伝播、マルコフクラスタリング、A*など山ほどある。だからまあ、学ぶべきだ。
[1] https://en.wikipedia.org/wiki/PageRank
- hackerbrother
いいね。求職中なのだが、「Leet Code」の質問のペースでグラフ理論が人気のようだ。とてもタイムリー、ありがとう！そして賢いドメイン名だね :)
- lopsotronic
グラフ理論（およびそのネットワーク理論への応用）の非常に非常に有用だが過小評価されている[1]応用の一つ：部品データシステムの構成管理。
ハードウェア製造の現場、特に新規または「ガレージ」的な店舗で多くの新規ビジネスを行っていると、「構成が多すぎる」という悪夢のようなシナリオにすぐに陥り、「人々が私たちのものを買いすぎている」という問題に真っ向から突き当たる。ガレージショップとしては、あらゆる種類の5〜6ユニットを作るのは問題ないが、1000、10000の注文が入り始めると、それらすべてのラインを運用し続ける複雑さに足元をすくわれる。最終的には何かを台無しにし、減点されたり、ブラックリストに載ったりする（防衛分野では大問題）。
しかし、これは部品データシステムにグラフ理論を適用することで回避できる問題だ。一部のPDMは実際にこれをネイティブに実行している - Oleg ShilovitskyのOpenBOM、Yoann MaingonのGanister、どちらも賢い人たちで彼らの製品を買おう！ - しかし、このネットワーク理論はどんな大きな馬鹿げたPDMの上にもレポーティングレイヤーとして使える。
例としては：
（以前使ったスライドからのAsciidocテーブル、すみません）
|===
| 方法 | 主な用途
| 入次数中心性 | 共有/高リスクコンポーネント
| 出次数中心性 | 複雑なアセンブリ
| 媒介中心性 | 変更リスク
| 近接中心性 | アーキテクチャ中心性
| PageRank | 戦略的コンポーネント
| 次数分布 | アーキテクチャの健全性 / べき乗則チェック
| 連結成分 | 孤立したものを見つける
| Sh […]
- ianbooker
https://vertex.degree/beginning/degrees#the-hypercube-graphs
超立方体の構築を紹介されたときの正確な場所を、大学のカフェテリアの正確なベンチまで、今日でも覚えている。それは多次元性についての私の理解を完全に変えた。