1read 100read
2012年5月数学320: 【グラフ理論】離散数学/情報数学 2【組合せ論】 (650) TOP カテ一覧 スレ一覧 2ch元 削除依頼
1+1=2について考える (139)
有名なのに業績があまり知られていない数学者 (161)
【肉棒】を積分して求積しようぜ?!【】 (320)
現状の大学院を健全化スルにはどうするべきか? (754)
ゲーム理論について (183)
女性初のフィールズ賞受賞者を目指してます! (152)

【グラフ理論】離散数学/情報数学 2【組合せ論】


1 :10/09/19 〜 最終レス :12/05/03
有限的で離散的な構造や事象を扱う、離散数学のスレです。
この分野は情報技術やコンピューターと密接な為、情報数学も対象とします。
■離散数学に属する主な分野
 ・グラフ理論
 ・組合せ論
 ・マトロイド理論
 ・デザイン理論
 ・離散幾何学
■離散数学の定義(参考)
 ・離散数学 - 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

2 :
■過去スレ
 俺とお前と離散数学
  http://kamome.2ch.net/test/read.cgi/math/1242450341/
■数学板の関連スレ(鯖飛びにより過去スレのみ)
 離散構造
  http://kamome.2ch.net/test/read.cgi/math/1177915636/
 グラフ理論って重要だよね
  http://kamome.2ch.net/test/read.cgi/math/1238950176/
 四色問題とHadwiger予想。二色目。
  http://kamome.2ch.net/test/read.cgi/math/1141729305/
 四色問題の簡単な証明
  http://kamome.2ch.net/test/read.cgi/math/1266094084/
 文系の俺にもわかる四色問題の反証をしてくれ
  http://kamome.2ch.net/test/read.cgi/math/1283661465/
■他板関連スレ(鯖飛びにより過去スレのみ)
 離散数学
  http://kamome.2ch.net/test/read.cgi/informatics/1179741001/
 グラフ理論の問題を出し合うスレ
  http://kamome.2ch.net/test/read.cgi/informatics/1155976582/

3 :
グラフ理論面白い

4 :
■関連スレ追加
 秋山仁総合スレッド
  http://kamome.2ch.net/test/read.cgi/math/1087128378/
 こんな 秋山仁は嫌だ。
  http://kamome.2ch.net/test/read.cgi/math/1059582076/

5 :
■重複スレのログ
 【グラフ理論】離散数学 2【組合せ離散】
  http://kamome.2ch.net/test/read.cgi/math/1284893527/

6 :
とりあえず1乙。明日からがんがれ
【計算機科学】計算幾何学スレ【じゃないよ】
http://kamome.2ch.net/test/read.cgi/math/1263048852/

7 :
離散数学の研究が盛んな大学は、どこだろう?
国内と海外それぞれ。

8 :
大学というより、むしろ秋山仁じゃね?

9 :
秋山仁というより、むしろペーターフランクル

10 :
>>7
国内・グラフ理論なら
慶應、横国、理科大、茨城大
辺りが院生も多い

11 :
グラフ理論の最先端ってどんなテーマがあるの?

12 :
グラフ理論というと
なんか情報やコンピュータ系の印象なのですが
数学科でやってるんですか?
結び目理論とかすか?

13 :
>>11
最先端というより、むしろ4色問題じゃね?

14 :
縁結びの理論

15 :
俺からあの娘まで、非連結グラフ。
ばかかー

16 :
でも、本当に「結婚定理」というのはあるよ。二部グラフが完全マッOを持つ必要十分条件っていうやつね。

17 :
有向グラフで頂点に入ってくる辺と出ていく辺は何と呼べばいいですか?
それぞれの本数は入次数と出次数というのはWikiにも載ってるんですが。
教えてください。できれば英語もお願いします。

18 :
>有向グラフで頂点に入ってくる辺と出ていく辺は何と呼べばいいですか?
入力辺、出力辺でわかると思う。せいしきなことは知らんけど。

19 :
>グラフ理論の最先端ってどんなテーマがあるの?
n点の平面グラフを埋め込むのに必要な面積をnの関数で表すこと。


20 :
整数ベクトル(a, c)^T, (b,d)^Tで、aとcは互いに素、bとdは互いに素のとき
行列A=((a, c)^T, (b,d)^T)について
det(A)=ad-bc=N+1
ここで、Nは(a, c)^T, (b,d)^Tが張る平行四辺形に含まれる点の個数。
はどうですか?

21 :
>>20
ミンコフスキーの創始した数の幾何学の話題やな。
最先端と言うより古典的な範囲になるんとちゃうか。
最近では格子の幾何を暗号理論に応用する研究もされているらしいので
そういう意味では最先端なのかもしれん。

22 :
>>21
平面グラフの埋め込みの意味も知らないど素人なんですが
>>20>>19と関係ありますか?
Aのはる平行四辺形の面積=det(A)=ad-bc=N+1

23 :
計算幾何学 - Wikipedia
http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E5%B9%BE%E4%BD%95%E5%AD%A6

24 :
グラフ理論は、これからますます重要になると思う。

25 :
平面グラフの三角形の数、四角形の数、五角形の数、六角形の数・・・
というように、面の数だけでなくもっと詳しく面の構造を
求めるアルゴリズムってあるのでしょうか?

26 :
計算幾何学?

27 :
構造主義的離散数学

28 :
離散幾何学って、どんな幾何学なの?
位相幾何学的グラフ理論ってのも気になる。

29 :
>>18
ありがとうございます。
ググってみたら使用例もかなりあるようで使わせていただきます。

30 :
>>22
>Aのはる平行四辺形の面積=det(A)=ad-bc=N+1
この平行四辺形内部にあるN個の格子点をうまくつないで
節点数nの平面グラフが描けばいい。
N+1=f(n)となる関数fで最適なものを見出すのが目標。
  nlog(n) <= f(n) <= n(log(n))^2
ぐらいまではわかっているらしいが正確な結果については自分も素人なのでよく知らん。

31 :
離散数学の授業を聴講したい

32 :
離散数学

33 :
数論は離散数学か否か?

34 :
スレタイに情報数学ってあるところをみると、
このスレって工学系の人もいるのかな?

35 :
情報工だけど何か
物理/工学系の数学
http://kamome.2ch.net/test/read.cgi/math/1284697219/

36 :
面白スレ発見
普通、情報数学って、群論とかの話ではないものなのかな?

37 :
群・環・体論は情報理論でちょっと出てきたぐらいか
授業まじめに聞いてなかったからかよくわからん

38 :
離散数学で群論やるね

39 :
>■離散数学に属する主な分野
>・グラフ理論
>・組合せ論
>・マトロイド理論
>・デザイン理論
>・離散幾何学
情報数学に含まれる分野についてもまとめておいてほしい。

40 :
123 名前:132人目の素数さん :2010/09/25(土) 09:52:02
>純粋数学する人たちが集まって会社作って
>どうやって収益あげるの?
Googleの検索システムは、グラフ理論の応用だってさ。
数論やってた人は、暗号ソフトの会社。
代数幾何やてた人は、符号ソフトの会社。
数値解析やってた人は、数値解析ソフトの会社。
確率やってた人は、トレーディングソフトの会社。

41 :
1.数論やってた人は、暗号ソフトの会社。
2.代数幾何やてた人は、符号ソフトの会社。
3.数値解析やってた人は、数値解析ソフトの会社。
4.確率やってた人は、トレーディングソフトの会社。
2だけ関連性がよくわからん。
符号理論は代数幾何のうえに組み立てられているのか?

42 :
やはり、グラフ理論の時代よの。

43 :
この世をばグラフ理論の世ぞと思う。

44 :
私は鳥が歌うように、グラフを描きたい。(クロ・モネ(画家))

45 :
>Googleの検索システムは、グラフ理論の応用だってさ。
共立出版から「PageRankの数理」という本が出ている。
線形代数、グラフ理論、マルコフ過程などのおさらいになる。

46 :
>数論は離散数学か否か?
整数という離散量を扱うので離散数学に含めてよいと思う。

47 :
googleの検索って、自己相関行列とかを使っているのかと思っていた。

48 :
>離散幾何学って、どんな幾何学なの?
組み合わせ幾何とどう違うのかな?

49 :
>>47
これから「PageRankの数理」を読んでいくのでわからんことがあったら教えてな。

50 :
符号理論は群論のイメージがあるけど。

51 :
誤り訂正符号とかには、多項式がいっぱいでてくるね

52 :
とある研修所の昼食はメニュー選択の余地がなく、
 ・カレ−ライス
 ・牛丼
 ・うどん
 ・スパゲティ
のどれか一つ、利用者全員が同じ種類のものを食べます。
4品を出す日程を工夫して、どの日から何泊している人にとっても
同じパターンが 続けて 繰り返すことがないようにしたい。
さて、どのような方法で毎日のメニューを決めていけばよいでしょうか?
「同じパターンが 続けて 繰り返す」の例
 …うう…  …カ牛カ牛…  …牛スうス牛スうス…
   (数セミ、Vol.37, No.7 エレ解, 出題2 (1998/07))

53 :
〔問題1〕
数列 {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))

54 :
 たった4品のメニューで頑張っていましたがBSE(牛海綿状脳症)感染疑惑牛発見のため、
牛丼の販売を休止……というわけで、牛丼を除く3品にメニューを減らすことになりました。
さて、上記のことは依然として実現できるでしょうか?


任意の整数xは、平衡3進法で
 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,

〔問題2〕
数列 {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,
をみたす。

55 :
任意の整数xは、平衡3進法で
 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,
これが〔問題1〕の答え?

56 :
>>55
〔問題2〕の下準備か・・・ゴメン

57 :
この等式を集合演算の性質を用いて示せ。
(1)A−(B∪C)=(AーB)∩(AーC)
(2)Aー(B∩C)=(AーB)∪(AーC)
(3)(¬A∪B)∪(A∪¬B)=(A∩B)∪(¬A∩¬B)
(4)(¬A∩B)∪(A∩¬B)=(A∪B)∩(¬A∪¬B)

58 :
幾何学的群論的グラフ理論

59 :
離散数学連盟

60 :
離散数学共和国

61 :
>>52 >>54
分子遺伝学的に云えば、遺伝子(DNAやRNA)の塩基が3種類 以上(望ましくは4種類 以上)あれば、
どんなに多くの種類の(RNAや蛋白質)でも表わすことができるってことでつね。

62 :
>>61
どういうことかkwsk

63 :
>>61
効率は悪いが塩基は2種類でも表せるのでは?
DNAは塩基対でペアを組むから偶数種類が都合がよい

64 :
>>61
 コンピュータは2値(2進数)ですべての情報を表現していまつが・・・・

 同じパターンが繰り返す、ということが遺伝情報の発現に不都合なんでつか?


65 :
多項定理おもすれー。
ttp://www1.c3-net.ne.jp/kato/pascal/index.html
群論との絡みもあるのかな?

66 :
合同会社離散数学商事

67 :
>>61
非可算無限は表せないな。

68 :
グラフ理論は楽しい

69 :
>>64
 未解決問題

70 :
(a+b+c)^n
x(a,b,c)a^ab^bc^c
nCa(n-a)Cb(n-a-b)Cc=x(a,b,c)

71 :
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

72 :
>>70 >>71
c=n-a-b だから3個目の (n-a-b)Cc はいらないのでは?

73 :
離散数学科作って!

74 :
コンビとれば?

75 :
解散でソロですか。

76 :
猫に小判、まで読んだ。

77 :


78 :
グラフ理論的幾何学

79 :
 

80 :
グラフ理論は凄い

81 :
>>63
2種類で21種のアミノ酸を指定するにはコドンは5個必要になるな

82 :
コドンの区切りがどうなっているのかいつも不思議に思う。
例えば開始コドンを | 00000 | として
| 11000 | 00111 | ...

11 | 00000 | 111 ...
と解釈されてしまわないのか

83 :
聴講したい

84 :
これからは離散数学の時代かな?

85 :
離散数学

86 :
IT以外の分野で、離散数学を応用している分野は?

87 :
>>86
工学部(計算機使うから)

88 :
そう意味では、ないだろうw

89 :
>>88
正直すまんかったw
誰も突っ込んでくれないから、一人で悲しんでた(´・ω・`)

90 :
かまってちゃん

91 :
>>89
(・へ・)

92 :
>>87
工学部の計算は大抵の場合、何でも線形問題に落として
行列計算することが多いから、間違いではないよ。

93 :
ここでいいのか分からないが、ラムゼーの定理について質問させてくれ。
ラムゼーの定理:ある6人がいて、それら6人は知り合いと知り合いでないそれぞれ3人づつに分けられる
6人を{a,b,c,d,e,f}として
鳩ノ巣の原理の拡張(知り合いか知り合いでないかは3人以上)により
aと知り合いの組は6−a=5人なので{3人2人}と{4人1人}のみ分けられる。逆は同じことなので除く
このとき{3人2人}の証明は分かったのだが
{4人1人}に分けた場合グラフをつなげてみたら
aと知り合いである人らのグループとお互いに知り合いでない人らのグループが、
5人{a,b,c,d,e}と5人{b,c,d,e,f}でつくれる。
これから重複を取り除いて3人と¬3人のグループにしたいのだがどうやるの?

94 :
>>93
ラムゼーの定理を勘違いしていると思うよ。
確か、互いに知りあい同士の3人がいるか、もしくは、互いに全然知らない人3人がいるか、
どちらか一方は必ず成り立つ。という定理だった気がする。

95 :
グラフ理論大好き

96 :
巡回指数ってやつの証明が乗ってる日本語の本教えてください。

97 :
グラフ理論のオススメの教科書は?
学ぶにあたり、前提として知っておかなくてはならない知識は何?

98 :
秋山仁の仕事

99 :
グラフ理論

100read 1read
1read 100read
TOP カテ一覧 スレ一覧 2ch元 削除依頼
雑談はここに書け!【44】 (923)
【R言語】統計解析フリーソフトR 第4章【GNU R】 (512)
復刊してほしい数学の本 (257)
【test】テストスレ (127)
★■★『無意味な大学について語るスレ』★■★ (557)
数学検定 (270)
--log9.info------------------
ちん毛カット総合スレ (212)
二重から一重になったやつ集合 (139)
前髪薄いやつ集まれ (210)
顔が白ければ美形部類に入るはずの俺 (100)
尾崎豊は男から見ても美神だろ? (342)
携帯の写メで顔撮ったら、爆笑wwwww (177)
尻のほっぺに毛が生えてる人いる? (113)
最近の若い男は彫が深いのが増えた (137)
昔はブサイクだったけどイケメンになったやつ集合 (228)
黒人って美容とか気にしなくて良いから楽だよな (109)
渋谷、イケメン多すぎワロタwwwwwwwwwww (115)
半身浴している時って何してる? (103)
27才だけど女子高生と付き合いたい (224)
 身長を伸ばす方法  (423)
我輩が美しい体を仕上げながらドラム缶を探すスレ (702)
朝の支度の所要時間書いてけ (167)
--log55.com------------------
【Asahi】白いサイダー【三ツ矢】
午後の紅茶「あやトラ」キャンペーンについて語ろう
【BOSS】で何がすき??
【山形】 パインサイダー 【地サイダー】
今わ亡きパンピーオレンジ・・・
☆【アサヒ 十六茶】 リニューアル新発売
結局一番うまいのはコカコーラだろ
デーリィ・フルーツサワー