【グラフ理論】離散数学／情報数学 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

749 ：１３２人目の素数さん：2015/03/28(土) 17:24:38.28 ID:Lfr8N1aI.net

代数・幾何・数論の問題にグラフの構造が見出され、しかもグラフ論的考察によって意味のある結果が得られた
という例はありませんか？

750 ：１３２人目の素数さん：2015/03/28(土) 20:35:29.95 ID:g+NJ+mow.net

電気回路解析かな

751 ：１３２人目の素数さん：2015/04/09(木) 21:39:09.46 ID:Yq4DJ3VC.net

音楽用に色々とデジタルフィルタを設計したいと思ってこのページを読んでるんだがな(ex ローパス、ハイパス、スクリーム、コム等々)
http://www.ic.is.tohoku.ac.jp/~swk/lecture/yaruodsp/toc.html

5章まで読んでそろそろ頭が追い付かなく・・・(絶命)
やっぱこれz変換まで全部理解しないと無理ですかね？

752 ：１３２人目の素数さん：2015/04/18(土) 22:09:36.24 ID:0P3y7//s.net

>>750
どう見ても数学の外の問題じゃないか

753 ：１３２人目の素数さん：2015/04/22(水) 20:46:49.62 ID:Cf2TBDii.net

離散数学の入門書、お勧めを教えて下さい。

754 ：１３２人目の素数さん：2015/04/22(水) 20:53:38.85 ID:I45R123Y.net

やさしく学べる離散数学

755 ：１３２人目の素数さん：2015/04/29(水) 02:09:25.41 ID:FdMLhvpF.net

「離散ガール」

756 ：１３２人目の素数さん：2015/07/15(水) 22:57:30.47 ID:OVdxHgUi.net

世界を変える魔法！ アルゴリズミ子研究所 - NHK
ttp://www4.nhk.or.jp/P3285/

カーナビ編でダイクストラ法とか出てくる？

757 ：１３２人目の素数さん：2015/07/23(木) 23:57:13.38 ID:+HrKcfMD.net

>>756
来そうですな。

758 ：１３２人目の素数さん：2015/07/24(金) 00:19:02.56 ID:4mpohRUc.net

>>755
パルプが…もったいなかろう！

759 ：１３２人目の素数さん：2015/08/21(金) 09:16:52.81 ID:JzZKQGbi.net

グラフ理論って実用上無意味な数学じゃね？
圏論よりも実用じゃ使えんと思うぐらいイミフだと思う
圏論はhaskellがあるから意味があるけど

グラフ理論なんてどこで使うのって思うけど反論出来る人いる？

760 ：１３２人目の素数さん：2015/08/21(金) 13:30:51.74 ID:ByIagWLB.net

圏論で扱う図式はグラフだから、グラフ理論は圏論のサブセット

761 ：１３２人目の素数さん：2015/08/21(金) 17:57:23.19 ID:7xlHXt9Z.net

>>760
だったら圏論があればいいじゃろ
グラフ理論なんて謎サブセット誰が喜ぶの？

762 ：１３２人目の素数さん：2015/08/21(金) 18:17:42.11 ID:BJUDjc16.net

んじゃ、代数学があれば、群論や環論とかいらないんか？

763 ：１３２人目の素数さん：2015/08/21(金) 18:23:23.48 ID:k7dziMRV.net

>>761はまず>>760の内容に疑問を覚えるべきだろう

764 ：１３２人目の素数さん：2015/08/21(金) 18:40:35.80 ID:BJUDjc16.net

覚える必要ないじゃろ
サブセットを調べれば役に立つこともある

765 ：１３２人目の素数さん：2015/08/21(金) 20:10:26.44 ID:7xlHXt9Z.net

>>762
それはいるだろw
具体的な構造特定せずに証明したり新しい構造見つけるのに必須だろ
でもグラフ理論いらんだろ？
数学の中で最も役に立たない実用性が皆無だと思うのだが？

766 ：１３２人目の素数さん：2015/08/22(土) 03:36:11.29 ID:1MufEQ7/.net

何を釣りたいんだろうな

グラフ「理論」として語るべきことがどれだけ多くあるかは知らんが
少なくとも様々な事柄の表現方法としてグラフが用いられている以上
その枠組みを整備することに意味がないわけはないし。

まあ、彼の「実用性」という言葉の定義が何か世間と乖離してるのだろう

767 ：１３２人目の素数さん：2015/08/31(月) 19:09:47.70 ID:xfN/nvpB.net

モジュラリティ処理を実装したいんだけど数学と実装が細かく書いてある本ってあるのだろうか？

768 ：１３２人目の素数さん：2015/09/04(金) 21:53:56.33 ID:2bVfeZdA.net

昨日なピザ12枚食っただろ？
今になって腹が痛くなってきたんだけど
救急病院って腹痛でも診てくれるのか？

769 ：１３２人目の素数さん：2015/11/11(水) 13:00:38.72 ID:0vAxwl0s.net

nビットのすべての2進数のうち、偶数個（0個も偶数個と考える）の0を含むものは
何個あるか？

という問題について質問です。

「対称性によりnビットの2進数2^n個のうち半数が0を偶数個含み、もう半数が
0を奇数個含むということに注意すれば、この問題は直ちに解ける。」

と書かれているのですが、対称性というのがよくわかりません。
説明をお願いします。

以下の本に載っている話です：

組合せ数学入門I（共立出版）

著者：
C. L. リウ

訳者：
伊理正夫
伊理由美

770 ：１３２人目の素数さん：2015/11/11(水) 13:10:17.54 ID:0vAxwl0s.net

Concrete Mathematicsって面白いですねー。

H_n = 1 + 1/2 + 1/3 + ... + 1/n

とすると、

H_n = log(n) + γ + 1/(2*n) - 1/(12*n^2) + ε_n/(120*n^4)

ただし、
γ=0.57721...
0 < ε_n < 1

このすごい公式を理解するのが目標です。

771 ：１３２人目の素数さん：2015/11/11(水) 13:16:15.81 ID:0vAxwl0s.net

これって驚異的な精度じゃないですか？

http://wolfr.am/89dUnK4o

772 ：１３２人目の素数さん：2015/11/11(水) 20:34:22.38 ID:0vAxwl0s.net

>>769

nが奇数のときには「対称性」の意味が分かるのですが、nが偶数のときには
言っている意味が分かりません。

773 ：１３２人目の素数さん：2015/11/11(水) 20:39:37.75 ID:0vAxwl0s.net

>>769

自分の解答は以下です。

(1+x)^n = C(n,0)*x^0 + C(n,1)*x^1 + ... + C(n, n)*x^n

x=1とすれば、
2^n = C(n,0) + C(n,1) + ... + C(n, n)

x=-1とすれば、
0 = C(n,0) - C(n,1) + ... + (-1)^n*C(n, n)

よって、
2^n = 2 * (C(n,0) + C(n,2) + ...)
2^(n-1) = C(n,0) + C(n,2) + ...

774 ：１３２人目の素数さん：2015/11/24(火) 03:48:10.83 ID:8cFrdAuA.net

一次合同方程式についての質問です。
2x+31≡ 7x+4(mod 12)という問題です。

正解はx=9(mod 12)なのですが，一部計算が気になります。

自分としては与式を変形すると-5x≡-27(mod12)となると思うのですが
模範解答を見てみると5x≡-27(mod 12)となっており，考え方が良く理解出来ないです。説明をお願いしたいです。以下模範解答を載せておきます

――――――――――――――

5x=-27(mod12)=9(mod12)　ここに(5,12)は互いに素であるから唯一解を持ち
12=5*2+2
5=2*2+1

上式より5x=1(mod12)の解はx=5(mod12)したがって
x=9(mod12)

775 ：１３２人目の素数さん：2015/11/24(火) 08:36:49.05 ID:6g7rXDks.net

単なる誤植というより盛大な間違いだな

776 ：１３２人目の素数さん：2015/11/24(火) 16:33:39.44 ID:Z5L8vrvM.net

http://shudaika.iinaa.net/%E6%AD%8C%E8%A9%9E0058.html
https://www.youtube.com/watch?v=iUIAZs2Lq00 👀
Rock54: Caution(BBR-MD5:0d11aca5c3e7934062b6d1e25bb7a9d7)

777 ：１３２人目の素数さん：2015/11/27(金) 19:44:06.37 ID:k8myT3ei.net

圏論に詳しいなら適当な問題作って圏論を使ったモデルで説明してくれない？
最近独学で勉強し始めて大雑把な理屈はつかめているんだけれど具体的にどういう条件の問題解決に向いているの？

778 ：１３２人目の素数さん：2015/11/27(金) 19:55:02.83 ID:SRJZF0Eb.net

閉路がない制約とは？

779 ：１３２人目の素数さん：2015/12/24(木) 12:43:53.45 ID:OP6SJ76d.net

>>766
グラフ理論の応用と言いながら、実態としてはグラフの考え方を使っているだけで、
純粋数学として得られたグラフの「理論」を直接的に応用する機会がないことを指しているのだろう

780 ：１３２人目の素数さん：2015/12/30(水) 17:00:40.93 ID:k5Blwscu.net

シュテフィ・グラフがセレシュを

781 ：１３２人目の素数さん：2016/02/05(金) 00:05:41.32 ID:00NlNw9S.net

ランダムグラフの質問です
ノード数n,各リンク生成が等確率pの有向ランダムグラフが与えられたとき,全てのノードが強連結する確率を見積もる公式は存在しますか?
無向グラフの連結確率はよく見かけるのですが･･･

782 ：１３２人目の素数さん：2016/03/13(日) 07:27:05.61 ID:1NkoRZjS.net

組み合わせ論
組合せ論

どっちが正しいの？

783 ：１３２人目の素数さん：2016/03/13(日) 19:17:12.05 ID:7de8Bui2.net

組合論

784 ：１３２人目の素数さん：2016/06/09(木) 17:08:33.36 ID:xIJE9U0K.net

http://imgur.com/uEZVSB8.jpg

グラフ理論の話ですが、木というものがあります。
↑のように根付き木を定義しているグラフ理論の本はありますか？

785 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:47:31.19 ID:8aYbGgjJ.net

￥

786 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:47:51.00 ID:8aYbGgjJ.net

￥

787 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:48:12.22 ID:8aYbGgjJ.net

￥

788 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:48:31.60 ID:8aYbGgjJ.net

￥

789 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:48:50.79 ID:8aYbGgjJ.net

￥

790 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:49:10.94 ID:8aYbGgjJ.net

￥

791 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:49:30.59 ID:8aYbGgjJ.net

￥

792 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:49:52.25 ID:8aYbGgjJ.net

￥

793 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:50:12.64 ID:8aYbGgjJ.net

￥

794 ：￥ ◆2VB8wsVUoo ：2016/06/09(木) 21:50:33.35 ID:8aYbGgjJ.net

￥

795 ：１３２人目の素数さん：2016/07/06(水) 00:03:08.38 ID:+a3NyTuQ.net

ビルド自動化ツールのMakeのように、これを構築するには前もってこれとこれとこれを構築しておかなければならないといった情報を元に、全体としてどういう順番で仕事をこなしていけばいいかを返すアルゴリズムを考えたいです。
用途はTODOリスト作成システムやゲームのイベントの因果関係管理です。
そのためにグラフ理論の入門レベルは勉強しといた方が良いですか？

入門書を教えてください。理系なので数式バリバリでも泣きません。

796 ：１３２人目の素数さん：2016/07/06(水) 01:21:46.03 ID:V7Y1MhrF.net

>>795
「トポロジカルソート」について調べろ
大抵のアルゴリズムの教科書にグラフの初歩とともに書いてある

797 ：796：2016/07/06(水) 02:21:44.19 ID:+a3NyTuQ.net

>>796
はい頑張ります

798 ：１３２人目の素数さん：2017/11/01(水) 22:16:03.44 ID:N2cwEHUQd

グラフ理論おもろいからみんなも知ってな.