Drkcore

13112010 Python math

「離散数学への招待」がおもしろい

上巻読み終えたけど、この本はグラフ理論のさわりをおさえるのにちょうどいい難易度だ（難しすぎず、かといって平易すぎもしない）

離散数学への招待〈上〉
J. マトウシェク,J. ネシェトリル
シュプリンガー・フェアラーク東京 / ￥ 2,835 ()
在庫あり。

第2章組合せ的数え上げ
- 2.1 関数と部分集合
- 2.2 置換と階乗
- 2.3 二項係数
- 2.4 評価 ―― 入門編
- 2.5 評価 ―― 階乗関数
- 2.6 評価 ―― 二項係数
- 2.7 包除原理
- 2.8 クローク係嬢の問題
第3章グラフ理論入門
- 3.1 グラフの概念 ―― 同型
- 3.2 部分グラフ，連結成分，隣接行列
- 3.3 次数列
- 3.4 オイラー・グラフ
- 3.5 オイラー回路を求めるアルゴリズム
- 3.6 オイラー有向グラフ
- 3.7 2-連結性
第4章木
- 4.1 木の定義と特徴づけ
- 4.2 木の同型
- 4.3 グラフの全域木
- 4.4 最小全域木問題
- 4.5 ヤルニークとボルーフカのアルゴリズム
第5章グラフを平面に描く
- 5.1 平面や曲面の上の描画
- 5.2 平面的グラフの中の閉路
- 5.3 オイラーの公式
- 5.4 地図の色分け ―― 四色定理

1.4

X Yを任意の集合とする。直感的には、関数fとはXの各元にYの元を一つだけ割り当てる何かである

という記述とその次のページからの関数合成とp.36の関数合成の集合のイメージでHaskellの関数合成のイメージがかなり強く沸いた。

3.3

次数列定理って面白いなと調べたら、Havel-Hakimiアルゴリズムというらしい。perlで書いてあったので、pythonでかいてみた。

def hakimi(deg):
    deg.sort()

    n = len(deg)
    m = deg[-1]

    if m == 0:           return True
    if m < 0:            return False
    if m > 0 and n == 1: return False

    new_deg = []
    for i,v in enumerate(deg[:-1]):
        if i+1 < n-v:
            new_deg.append(v)
        else:
            new_deg.append(v-1)
    return hakimi(new_deg)


if __name__ == "__main__":
    print [1,1,1,2,2,3,4,5,5]
    print hakimi([1,1,1,2,2,3,4,5,5]) # True
    print [2,2,2]
    print hakimi([2,2,2]) # True
    print [3,3,3]
    print hakimi([3,3,3]) # False

4

木の章もおもしろかった(符号化アルゴリズムとか)。

クラスカルのアルゴリズムやヤルニークとボルーフカのアルゴリズム（プリムのアルゴリズム）は読みなおした。そっちに興味がわくようだったら、最短経路の本がより深いのでよいかも。

5

4色定理はいわんとしていることは分かるが証明の過程をきちんと理解しているとは言いがたい。確か図書館に四色定理の本が置いてあったので今度借りてみるかな

四色問題
ロビン・ウィルソン
新潮社 / ￥ 2,310 ()
在庫あり。

Drkcore

代数的構造

代数的構造

群

「数学ガール／乱択アルゴリズム」を予約した

「なわばりの数理モデル」を読んだ

「食える数学」を読んだ

「データ構造とアルゴリズム」を読んだ

「計算論」を(中途半端に)読んだ

離散数学への招待〈下〉

「離散数学への招待」がおもしろい

1.4

3.3

4

5

mimetex入れた