2021年度：幾何学序論II
連絡事項
講義の情報はWebClassをご覧ください．
グラフ理論の基本的なことについて概説します。
講義内容
1.グラフとは？握手補題
2.グラフの用語と最短経路問題
3.Eulerグラフ
4.Hamiltonグラフ
5.木について，Kruskal's algorithm，中国人郵便配達人問題，巡回セールスマン問題，
6.有向グラフ
7.平面的グラフ，Pick の定理，厚さと交差数
試験1
8.Max-flow min-cut，Ford-Fulkerson algorithm
8.マッチング，結婚定理，König-Egerváry の定理，Menger の定理
9.彩色可能性
10.Chromatic polynomial
11.Cycle polynomial
12.グラフの数え上げ
13.サイクル空間とカット空間
14.Tutte polynomial
試験2
2020年度：幾何学序論II
連絡事項
講義の情報はWebClassをご覧ください．
グラフ理論の基本的なことについて概説します。
講義内容
1.グラフとは？握手補題
2.グラフの用語と最短経路問題
3.Eulerグラフ
4.Hamiltonグラフ
5.木について，Kruskal's algorithm，中国人郵便配達人問題，巡回セールスマン問題，
6.有向グラフ
7.平面的グラフ，Pick の定理，厚さと交差数
試験1
8.Max-flow min-cut，Ford-Fulkerson algorithm
8.マッチング，結婚定理，König-Egerváry の定理，Menger の定理
9.彩色可能性
10.Chromatic polynomial
11.Cycle polynomial
12.グラフの数え上げ
13.サイクル空間とカット空間
14.Tutte polynomial
試験2
2019年度：幾何学序論II
連絡事項
グラフ理論の基本的なことについて概説します。
講義内容
1.グラフとは？握手補題
2.グラフの用語と最短経路問題，3.Eulerグラフ
4.Hamiltonグラフ，5.木について
5.Kruskal's algorithm，中国人郵便配達人問題，巡回セールスマン問題，6.有向グラフ
6.有向グラフ，7.平面的グラフ，Pick の定理，8.Max-flow min-cut
7.平面的グラフ，8.Max-flow min-cut，Ford-Fulkerson algorithm
7.平面的グラフ，厚さと交差数，8.マッチング，結婚定理，König-Egerváry の定理，Menger の定理，9.彩色可能性
9.彩色可能性，10.Chromatic polynomial
11.Cycle polynomial
中間試験と演習
課題の添削，12.グラフの数え上げ
12.グラフの数え上げ，B.サイクル空間とカット空間
13.Tutte polynomial
群に値を持つ flow，flow polynomial，flow と彩色の双対性
ラマヌジャングラフ，ラムゼー理論
研究発表会
研究発表会タイトル
トーナメントにおける優勝可能性判定
完全グラフの一次元ホモロジー群のランク
クラトウスキーの定理の証明
ブルックスの定理の証明
握手の問題の一般化
ピックの公式の一般化