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

0001１３２人目の素数さん

2009/04/06(月) 01:49:36

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

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

0002１３２人目の素数さん

2009/04/06(月) 02:59:24

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

0003１３２人目の素数さん

2009/04/06(月) 03:49:31

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

0004１３２人目の素数さん

2009/04/06(月) 04:01:38

ブラフ理論は大切だ！

0005１３２人目の素数さん

2009/04/06(月) 04:17:07

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

0006１３２人目の素数さん

2009/04/06(月) 09:44:57

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

0007１３２人目の素数さん

2009/04/06(月) 10:09:49

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

0008１３２人目の素数さん

2009/04/08(水) 00:12:26

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

0009１３２人目の素数さん

2009/04/08(水) 01:09:47

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

0010１３２人目の素数さん

2009/04/08(水) 06:40:32

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

0011１３２人目の素数さん

2009/04/12(日) 00:23:55

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

0012１３２人目の素数さん

2009/04/13(月) 22:48:13

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

0013１３２人目の素数さん

2009/04/13(月) 22:53:49

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

0014１３２人目の素数さん

2009/04/13(月) 23:00:31

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

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

0015１３２人目の素数さん

2009/04/17(金) 22:37:50

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

0016１３２人目の素数さん

2009/04/17(金) 23:33:27

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

0017１３２人目の素数さん

2009/04/17(金) 23:49:23

直積→AはBとCの直積

0018１３２人目の素数さん

2009/04/18(土) 02:09:19

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

0019１３２人目の素数さん

2009/04/18(土) 16:44:30

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

0020ユビー ◆6wmx.B3qBE

2009/04/25(土) 07:44:37

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

0021１３２人目の素数さん

2009/04/25(土) 15:53:34

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

0022１３２人目の素数さん

2009/04/25(土) 16:29:39

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

━┃━

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

━╋━

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

0023１３２人目の素数さん

2009/04/25(土) 21:18:34

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

0024ユビー ◆6wmx.B3qBE

2009/04/27(月) 04:34:43

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

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

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

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

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

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

0025１３２人目の素数さん

2009/04/27(月) 06:37:52

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

0026１３２人目の素数さん

2009/05/04(月) 16:10:41

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

0027１３２人目の素数さん

2009/05/21(木) 22:33:30

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

0028猫でつ ◆ghclfYsc82

2009/05/21(木) 22:52:08

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

0029１３２人目の素数さん

2009/05/21(木) 23:52:42

ＬＱＧの時代が来る

0030猫の感覚 ◆ghclfYsc82

2009/05/22(金) 00:28:08

ＬＰＧの間違いでしょｗ

0031１３２人目の素数さん

2009/05/22(金) 00:45:44

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

0032猫の記憶 ◆ghclfYsc82

2009/05/22(金) 01:00:12

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

0033１３２人目の素数さん

2009/05/22(金) 01:51:44

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

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

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

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

0034猫でつ ◆ghclfYsc82

2009/05/22(金) 02:42:21

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

0035１３２人目の素数さん

2009/05/22(金) 02:54:50

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

0036１３２人目の素数さん

2009/05/22(金) 03:46:27

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

0037猫は良く判りませんが ◆ghclfYsc82

2009/05/22(金) 04:01:38

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

0038１３２人目の素数さん

2009/05/22(金) 04:09:53

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

0039猫は素人です ◆ghclfYsc82

2009/05/22(金) 04:26:07

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

0040１３２人目の素数さん

2009/07/10(金) 08:18:14

189

0041１３２人目の素数さん

2009/08/15(土) 19:41:54

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

0042「猫」∈社会の屑 ◆ghclfYsc82

2009/08/15(土) 20:21:11

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

0043１３２人目の素数さん

2009/08/29(土) 16:34:14

山本君はグラフそのもの

0044１３２人目の素数さん

2009/09/02(水) 15:03:04

人間はグラフ

0045１３２人目の素数さん

2009/09/19(土) 14:46:02

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

0046１３２人目の素数さん

2009/09/19(土) 19:18:42

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

0047１３２人目の素数さん

2009/09/19(土) 19:28:43

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

0048１３２人目の素数さん

2009/09/19(土) 19:30:00

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

0049１３２人目の素数さん

2009/09/19(土) 19:30:23

＞47

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

0050１３２人目の素数さん

2009/09/19(土) 20:06:35

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

0051１３２人目の素数さん

2009/09/21(月) 10:21:57

グラフはこれから

0052１３２人目の素数さん

2009/11/13(金) 20:53:00

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

0053猫は珍獣 ◆ghclfYsc82

2009/11/13(金) 21:19:38

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

猫

0054べ

2009/11/16(月) 23:19:39

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

0055１３２人目の素数さん

2009/11/16(月) 23:26:21

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

0056１３２人目の素数さん

2010/01/31(日) 10:42:07

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

0057猫は淫獣 ◆ghclfYsc82

2010/01/31(日) 10:46:53

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

猫

0058１３２人目の素数さん

2010/01/31(日) 14:48:35

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

0059１３２人目の素数さん

2010/02/20(土) 16:07:01

重要

0060１３２人目の素数さん

2010/02/21(日) 00:32:40

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

0061１３２人目の素数さん

2010/02/21(日) 17:35:24

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

0062１３２人目の素数さん

2010/02/21(日) 18:40:52

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

0063１３２人目の素数さん

2010/02/22(月) 19:54:25

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

0064１３２人目の素数さん

2010/05/07(金) 16:44:16

525

0065１３２人目の素数さん

2010/06/09(水) 22:30:36

グラフ構造は宇宙

0066１３２人目の素数さん

2010/06/10(木) 07:03:33

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

0067１３２人目の素数さん

2010/06/10(木) 20:44:24

由美かおる

0068１３２人目の素数さん

2010/06/10(木) 22:08:47

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

0069１３２人目の素数さん

2010/06/10(木) 23:20:07

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

0070１３２人目の素数さん

2010/06/10(木) 23:55:54

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

0071１３２人目の素数さん

2010/06/11(金) 04:40:43

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

0072１３２人目の素数さん

2010/06/22(火) 15:54:01

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

0073１３２人目の素数さん

2010/06/22(火) 16:12:25

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

0074１３２人目の素数さん

2010/06/23(水) 00:02:12

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

0075１３２人目の素数さん

2010/06/23(水) 00:03:29

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

0076１３２人目の素数さん

2010/06/23(水) 00:13:52

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

0077１３２人目の素数さん

2010/06/23(水) 01:47:18

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

0078１３２人目の素数さん

2010/06/29(火) 04:23:12

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

0079１３２人目の素数さん

2010/06/29(火) 09:52:09

（´･ω･`）

0080１３２人目の素数さん

2010/06/29(火) 09:53:07

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

0081１３２人目の素数さん

2010/06/30(水) 23:01:50

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

0082１３２人目の素数さん

2010/07/24(土) 13:43:41

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

0083１３２人目の素数さん

2010/07/26(月) 11:33:58

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

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

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

0084１３２人目の素数さん

2010/07/26(月) 11:46:08

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

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

0085超越論的数学天使 ◆slSTfGIdiJ27

2010/07/27(火) 21:30:30

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