グラフ理論って重要だよね

グラフマイナー定理とか面白いよね

グラフ理論って重要じゃないの？
http://science4.2ch.net/test/read.cgi/math/973368655/

　　　　　　▂▃￭◤　　　　▀◥◣　▂▂▂
　　　　◢◤　　　　　　　　　　　◥◣　▂◤
　　　 ◤　　　　　 　　　　　　　　 ▼
　　　▌　　　　　　　　　　　　　　　◥
　　　▍　　　　　　　　　　　 ▂◢ ▲▀◥◣
　　　 ◣▂　　　　　　　 ▄▅▀　 █▌　　 ◥
　　　 ▐▂ ▀◥▅￭￭▀ ▂▄▂▍ 　▍　　　　 ▍　　また即死？
　　　　■　 　 ▼▂◤　　　◥　　◣　　　▂▲
　　　　▍　　　　▍ ▍　　　　▌　　◥▅◤　　 ◥▍
　　　　▌▂　　 ◢　 ▍　　◢◤▀◥　　▂　　　　 ▍
　　　▐◤　　▀◥　　 ◥▄▲▄▂◢▍ ▐　◥　　　 ▎
　　　 ▍　　 　 　 ▂ 　◣▄▂▂◢　　 ◣▂▌　　▲
　　　　◣　　　　▐▂◢　　 　　　　　　　　　◤▀▍
　　　　　◥◣▂　　　　　　　　　　　　　　◢◤　　▀◣
　　　　 ▲　　◥◣　　　　　　　　　　　　　　　 ▐◤
　　▂◢￭▀　　　　　　　　　　　　　　　　　　　　▀◣
　　　◢▅ 　◢▍　　　　　　　　　　　　　◢▍　　　　 ▋
　◣▂◢◤　　　◣　　　　　　　　　　　　　　　　　　　　▌
◢◤　　　　　　　　　　　　　　　　　　　　　　　　　　　▍
▀▌　　　　　　　　　　　　　　　　　　　　　▐◣　　　　▍
　▍　　　　◢◤ 　　　　　　　　　　　　　　　　　　　　　▎

4色問題を解くには必須なの？

ブラフ理論は大切だ！

Robertson-Seymour-Thomas読もうと思ったんだけど
いかんせん多くて手を出すのに躊躇してしまう

グラフ理論って情報の分野では役立ちそうだけど数学内部では
離散数学以外への応用があまりなさそうなイメージがある

トポロジーの端緒としての歴史的意味は大きいのだけどねえ

グラフ理論ってグラフ作るの？
エクセルとかで？

ワードでも方眼紙は作れる。
これだからエクセル厨は・・・

いや、逆に方眼紙はワードを連想する

>>8
グラフといっても、折れ線グラフや棒グラフ、円グラフとは、
まーーーーったく関係ないぞｗ

じゃあどういうグラフなんだよ
エクセルには無いタイプか？

頂点同士が辺で繋がってるやつ。
つまり１次元のCW複体。

>>6
実際には組合せ論以外にも色々と応用されてるんだけどねえ。

たとえば、グラフから代数構造を作る手続きを設計し、
その代数構造のホモロジー群とかをグラフの言葉で述べておくと、
条件を満たす代数を構成する問題とかが楽、ってパターン。

グラフ理論、東大後期に出たよね昔

>>14
そのとき代数構造同士の関係（AはBの部分代数、とか直積とか）はグラフの言葉で言うとどうなるのですか？

直積→AはBとCの直積

>>16
グラフの直積であるとかグラフの部分グラフであるとかグラフのマイナーであるとか構成次第

>>18 いい加減な物言いだな。ちゃんとわかってて言ってるんなら、
その３つの場合それぞれについてソース出してみろよ

ヒューリスティクス　（思考や判断の簡便法）
心理的なバイアスを避け、少ない情報で効率よく判断することが出来るし、逆に判断を誤ったりする。
過去の動きを把握するには、言葉で何度も説明されるよりも､一枚のグラフを見た方が早い。

グラフ理論って化合物とかピラミッドみたいに立体とかには考えないの？
ぱらぱら眺めても全部平面で終わってる気が

>>21
平面だけではなく立体も扱いますよ
紙には立体が書けないだけです

━┃━

二本の辺がねじれの位置にあるとき普通はこんな書き方をしますが

━╋━

グラフ理論の教科書ではこう描いてしまいます
あくまでも交わってはいません
交わっているときは交点に○とか●を描きます

平面に書けるグラフなんてのはグラフのほんの一部でしかないからな
平面に交差無しで書けるかどうか、グラフを平面に書くとき最低何個の辺の交差が必要になるか、なんてのもグラフ理論のまな板に載せて解ける

ヒューリスティクス（思考や判断の簡便法）

バークリーは考えた。　人間の目、視覚と言うのは、当てにはならない。
人の目では小さくしか見えていない。
すべては（本質は）触覚でもって知ると言うのだ。

ピラミッドは視覚によっては、小さくも大きくも見えるし、
それが視覚によって何故自分の外部に存在するものだといえるのだろうか。
人が、触覚を経験せずに、そのように判断することは不可能である。

視覚とは、単に触覚のサポートのようなものであって、なんら当てになるものではないと、彼は言うのだ。

しかしどうだろう。
これは、視覚は、ヒューリスティクスといえるのである。
私達は、いちいち目に見えることによって、触ってたしかめなくても良いのだ。
大体のことは、分かるし、たまに分かっていなかったりもする。


そして数学における視覚なるものが、グラフである。

化学で考えられるグラフと
情報で考えられるグラフは微妙に違うんだろうな

結び目理論とはなにが違うの？

グラフ理論の人ってどうしてあんなに論文が沢山書けるの？

結び目（とか絡み目）は「S^3の中のS^1の磯とピーのクラス」で、
グラフ理論ってのは「高々一次元の単体複体の代数と幾何」なんじゃ
ないんでしょうか。間違ったたら誰か直して下さい。

ＬＱＧの時代が来る

ＬＰＧの間違いでしょｗ

>>21
ピラミッド型も立方体も平面で表せますからね
多くの場合平面で十分なのでしょう

その昔、朝永先生の「立体電気回路」なんてのがありましたな。
ひょっとして小谷先生でしたかね？

グラフ理論は素人なのですが

グラフの対称性を、平面図形や空間図形として表現することや、
空間図形でも表現できないものでも、n次元空間以上ではその対称性を
表現できる、というようなことを論じた本ってないですかね。
（専門ではないけどちょっと興味があるので、できれば専門的過ぎない方がよいのですが。）

たとえば、立方体の頂点と辺からなる８頂点12辺のグラフを作り、
さらにそれとは別に２点P,Qを用意して、
立方体の８頂点を交互に偶点と奇点に分けた上で
Pと偶点、Qと奇点を結ぶ計８本の辺を追加すると、
10頂点20辺のグラフができますが、
これって、グラフとしてはどの頂点からみても同じつながり方を
してますよね。こいつの対称性をn次元空間に埋め込んで
うまく表現できないか、とか。

グラフの対称性の体系的な分類とかもあれば．．．。

全部が繋がってるヤツは「ハイパーキュービック」とか言うじゃないですか。
だから「そんなの」はちゃんとした埋め込み（イマーションじゃなくって）なの
は当然に「次元の制約」がきっと付くんでしょうかね、そんなんはもう既に
「ある」のかも知れませんが。そんなら「ホイットニーの埋蔵定理」みたいな
次元勘定とかがありませんかねぇ

>>34
おまえには聞いてない

>>34
>>33で例として挙げたグラフは、n次元超立方体の頂点と辺からなるグラフには
埋め込めないようですが．．．。
それ以外のお話はよくわかりません。

いやいや、それは「エッジの数」が物凄く沢山あるからそうは行かないですよ。
そんで「ペラペラになる」のはハイパボリックとかオートマティックとか、「そんな
ケース」でしょうから、普通に考えるとアンビエントの次元は（かなり）大きい様
な気がしますが、まあ「ド素人の意見」という訳です

>>34
それと、
>全部が繋がってるヤツ
というと、グラフ理論の文脈では完全グラフのことかと思うのですが、
それと超立方体との関係がわかりません。
n次元の単体であれば、たしかに頂点と辺からなるグラフが
n+1点からなる完全グラフになりますが・・・。

確かに「そんな感じ」ですねぇ。超立方体ってのは、まあ「球面」みたいなモン
でしょ。だからinductiveにはsuspensionで次元を順次上げて行くみたいな
感じですよね。だから当然に「アンビエントの次元」は上がりますよね。それで
「球面は曲率が正」だから、次元は「ちょびっとだけ」上がるんですかね？

189

グラフのラプラシアンとかぶっちゃけラプラシアンとは言えない

いや、ワシはかなり似てると思いますね
ソレに数論とか表現論とか色々あるから
面白いじゃないですか。

山本君はグラフそのもの

人間はグラフ

グラフ理論は色々応用できそうね；∨；

グラフ理論と数論幾何って接点はないのかな

グラフ理論と代数幾何の接点ならある
グラフからトーリック多様体を構成する方法がある
http://arxiv.org/abs/math/0606683

Serreが木の本書いてなかった？

＞47

すばやいレスども
2ｃｈにもたまには物知りがいるね

>>49
貴方のレスする30分前にトーリック多様体を調べてただけなんだよね

グラフはこれから

いまいち注目されませんな

ああ、そう。でも何でやねん？

猫

トーリックよりトーイックの点数の方が重要だな。

ピーターフランクルが専門の極値集合論は注目されているのだろうか。
単に数学オリのネタになるだけのもんかな。

ドラマのブラマンでグラフ出ていたお

>>54
おお、そうかァ。オマエはちゃんと英語が出来るんやナ。
ほんで何点あんねん？　言うてみいや、ワシが判定したるがな！

猫

頂点数可算個のグラフの同型類の種類の濃度は幾つ

重要

グラフで表現することは多くなったよな。

四色定理の証明のプログラムは簡単になったのですか？
プログラムそのものが大量にありすぎて読む気がしないなんて、
数学としてはちょっとね。

数式が多すぎて論文読めない俺が通りますよ

有限単純群の分類の証明だってプログラムを使うようにすれば
証明にかかるページ数が1/10くらいになるんじゃとか思ったりする

525

グラフ構造は宇宙

電子(電気)工学の回路理論では必須ですなぁ。
まぁ、象牙の塔ではともかくとして、電気会社の設計部門では、とりあえずは、
あんまり関係ないけど。いやいや、どうして、あるのかな？

由美かおる

由美かおるって数学辞典に乗るのですね／

>>66
むしろ、情報工学で必須。

>>68
そりゃ岡潔が女神と崇めてたひとだからな．

>>70
女神じゃない、アマテラスだ

コンパイラの理論なんかにもグラフ表現が出てくるよな。
グラフ理論は数理工学とか情報工学の分野で重宝されておるようやね。

今年度の京都賞を離散数学の大御所ロバース教授が受賞！
http://www.inamori-f.or.jp/ja_kp_lau_thi.html

>>72
　実は、経済学や文化人類学や社会学や心理学等にも貢献している。
　ありがたい存在です。

>>72
　数理工学や情報工学では、無いと死ぬ位ありがたい存在。

応用範囲が広くなりすぎたようやな。
わしが高校生やった頃はＯＲと回路への応用が主流やった。

さすがに現代の学生でグラフ理論と聞いて棒グラフや折れ線グラフを連想する奴はおらんよな。

パズル好きにオイラーグラフって言っても一筆書きのことだとは理解してもらえぬ世。

（´･ω･`）

グラフ構造って、色々応用できるよね。

グラフ同型性判定アルゴリズムは汎用性が高そうだな。
でもいまだにどの計算量のクラスに属するかよくわかっておらんようだ。

無限次元のグラフ環って産業界で重宝されてますか？

今のコンピュータの、基本設計を変えるには
グラフ理論が必要そうだ。

あと、ケータイ、通信の電波、ケーブルの効率化に
グラフ理論は必須

あと、東京の地下鉄は込み入っててよくわからん
グラフ理論による、効率化が必要だ。

あと脳科学の研究も、
脳ってのは、脳の神経ネットワークの回路の型が大事そうだから

グラフ理論が重要である。

グラフ理論と束論は関係ある。
あと有限集合の位相をとるアルゴリズムで、
グラフ理論の定理を使って最適化するものがあった。

941