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

1 ：2010/09/19 〜 最終レス ：2013/01/16

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

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

■離散数学の定義（参考）
　・離散数学 - 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 ：

とりあえず１乙。明日からがんがれ
【計算機科学】計算幾何学スレ【じゃないよ】
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 ：

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

20 ：

整数ベクトル(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 ：

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

31 ：

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

32 ：

離散数学

33 ：

数論は離散数学か否か？

34 ：

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

35 ：

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

36 ：

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

37 ：

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

38 ：

離散数学で群論やるね

39 ：

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

40 ：

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

41 ：

１．数論やってた人は、暗号ソフトの会社。
２．代数幾何やてた人は、符号ソフトの会社。
３．数値解析やってた人は、数値解析ソフトの会社。
４．確率やってた人は、トレーディングソフトの会社。
２だけ関連性がよくわからん。
符号理論は代数幾何のうえに組み立てられているのか？

42 ：

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

43 ：

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

44 ：

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

45 ：

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

46 ：

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

47 ：

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

48 ：

＞離散幾何学って、どんな幾何学なの？
組み合わせ幾何とどう違うのかな？

49 ：

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

50 ：

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

51 ：

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

52 ：

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

53 ：

〔問題１〕
数列 {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 ：

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

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

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

57 ：

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

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

59 ：

離散数学連盟

60 ：

離散数学共和国

61 ：

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

62 ：

>>61
どういうことかkwsk

63 ：

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

64 ：

>>61
　コンピュータは２値（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 だから３個目の (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 ：

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

89 ：

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

90 ：

かまってちゃん

91 ：

>>89
（・へ・）

92 ：

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

93 ：

ここでいいのか分からないが、ラムゼーの定理について質問させてくれ。
ラムゼーの定理：ある６人がいて、それら６人は知り合いと知り合いでないそれぞれ３人づつに分けられる
６人を{a,b,c,d,e,f}として
鳩ノ巣の原理の拡張（知り合いか知り合いでないかは３人以上）により
aと知り合いの組は６−a＝５人なので{３人２人}と{４人１人}のみ分けられる。逆は同じことなので除く
このとき{３人２人}の証明は分かったのだが
{４人１人}に分けた場合グラフをつなげてみたら
aと知り合いである人らのグループとお互いに知り合いでない人らのグループが、
５人{a,b,c,d,e}と５人{b,c,d,e,f}でつくれる。
これから重複を取り除いて３人と¬３人のグループにしたいのだがどうやるの？

94 ：

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

95 ：

グラフ理論大好き

96 ：

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

97 ：

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

98 ：

秋山仁の仕事

99 ：

グラフ理論

100read 1read

1read 100read
TOP カテ一覧 スレ一覧 2ch元 削除依頼 ▲

初等整数論の問題�A (932)
第３種完全楕円積分 (229)
６÷２（１＋２）＝？ (715)
【数式処理システム】 Maxima 【Common Lisp】 (278)
さてテストが迫ってきたのだが (723)
【和算もｵｯｻﾝも】▲初等幾何ｽﾚｯﾄﾞ2●【代数で解析】 (669)
--log9.info------------------
ロマサガの四天王たんはゆっくりしていけｶﾜｲｲ (313)
【スイギンのいまどき　】　ロマンシングサガ3 (200)
【前張るの】風来のシレンＤＳ【だるい】 (857)
テイルズオブザテンペスト攻略スレ (266)
ファントムキングダム攻略スレ48 (815)
【デビルアクシズ】スーパーロボット大戦64 (707)
【ネタ】ドラゴンフォース・台詞集【バレ】 (342)
なぜｸﾞﾗﾝﾃﾞｨｱ１と２は名作なのかを語り合うスレ (367)
復刻版スーパーロボット大戦GC専用攻略スレPart24 (416)
FF１２　攻略だぜ？ (389)
ローグギャクシーファクトリースレ (544)
PS3の希望ゲーム (308)
【SO4】ｽﾀｰｵｰｼｬﾝ4 THE LAST HOPE 攻略・質問スレ34 (665)
スーパーロボット大戦ORIGINAL GENERATIONS攻略ｽﾚ25 (916)
【PS3】デモンズソウルにありがちな事 (969)
モンスターファーム5改造コード (212)
--log55.com------------------
★2ch.scは何故失敗したのか
★クロール批判要望スレ
★削ジェンヌに文句ある人集合
★迷惑行為報告担当 - 小さな親切募集中 2
★2ch.scへの要望スレ Part3
★かっこう観測所
★スレ立て人キャップ
★2ch.scニュース系板観測所