【グラフ理論】離散数学／情報数学 2【組合せ論】
この分野は情報技術やコンピューターと密接な為、情報数学も対象とします。
■離散数学に属する主な分野
・グラフ理論
・組合せ論
・マトロイド理論
・デザイン理論
・離散幾何学
■離散数学の定義（参考）
・離散数学 - Wikipedia
ttp://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E6%95%B0%E5%AD%A6
・離散数学で変わる数学教育
ttp://www.ngm.edhs.ynu.ac.jp/negami/document/discmath/discmath.html
俺とお前と離散数学
http://kamome.2ch.sc/test/read.cgi/math/1242450341/
■数学板の関連スレ（鯖飛びにより過去スレのみ）
離散構造
http://kamome.2ch.sc/test/read.cgi/math/1177915636/
グラフ理論って重要だよね
http://kamome.2ch.sc/test/read.cgi/math/1238950176/
四色問題とHadwiger予想。二色目。
http://kamome.2ch.sc/test/read.cgi/math/1141729305/
四色問題の簡単な証明
http://kamome.2ch.sc/test/read.cgi/math/1266094084/
文系の俺にもわかる四色問題の反証をしてくれ
http://kamome.2ch.sc/test/read.cgi/math/1283661465/
■他板関連スレ（鯖飛びにより過去スレのみ）
離散数学
http://kamome.2ch.sc/test/read.cgi/informatics/1179741001/
グラフ理論の問題を出し合うスレ
http://kamome.2ch.sc/test/read.cgi/informatics/1155976582/
秋山仁総合スレッド
http://kamome.2ch.sc/test/read.cgi/math/1087128378/
こんな 秋山仁は嫌だ。
http://kamome.2ch.sc/test/read.cgi/math/1059582076/
【グラフ理論】離散数学 2【組合せ離散】
http://kamome.2ch.sc/test/read.cgi/math/1284893527/
【計算機科学】計算幾何学スレ【じゃないよ】
http://kamome.2ch.sc/test/read.cgi/math/1263048852/
国内と海外それぞれ。
国内・グラフ理論なら
慶應、横国、理科大、茨城大
辺りが院生も多い
なんか情報やコンピュータ系の印象なのですが
数学科でやってるんですか？
結び目理論とかすか？
最先端というより、むしろ4色問題じゃね？
ばかかー
それぞれの本数は入次数と出次数というのはWikiにも載ってるんですが。
教えてください。できれば英語もお願いします。
入力辺、出力辺でわかると思う。せいしきなことは知らんけど。
ｎ点の平面グラフを埋め込むのに必要な面積をｎの関数で表すこと。
行列A=((a, c)^T, (b,d)^T)について
det(A)=ad-bc=N+1
ここで、Nは(a, c)^T, (b,d)^Tが張る平行四辺形に含まれる点の個数。
はどうですか？
ミンコフスキーの創始した数の幾何学の話題やな。
最先端と言うより古典的な範囲になるんとちゃうか。
最近では格子の幾何を暗号理論に応用する研究もされているらしいので
そういう意味では最先端なのかもしれん。
平面グラフの埋め込みの意味も知らないど素人なんですが
>>20は>>19と関係ありますか？
Aのはる平行四辺形の面積=det(A)=ad-bc=N+1
http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E5%B9%BE%E4%BD%95%E5%AD%A6
というように、面の数だけでなくもっと詳しく面の構造を
求めるアルゴリズムってあるのでしょうか？
位相幾何学的グラフ理論ってのも気になる。
ありがとうございます。
ググってみたら使用例もかなりあるようで使わせていただきます。
>Aのはる平行四辺形の面積=det(A)=ad-bc=N+1
この平行四辺形内部にあるＮ個の格子点をうまくつないで
節点数ｎの平面グラフが描けばいい。
Ｎ＋１＝ｆ（ｎ）となる関数ｆで最適なものを見出すのが目標。
ｎｌｏｇ（ｎ） ＜＝ ｆ（ｎ） ＜＝ ｎ（ｌｏｇ（ｎ））＾２
ぐらいまではわかっているらしいが正確な結果については自分も素人なのでよく知らん。
このスレって工学系の人もいるのかな？
物理/工学系の数学
http://kamome.2ch.sc/test/read.cgi/math/1284697219/
普通、情報数学って、群論とかの話ではないものなのかな？
授業まじめに聞いてなかったからかよくわからん
>・グラフ理論
>・組合せ論
>・マトロイド理論
>・デザイン理論
>・離散幾何学
情報数学に含まれる分野についてもまとめておいてほしい。
＞純粋数学する人たちが集まって会社作って
＞どうやって収益あげるの？
Googleの検索システムは、グラフ理論の応用だってさ。
数論やってた人は、暗号ソフトの会社。
代数幾何やてた人は、符号ソフトの会社。
数値解析やってた人は、数値解析ソフトの会社。
確率やってた人は、トレーディングソフトの会社。
２．代数幾何やてた人は、符号ソフトの会社。
３．数値解析やってた人は、数値解析ソフトの会社。
４．確率やってた人は、トレーディングソフトの会社。
２だけ関連性がよくわからん。
符号理論は代数幾何のうえに組み立てられているのか？
共立出版から「ＰａｇｅＲａｎｋの数理」という本が出ている。
線形代数、グラフ理論、マルコフ過程などのおさらいになる。
整数という離散量を扱うので離散数学に含めてよいと思う。
組み合わせ幾何とどう違うのかな？
これから「ＰａｇｅＲａｎｋの数理」を読んでいくのでわからんことがあったら教えてな。
・カレ－ライス
・牛丼
・うどん
・スパゲティ
のどれか一つ、利用者全員が同じ種類のものを食べます。
４品を出す日程を工夫して、どの日から何泊している人にとっても
同じパターンが 続けて 繰り返すことがないようにしたい。
さて、どのような方法で毎日のメニューを決めていけばよいでしょうか？
「同じパターンが 続けて 繰り返す」の例
…うう… …カ牛カ牛… …牛スうス牛スうス…
（数セミ、Vol.37, No.7 エレ解, 出題2 (1998/07)）
数列 {a_n} を次のように定義する。（m,rは自然数）
a_n = 1, {n=4m-3 のとき}
a_n = 2, {n=(2^r)･(4m-3) のとき}
a_n = 3, {n=4m-1 のとき}
a_n = 4, {n=(2^r)･(4m-1) のとき}
数列 {a_n} には、同じパターンが 続けて 繰り返すことがないことを示せ。
（数セミ、Vol.37, No.10, エレ解, 解説2 (1998/10)）
牛丼の販売を休止……というわけで、牛丼を除く３品にメニューを減らすことになりました。
さて、上記のことは依然として実現できるでしょうか？
任意の整数xは、平衡３進法で
x = Σ[n=0,h] 3^n･t_n,
と表わされる。（ただし t_n =-1,0,1 n>h のとき t_n=0）
0 と t の互換を σ(t) と表わす。
σ(t)^2 = I,
σ(0) = I,
〔問題２〕
数列 {b_x} を次式で定義する。
b_x = σ(t_h)・σ(t_(h-1))・･････・σ(t_1)・σ(t_0) {0}
数列 {b_x} にも、同じパターンが 続けて 繰り返すことがないことを示せ。
注）これは b_(3x) = b_x,
b_(x - 3^h) = σ(-1) b_x, |x| ≦ (3^h -1)/2,
b_(x + 3^h) = σ( 1) b_x, |x| ≦ (3^h -1)/2,
をみたす。
x = Σ[n=0,h] 3^n･t_n,
と表わされる。（ただし t_n =-1,0,1 n>h のとき t_n=0）
0 と t の互換を σ(t) と表わす。
σ(t)^2 = I,
σ(0) = I,
これが〔問題１〕の答え？
〔問題２〕の下準備か・・・ゴメン
（１）A－（B∪C）＝（AーB）∩（AーC）
（２）Aー（B∩C）＝（AーB）∪（AーC）
（３）（￢A∪B）∪（A∪￢B）＝（A∩B）∪（￢A∩￢B）
（４）（￢A∩B）∪（A∩￢B）＝（A∪B）∩（￢A∪￢B）
分子遺伝学的に云えば、遺伝子（DNAやRNA）の塩基が３種類 以上（望ましくは４種類 以上）あれば、
どんなに多くの種類の（RNAや蛋白質）でも表わすことができるってことでつね。
どういうことかkwsk
効率は悪いが塩基は２種類でも表せるのでは？
DNAは塩基対でペアを組むから偶数種類が都合がよい
コンピュータは２値（2進数）ですべての情報を表現していまつが････
同じパターンが繰り返す、ということが遺伝情報の発現に不都合なんでつか？
ttp://www1.c3-net.ne.jp/kato/pascal/index.html
群論との絡みもあるのかな？
非可算無限は表せないな。
未解決問題
x(a,b,c)a^ab^bc^c
nCa(n-a)Cb(n-a-b)Cc=x(a,b,c)
=n!/a!b!c!(n-a-b-c)!=n!/a!b!c!
(a+b+c+d)^n
x(a,b,c,d)=n!/a!b!c!d!
x(a,b)=n!/a!b!
2!/1!1!=2
2!/0!2!=1
2!/2!0!=1
c=n-a-b だから３個目の (n-a-b)Cc はいらないのでは？
2種類で21種のアミノ酸を指定するにはコドンは5個必要になるな
例えば開始コドンを | 00000 | として
| 11000 | 00111 | ...
が
11 | 00000 | 111 ...
と解釈されてしまわないのか
工学部（計算機使うから）
正直すまんかったｗ
誰も突っ込んでくれないから、一人で悲しんでた(´・ω・｀)
（・へ・）
工学部の計算は大抵の場合、何でも線形問題に落として
行列計算することが多いから、間違いではないよ。
ラムゼーの定理：ある６人がいて、それら６人は知り合いと知り合いでないそれぞれ３人づつに分けられる
６人を{a,b,c,d,e,f}として
鳩ノ巣の原理の拡張（知り合いか知り合いでないかは３人以上）により
aと知り合いの組は６－a＝５人なので{３人２人}と{４人１人}のみ分けられる。逆は同じことなので除く
このとき{３人２人}の証明は分かったのだが
{４人１人}に分けた場合グラフをつなげてみたら
aと知り合いである人らのグループとお互いに知り合いでない人らのグループが、
５人{a,b,c,d,e}と５人{b,c,d,e,f}でつくれる。
これから重複を取り除いて３人と￢３人のグループにしたいのだがどうやるの？
ラムゼーの定理を勘違いしていると思うよ。
確か、互いに知りあい同士の３人がいるか、もしくは、互いに全然知らない人３人がいるか、
どちらか一方は必ず成り立つ。という定理だった気がする。
学ぶにあたり、前提として知っておかなくてはならない知識は何？
100～のスレッドの続きを読む