グラフ理論入門 | DevelopersIO

こんにちは、ドイツのモナでございます〜 いろんなサイエンスにおいてグラフ理論がとても重要な用具となっていますが、グラフ理論ってそもそも何なのかご存知ない方も少なくもないですね。 ということで、今日は簡単にグラフ理論の基本や用語など紹介したいと思います！なお、入門のため誰にでも分かるように数学的な定義は避けるようにします。 また、グラフ理論の応用は別の話ですので今回は応用の話しません〜 なぜグラフが面白いのか 具体的な応用の話はしませんが、たくさんの分野においてグラフ理論が重要となっています。 ネットワーク（例：トポロジー、ルーティングアルゴリズム） AI（例：ニューラルネットワーク） コンピューターサイエンス（例：ファイルシステム） 社会科学（例：ソーシャルネットワーク分析） 皆さんの生活の中（例：カーナビの最短ルートの計算） グラフ理論とは？ ここで議論するグラフというのは、よく思い浮か

[uunfo]

だいたい理論まで行かずに言葉の定義で終わるのがグラフ理論／もう辺や頂点とは言わないのかな

[punychan]

まあ、辺重み付きグラフで最短経路を求めよとかやっているうちは全然面白くなくて、現実の最適化問題をモデル化したら、これクリーク分割問題と等価でintractableやんけ、うげーー、とかなってからが本番。

[hevohevo]

僕も好き。学生時代に「1年生は0.9の確率で進学し0.1で留年、2年生は・・・。では1年生がストレートで卒業できる確率は」みたいな課題出されて、えぇ？と思いながら解いた思い出。

[ewq]

修士のテーマがグラフ理論だったので懐かしい。SIerじゃなくweb系に就職してれば今もやってたかもなー。

[andonut146]

集合論とグラフ理論、ほとんど同じような式と陳述で淡々と進んでいくモノクロな学問という記憶があります。楽しいとか微塵もなかったよ…。

[eller]

「最短経路の本－レナのふしぎな数学の旅」で見た。応用としてはControl Flow Graphとかがおすすめですね（我田引水）

[kura-2]

こういう絵をみると単体的複体とかホモトピー、ホモロジーやってたころの記憶を思い出す

[richard_raw]

基本的な定義は分かった（気がする）。ここからどう進めば……？

[toitoitoi2718]

入門以前

[swdrsker]

グラフ理論によって何がどう解決出来るようになるのかを知りたい

[hamamuratakuo]

なんで今グラフ理論が注目されてるんだろ？（何かきっかけがあったのかな？）次は「圏論」をお願いします。

[natu3kan]

現実に落とし込むとクッソめんどくさくなるヤツ

[aox]

魔法陣ぽいですね

[samu_i]

3色では塗り分けできない定理を判例をだして証明すれば、証明したことになるな！

[mn_kun]

Map equationとかLouvain methodとか実装してました

[crexist]

懐かしい。教授が結婚問題の解説をした後、実際の結婚はこんなきれいに片付かないんですけどね、ということを呟いてたのを思い出した

[for-my-internet-demo]

このへんしゅしゅっとモノにしたいんだけど先に実用時のインフラから気になりだすという

[ad2217]

「最短経路の本 レナのふしぎな数学の旅」がよい。

[xlc]

30数年前、ダイクストラ法で最短経路を解く卒論を書いた友人は、民営化したばかりのJRに就職し、過密ダイヤの危険性にウンザリして退職したのであった。

[timetosay]

オイラー！オイラー！

[onesplat]

入門まで行ってない

[steel_eel]

グラフ理論、頑張って学ぼうと思ったことが何回もあるがいまだにここに書かれてること+αくらいしかわからんわ……。

[kiyo_hiko]

昔マグロウヒルで読んだけど道だの小道だの遠足みたいな字面が出てきて用語にほっこりしながら進めた思い出

[kabakiyo]

一筆書きができる条件とかもあったよね。

[aroechan]

興味持ったらヨビノリのグラフ理論の動画も見よう。パーティ問題はおもろいで

[misshiki]

グラフ理論の基礎の基礎。

[MetaVariable]

少しの用語と概念の解説だけで続きもないので、これだけブックマークしていても何もならなさそう（何処かにいい教材ないかな）

[hazardprofile]

2ページ目がなかった　早稲田の講義が公開になっててこれで足るんじゃない https://youtu.be/d0KPWURyFIs 目的がCSならCS向けのがいいけどダイクストラ法を実装したら状態遷移とか形式言語とか書いてあるヤツ探して移動？

[finefinethankyou]

ディープラーニングがグラフにも適用されて応用範囲が広がっている

[irimo]

ニューロンを模した（あくまで模した）ものをグラフ理論と呼ぶこと、ルーティングアルゴリズムもグラフ理論を使っているということ、知らなかった。

[t-sat]

「とある」が気になる。命題を述べる時に「と」はいらんよな。/では、どういう時に使うのかと言われると、気分…?

[m_ogawa]

グラフって図や概念は分かりやすいけどコーディングしようとすると途端に難しくなるイメージ。私生活で使う機会あんま無いので競プロやって手癖化したい…。