【グラフ理論】離散数学／情報数学 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 離散数学の研究が盛んな大学は、どこだろう？
国内と海外それぞれ。 >>7
国内・グラフ理論なら
慶應、横国、理科大、茨城大
辺りが院生も多い グラフ理論というと
なんか情報やコンピュータ系の印象なのですが
数学科でやってるんですか？
結び目理論とかすか？ >>11
最先端というより、むしろ4色問題じゃね？ でも、本当に「結婚定理」というのはあるよ。二部グラフが完全マッチングを持つ必要十分条件っていうやつね。 有向グラフで頂点に入ってくる辺と出ていく辺は何と呼べばいいですか？
それぞれの本数は入次数と出次数というのはWikiにも載ってるんですが。
教えてください。できれば英語もお願いします。 >有向グラフで頂点に入ってくる辺と出ていく辺は何と呼べばいいですか？
入力辺、出力辺でわかると思う。せいしきなことは知らんけど。
＞グラフ理論の最先端ってどんなテーマがあるの？
ｎ点の平面グラフを埋め込むのに必要な面積をｎの関数で表すこと。
整数ベクトル(a, c)^T, (b,d)^Tで、aとｃは互いに素、bとdは互いに素のとき
行列A=((a, c)^T, (b,d)^T)について
det(A)=ad-bc=N+1
ここで、Nは(a, c)^T, (b,d)^Tが張る平行四辺形に含まれる点の個数。
はどうですか？
>>20
ミンコフスキーの創始した数の幾何学の話題やな。
最先端と言うより古典的な範囲になるんとちゃうか。
最近では格子の幾何を暗号理論に応用する研究もされているらしいので
そういう意味では最先端なのかもしれん。
>>21
平面グラフの埋め込みの意味も知らないど素人なんですが
>>20は>>19と関係ありますか？
Aのはる平行四辺形の面積=det(A)=ad-bc=N+1 平面グラフの三角形の数、四角形の数、五角形の数、六角形の数・・・
というように、面の数だけでなくもっと詳しく面の構造を
求めるアルゴリズムってあるのでしょうか？ 離散幾何学って、どんな幾何学なの？
位相幾何学的グラフ理論ってのも気になる。 >>18
ありがとうございます。
ググってみたら使用例もかなりあるようで使わせていただきます。
>>22
>Aのはる平行四辺形の面積=det(A)=ad-bc=N+1
この平行四辺形内部にあるＮ個の格子点をうまくつないで
節点数ｎの平面グラフが描けばいい。
Ｎ＋１＝ｆ（ｎ）となる関数ｆで最適なものを見出すのが目標。
ｎｌｏｇ（ｎ） ＜＝ ｆ（ｎ） ＜＝ ｎ（ｌｏｇ（ｎ））＾２
ぐらいまではわかっているらしいが正確な結果については自分も素人なのでよく知らん。
スレタイに情報数学ってあるところをみると、
このスレって工学系の人もいるのかな？ 面白スレ発見
普通、情報数学って、群論とかの話ではないものなのかな？ 群・環・体論は情報理論でちょっと出てきたぐらいか
授業まじめに聞いてなかったからかよくわからん >■離散数学に属する主な分野
>・グラフ理論
>・組合せ論
>・マトロイド理論
>・デザイン理論
>・離散幾何学
情報数学に含まれる分野についてもまとめておいてほしい。
123 名前:１３２人目の素数さん :2010/09/25(土) 09:52:02
＞純粋数学する人たちが集まって会社作って
＞どうやって収益あげるの？
Googleの検索システムは、グラフ理論の応用だってさ。
数論やってた人は、暗号ソフトの会社。
代数幾何やてた人は、符号ソフトの会社。
数値解析やってた人は、数値解析ソフトの会社。
確率やってた人は、トレーディングソフトの会社。 １．数論やってた人は、暗号ソフトの会社。
２．代数幾何やてた人は、符号ソフトの会社。
３．数値解析やってた人は、数値解析ソフトの会社。
４．確率やってた人は、トレーディングソフトの会社。
２だけ関連性がよくわからん。
符号理論は代数幾何のうえに組み立てられているのか？ 私は鳥が歌うように、グラフを描きたい。(クロ・モネ（画家）) ＞Googleの検索システムは、グラフ理論の応用だってさ。
共立出版から「ＰａｇｅＲａｎｋの数理」という本が出ている。
線形代数、グラフ理論、マルコフ過程などのおさらいになる。 ＞数論は離散数学か否か？
整数という離散量を扱うので離散数学に含めてよいと思う。 googleの検索って、自己相関行列とかを使っているのかと思っていた。 ＞離散幾何学って、どんな幾何学なの？
組み合わせ幾何とどう違うのかな？ >>47
これから「ＰａｇｅＲａｎｋの数理」を読んでいくのでわからんことがあったら教えてな。 とある研修所の昼食はメニュー選択の余地がなく、
・カレ−ライス
・牛丼
・うどん
・スパゲティ
のどれか一つ、利用者全員が同じ種類のものを食べます。
４品を出す日程を工夫して、どの日から何泊している人にとっても
同じパターンが 続けて 繰り返すことがないようにしたい。
さて、どのような方法で毎日のメニューを決めていけばよいでしょうか？
「同じパターンが 続けて 繰り返す」の例
…うう… …カ牛カ牛… …牛スうス牛スうス…
（数セミ、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)） たった４品のメニューで頑張っていましたがBSE(牛海綿状脳症)感染疑惑牛発見のため、
牛丼の販売を休止……というわけで、牛丼を除く３品にメニューを減らすことになりました。
さて、上記のことは依然として実現できるでしょうか？
任意の整数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は、平衡３進法で
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） >>52 >>54
分子遺伝学的に云えば、遺伝子（DNAやRNA）の塩基が３種類 以上（望ましくは４種類 以上）あれば、
どんなに多くの種類の（RNAや蛋白質）でも表わすことができるってことでつね。
>>61
効率は悪いが塩基は２種類でも表せるのでは？
DNAは塩基対でペアを組むから偶数種類が都合がよい >>61
コンピュータは２値（2進数）ですべての情報を表現していまつが････
同じパターンが繰り返す、ということが遺伝情報の発現に不都合なんでつか？
多項定理おもすれー。
ttp://www1.c3-net.ne.jp/kato/pascal/index.html
群論との絡みもあるのかな？ (a+b+c)^n
x(a,b,c)a^ab^bc^c
nCa(n-a)Cb(n-a-b)Cc=x(a,b,c) n!/a!(n-a)!*(n-a)!/b!(n-a-b)!*(n-a-b)!/c!(n-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 >>70 >>71
c=n-a-b だから３個目の (n-a-b)Cc はいらないのでは？ >>63
2種類で21種のアミノ酸を指定するにはコドンは5個必要になるな コドンの区切りがどうなっているのかいつも不思議に思う。
例えば開始コドンを | 00000 | として
| 11000 | 00111 | ...
が
11 | 00000 | 111 ...
と解釈されてしまわないのか >>88
正直すまんかったｗ
誰も突っ込んでくれないから、一人で悲しんでた(´・ω・｀) >>87
工学部の計算は大抵の場合、何でも線形問題に落として
行列計算することが多いから、間違いではないよ。
ここでいいのか分からないが、ラムゼーの定理について質問させてくれ。
ラムゼーの定理：ある６人がいて、それら６人は知り合いと知り合いでないそれぞれ３人づつに分けられる
６人を{a,b,c,d,e,f}として
鳩ノ巣の原理の拡張（知り合いか知り合いでないかは３人以上）により
aと知り合いの組は６−a＝５人なので{３人２人}と{４人１人}のみ分けられる。逆は同じことなので除く
このとき{３人２人}の証明は分かったのだが
{４人１人}に分けた場合グラフをつなげてみたら
aと知り合いである人らのグループとお互いに知り合いでない人らのグループが、
５人{a,b,c,d,e}と５人{b,c,d,e,f}でつくれる。
これから重複を取り除いて３人と¬３人のグループにしたいのだがどうやるの？
>>93
ラムゼーの定理を勘違いしていると思うよ。
確か、互いに知りあい同士の３人がいるか、もしくは、互いに全然知らない人３人がいるか、
どちらか一方は必ず成り立つ。という定理だった気がする。 巡回指数ってやつの証明が乗ってる日本語の本教えてください。 グラフ理論のオススメの教科書は？
学ぶにあたり、前提として知っておかなくてはならない知識は何？ 巡回指数というかポリアの定理の証明が乗ってるやつでいいです。 ■ このスレッドは過去ログ倉庫に格納されています
