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

1 ：１３２人目の素数さん：2010/09/19(日) 21:27:42 .net

有限的で離散的な構造や事象を扱う、離散数学のスレです。
この分野は情報技術やコンピューターと密接な為、情報数学も対象とします。



■離散数学に属する主な分野

　・グラフ理論
　・組合せ論
　・マトロイド理論
　・デザイン理論
　・離散幾何学


■離散数学の定義（参考）

　・離散数学 - 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 ：１３２人目の素数さん：2010/09/19(日) 21:39:19 .net

■過去スレ

　俺とお前と離散数学
　　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 ：１３２人目の素数さん：2010/09/20(月) 08:58:45 .net

グラフ理論面白い

4 ：１３２人目の素数さん：2010/09/20(月) 09:08:58 .net

■関連スレ追加

　秋山仁総合スレッド
　　http://kamome.2ch.net/test/read.cgi/math/1087128378/

　こんな 秋山仁は嫌だ。
　　http://kamome.2ch.net/test/read.cgi/math/1059582076/

5 ：１３２人目の素数さん：2010/09/20(月) 09:10:31 .net

■重複スレのログ

　【グラフ理論】離散数学 2【組合せ離散】
　　http://kamome.2ch.net/test/read.cgi/math/1284893527/

6 ：１３２人目の素数さん：2010/09/21(火) 00:48:53 .net

とりあえず１乙。明日からがんがれ

【計算機科学】計算幾何学スレ【じゃないよ】
http://kamome.2ch.net/test/read.cgi/math/1263048852/

7 ：１３２人目の素数さん：2010/09/21(火) 16:45:14 .net

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

8 ：１３２人目の素数さん：2010/09/21(火) 18:50:07 .net

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

9 ：おさーん ◆xKQl9rTMwao4 ：2010/09/21(火) 18:59:47 .net

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

10 ：１３２人目の素数さん：2010/09/21(火) 19:35:16 .net

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

11 ：１３２人目の素数さん：2010/09/21(火) 22:06:28 .net

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

12 ：１３２人目の素数さん：2010/09/21(火) 22:55:51 .net

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

結び目理論とかすか？

13 ：１３２人目の素数さん：2010/09/21(火) 22:57:02 .net

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

14 ：１３２人目の素数さん：2010/09/21(火) 23:55:53 .net

縁結びの理論

15 ：１３２人目の素数さん：2010/09/22(水) 00:10:01 .net

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

16 ：１３２人目の素数さん：2010/09/22(水) 11:15:35 .net

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

17 ：１３２人目の素数さん：2010/09/22(水) 18:38:36 .net

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

18 ：１３２人目の素数さん：2010/09/22(水) 23:31:20 .net

>有向グラフで頂点に入ってくる辺と出ていく辺は何と呼べばいいですか？

入力辺、出力辺でわかると思う。せいしきなことは知らんけど。

19 ：１３２人目の素数さん：2010/09/22(水) 23:40:25 .net

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

ｎ点の平面グラフを埋め込むのに必要な面積をｎの関数で表すこと。

20 ：１３２人目の素数さん：2010/09/22(水) 23:51:33 .net

整数ベクトル(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が張る平行四辺形に含まれる点の個数。

はどうですか？

21 ：１３２人目の素数さん：2010/09/23(木) 00:01:19 .net

>>20

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

22 ：１３２人目の素数さん：2010/09/23(木) 00:12:06 .net

>>21
平面グラフの埋め込みの意味も知らないど素人なんですが
>>20は>>19と関係ありますか？

Aのはる平行四辺形の面積=det(A)=ad-bc=N+1

23 ：１３２人目の素数さん：2010/09/23(木) 05:44:26 .net

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

24 ：１３２人目の素数さん：2010/09/23(木) 07:27:22 .net

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

25 ：１３２人目の素数さん：2010/09/23(木) 12:44:45 .net

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

26 ：１３２人目の素数さん：2010/09/23(木) 13:19:59 .net

計算幾何学？

27 ：１３２人目の素数さん：2010/09/23(木) 13:24:40 .net

構造主義的離散数学

28 ：１３２人目の素数さん：2010/09/23(木) 13:27:26 .net

離散幾何学って、どんな幾何学なの？

位相幾何学的グラフ理論ってのも気になる。

29 ：１３２人目の素数さん：2010/09/23(木) 22:15:18 .net

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

30 ：１３２人目の素数さん：2010/09/24(金) 16:55:05 .net

>>22
>Aのはる平行四辺形の面積=det(A)=ad-bc=N+1

この平行四辺形内部にあるＮ個の格子点をうまくつないで
節点数ｎの平面グラフが描けばいい。
Ｎ＋１＝ｆ（ｎ）となる関数ｆで最適なものを見出すのが目標。
　　ｎｌｏｇ（ｎ）　＜＝　ｆ（ｎ）　＜＝　ｎ（ｌｏｇ（ｎ））＾２
ぐらいまではわかっているらしいが正確な結果については自分も素人なのでよく知らん。

31 ：１３２人目の素数さん：2010/09/24(金) 19:02:45 .net

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

32 ：１３２人目の素数さん：2010/09/25(土) 13:23:17 .net

離散数学

33 ：１３２人目の素数さん：2010/09/25(土) 20:41:07 .net

数論は離散数学か否か？

34 ：１３２人目の素数さん：2010/09/26(日) 00:10:02 .net

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

35 ：１３２人目の素数さん：2010/09/26(日) 08:55:11 .net

情報工だけど何か

物理/工学系の数学
http://kamome.2ch.net/test/read.cgi/math/1284697219/

36 ：１３２人目の素数さん：2010/09/26(日) 09:09:45 .net

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

37 ：１３２人目の素数さん：2010/09/26(日) 09:42:53 .net

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

38 ：１３２人目の素数さん：2010/09/26(日) 10:43:47 .net

離散数学で群論やるね

39 ：１３２人目の素数さん：2010/09/26(日) 11:01:32 .net

>■離散数学に属する主な分野
>・グラフ理論
>・組合せ論
>・マトロイド理論
>・デザイン理論
>・離散幾何学

情報数学に含まれる分野についてもまとめておいてほしい。

40 ：１３２人目の素数さん：2010/09/26(日) 13:00:08 .net

123 名前:１３２人目の素数さん :2010/09/25(土) 09:52:02

＞純粋数学する人たちが集まって会社作って
＞どうやって収益あげるの？

Googleの検索システムは、グラフ理論の応用だってさ。

数論やってた人は、暗号ソフトの会社。
代数幾何やてた人は、符号ソフトの会社。
数値解析やってた人は、数値解析ソフトの会社。
確率やってた人は、トレーディングソフトの会社。

41 ：１３２人目の素数さん：2010/09/26(日) 18:38:03 .net

１．数論やってた人は、暗号ソフトの会社。
２．代数幾何やてた人は、符号ソフトの会社。
３．数値解析やってた人は、数値解析ソフトの会社。
４．確率やってた人は、トレーディングソフトの会社。

２だけ関連性がよくわからん。
符号理論は代数幾何のうえに組み立てられているのか？

42 ：１３２人目の素数さん：2010/09/26(日) 19:08:36 .net

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

43 ：１３２人目の素数さん：2010/09/26(日) 23:39:53 .net

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

44 ：１３２人目の素数さん：2010/09/26(日) 23:55:36 .net

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

45 ：１３２人目の素数さん：2010/09/26(日) 23:56:56 .net

＞Googleの検索システムは、グラフ理論の応用だってさ。

共立出版から「ＰａｇｅＲａｎｋの数理」という本が出ている。
線形代数、グラフ理論、マルコフ過程などのおさらいになる。

46 ：１３２人目の素数さん：2010/09/27(月) 00:05:52 .net

＞数論は離散数学か否か？

整数という離散量を扱うので離散数学に含めてよいと思う。

47 ：１３２人目の素数さん：2010/09/27(月) 00:11:10 .net

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

48 ：１３２人目の素数さん：2010/09/27(月) 00:21:05 .net

＞離散幾何学って、どんな幾何学なの？

組み合わせ幾何とどう違うのかな？

49 ：１３２人目の素数さん：2010/09/27(月) 00:32:35 .net

>>47

これから「ＰａｇｅＲａｎｋの数理」を読んでいくのでわからんことがあったら教えてな。

50 ：１３２人目の素数さん：2010/09/30(木) 22:30:09 .net

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

51 ：１３２人目の素数さん：2010/09/30(木) 23:05:26 .net

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

52 ：１３２人目の素数さん：2010/10/01(金) 00:27:32 .net

とある研修所の昼食はメニュー選択の余地がなく、
　・カレ−ライス
　・牛丼
　・うどん
　・スパゲティ
のどれか一つ、利用者全員が同じ種類のものを食べます。

４品を出す日程を工夫して、どの日から何泊している人にとっても
同じパターンが 続けて 繰り返すことがないようにしたい。
さて、どのような方法で毎日のメニューを決めていけばよいでしょうか？

「同じパターンが 続けて 繰り返す」の例
　…うう…　　…カ牛カ牛…　　…牛スうス牛スうス…

　　　（数セミ、Vol.37, No.7　エレ解, 出題2 (1998/07)）

53 ：１３２人目の素数さん：2010/10/01(金) 00:29:39 .net

〔問題１〕
数列 {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 ：１３２人目の素数さん：2010/10/01(金) 00:36:19 .net

　たった４品のメニューで頑張っていましたが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,
をみたす。

55 ：１３２人目の素数さん：2010/10/01(金) 18:31:57 .net

任意の整数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,

これが〔問題１〕の答え？

56 ：１３２人目の素数さん：2010/10/01(金) 18:33:24 .net

>>55
〔問題２〕の下準備か・・・ゴメン

57 ：１３２人目の素数さん：2010/10/03(日) 18:31:55 .net

この等式を集合演算の性質を用いて示せ。
（１）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）

58 ：１３２人目の素数さん：2010/10/04(月) 00:36:23 .net

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

59 ：１３２人目の素数さん：2010/10/06(水) 00:19:35 .net

離散数学連盟

60 ：１３２人目の素数さん：2010/10/07(木) 21:15:12 .net

離散数学共和国

61 ：１３２人目の素数さん：2010/10/10(日) 05:01:58 .net

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

62 ：１３２人目の素数さん：2010/10/11(月) 00:20:53 .net

>>61
どういうことかkwsk

63 ：１３２人目の素数さん：2010/10/11(月) 01:19:25 .net

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

64 ：１３２人目の素数さん：2010/10/11(月) 04:23:50 .net

>>61
　コンピュータは２値（2進数）ですべての情報を表現していまつが････

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

65 ：１３２人目の素数さん：2010/10/13(水) 17:46:05 .net

多項定理おもすれー。
ttp://www1.c3-net.ne.jp/kato/pascal/index.html

群論との絡みもあるのかな？

66 ：１３２人目の素数さん：2010/10/14(木) 04:43:25 .net

合同会社離散数学商事

67 ：１３２人目の素数さん：2010/10/15(金) 21:56:58 .net

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

68 ：１３２人目の素数さん：2010/10/16(土) 22:21:28 .net

グラフ理論は楽しい

69 ：１３２人目の素数さん：2010/10/16(土) 22:54:47 .net

>>64
　未解決問題

70 ：１３２人目の素数さん：2010/10/17(日) 00:48:39 .net

(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 ：１３２人目の素数さん：2010/10/17(日) 00:54:18 .net

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 ：１３２人目の素数さん：2010/10/17(日) 08:29:50 .net

>>70 >>71
c=n-a-b だから３個目の (n-a-b)Cc はいらないのでは？

73 ：１３２人目の素数さん：2010/10/24(日) 13:01:31 .net

離散数学科作って！

74 ：１３２人目の素数さん：2010/10/24(日) 13:31:08 .net

コンビとれば？

75 ：１３２人目の素数さん：2010/10/24(日) 22:27:35 .net

解散でソロですか。

76 ：１３２人目の素数さん：2010/10/27(水) 12:24:02 .net

猫に小判、まで読んだ。

77 ：猫は火病 ◆MuKUnGPXAY ：2010/10/27(水) 16:07:37 .net

猫

78 ：１３２人目の素数さん：2010/10/30(土) 19:02:22 .net

グラフ理論的幾何学

79 ：１３２人目の素数さん：2010/11/01(月) 01:22:19 .net

　

80 ：１３２人目の素数さん：2010/11/01(月) 01:23:11 .net

グラフ理論は凄い

81 ：１３２人目の素数さん：2010/11/06(土) 07:58:20 .net

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

82 ：１３２人目の素数さん：2010/11/06(土) 19:55:08 .net

コドンの区切りがどうなっているのかいつも不思議に思う。
例えば開始コドンを | 00000 | として
| 11000 | 00111 | ...
が
11 | 00000 | 111 ...
と解釈されてしまわないのか

83 ：１３２人目の素数さん：2010/11/07(日) 08:54:18 .net

聴講したい

84 ：１３２人目の素数さん：2010/11/08(月) 02:11:19 .net

これからは離散数学の時代かな？

85 ：１３２人目の素数さん：2010/11/13(土) 03:03:30 .net

離散数学

86 ：１３２人目の素数さん：2010/11/15(月) 16:47:07 .net

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

87 ：１３２人目の素数さん：2010/11/16(火) 02:34:17 .net

>>86
工学部（計算機使うから）

88 ：１３２人目の素数さん：2010/11/20(土) 09:20:40 .net

そう意味では、ないだろうｗ

89 ：１３２人目の素数さん：2010/11/20(土) 11:37:39 .net

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

90 ：１３２人目の素数さん：2010/11/20(土) 11:42:08 .net

かまってちゃん

91 ：１３２人目の素数さん：2010/11/24(水) 12:40:37 .net

>>89
（・へ・）

92 ：１３２人目の素数さん：2010/11/26(金) 02:09:16 .net

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

93 ：１３２人目の素数さん：2010/11/27(土) 10:42:24 .net

ここでいいのか分からないが、ラムゼーの定理について質問させてくれ。

ラムゼーの定理：ある６人がいて、それら６人は知り合いと知り合いでないそれぞれ３人づつに分けられる

６人を{a,b,c,d,e,f}として
鳩ノ巣の原理の拡張（知り合いか知り合いでないかは３人以上）により
aと知り合いの組は６−a＝５人なので{３人２人}と{４人１人}のみ分けられる。逆は同じことなので除く
このとき{３人２人}の証明は分かったのだが

{４人１人}に分けた場合グラフをつなげてみたら
aと知り合いである人らのグループとお互いに知り合いでない人らのグループが、
５人{a,b,c,d,e}と５人{b,c,d,e,f}でつくれる。
これから重複を取り除いて３人と¬３人のグループにしたいのだがどうやるの？

94 ：１３２人目の素数さん：2010/11/27(土) 14:59:03 .net

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

95 ：１３２人目の素数さん：2010/11/28(日) 00:16:53 .net

グラフ理論大好き

96 ：１３２人目の素数さん：2010/11/29(月) 14:30:30 .net

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

97 ：１３２人目の素数さん：2010/11/29(月) 21:06:39 .net

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

98 ：１３２人目の素数さん：2010/11/30(火) 12:42:26 .net

秋山仁の仕事

99 ：１３２人目の素数さん：2010/12/04(土) 01:35:56 .net

グラフ理論

100 ：１３２人目の素数さん：2010/12/04(土) 01:37:27 .net

グラフ理論を義務教育の必修科目に！