離散最適化基礎論

岡本 吉央

テーマ：グラフの準同型

注意：内容は毎年変わります

ショートカット： 講義資料 | コメント | レポート・評価 | 公式シラバス | スケジュール | 参考書 | 過去の講義

講義資料

• 1/25 (14) アルゴリズム (4)：多数決
  • 前回の続きから始めます
  • スライド (1/28修正) | 印刷用スライド (1/28修正)
  • 講義動画
• 1/18 (13) アルゴリズム (3)：双対性
  • スライド (1/18修正) | 印刷用スライド (1/18修正)
  • 講義動画
• 1/11 (12) アルゴリズム (2)：整合性
  • スライド (1/11修正) | 印刷用スライド (1/11修正)
  • 講義動画
• 1/4 (11) アルゴリズム (1)：例
  • スライド | 印刷用スライド
  • 講義動画
• 12/21 (10) 準同型が導く半順序 (2)：構造
  • 前回の残りから始めます
  • スライド (2/22修正) | 印刷用スライド (2/22修正)
  • 講義動画
  • 補足動画
• 12/14 (9) 準同型が導く半順序 (1)：構成
  • スライド | 印刷用スライド
  • 講義動画
• 11/30 (8) グラフのコア
  • スライド (12/2修正) | 印刷用スライド (12/2修正)
  • 講義動画
• 11/16 (7) グラフの商と引き込み
  • スライド | 印刷用スライド
  • 講義動画
• 11/9 (6) グラフの積と準同型
  • 前回の続きから始めます
  • スライド (11/10修正) | 印刷用スライド (11/10修正)
  • 講義動画
  • 補足動画
• 11/2 (5) グラフの分数彩色
  • スライド (11/10修正) | 印刷用スライド (11/10修正)
  • 講義動画
• 10/26 (4) グラフの円彩色
  • スライド (10/26改訂) | 印刷用スライド (10/26改訂)
  • 講義動画
  • 補足動画
• 10/19 (3) 準同型の基本性質 (2)：準同型の合成
  • スライド (10/21修正) | 印刷用スライド (10/21修正)
  • 講義動画
  • 前回の続きからやります
• 10/12 (2) 準同型の基本性質 (1)：部分構造
  • スライド (10/13修正) | 印刷用スライド (10/13修正)
  • 講義動画
• 10/5 (1) グラフの彩色と準同型
  • スライド (10/13修正) | 印刷用スライド (10/13修正)
  • 講義動画

• 1/25 (14) アルゴリズム (4)：多数決
  • コメントありがとうございました．
  • 準同型のように告白したら、振られてしまいました。なぜでしょうか。
    -- さて，なぜでしょうか ;-)
  • この講義おもしろかったです。レポートがんばります。
    -- はい，レポートにしっかりと取り組んで下さい．
  • 後学期間ありがとうございました。
    期末レポートにもしっかりと取り組み、さらに理解を深めていきたいと思います。
    -- こちらこそありがとうございました．レポートにしっかりと取り組んで下さい．
  • 半年間ありがとうございました。
    -- こちらこそありがとうございました．
  • お世話になりました。
    -- こちらこそありがとうございました．
  • ありがとうございます。レポート課題に頑張ります。
    -- こちらこそありがとうございました．レポートにしっかりと取り組んで下さい．
  • 授業ありがとうございました。レポートに苦戦しているので、この授業でグラフと準同型について全て理解出来たとはとても言えませんが、奥深さは少し理解できたと思いたいです。
    -- 奥深さが伝わったのなら，なによりです．離散最適化や離散アルゴリズムは「何か適当にやれば，適当によさそうなものが得られる」と思われていることも多いので，実際はそういうものではないということが少しでも理解できれば，この講義を履修した意味はあったと思います．
  • 半年間ありがとうございました．弧整合性アルゴリズムより対整合性アルゴリズムの方が強力であるのに，多数決多型写像はアリティ3の場合のみを考えればよいというのは不思議に感じました．
    -- 多数決多型写像の存在性は，対整合性検査アルゴリズムで解けるための必要十分条件を与えていないことがポイントだと思います．ある意味で，多数決多型写像の存在性は，多項式時間でH彩色問題が解けることを証明するための，簡便な判定法であると捉えるとよさそうです．
• 1/18 (13) アルゴリズム (3)：双対性
  • コメントありがとうございました．次回が最終回となります．第2回レポートも出題されますので，しっかりと取り組んで下さい．
  • 寒すぎて布団から出れません
    -- 気持ちはよくわかります．;-)
  • 今日もありがとうございました。
    -- こちらこそありがとうございました．
  • ありがとうございました.復習時,単純に忘れてしまっていたところが結構あったので知識を入れなおしつつレポートに取り組みたいです...
    -- はい，しっかりと復習をして下さい．
  • レポート頑張ります
    -- はい，よろしくお願いします．
  • 他の授業のレポートも続々と出てきているので計画的に進めていきたいです。
    -- そうですね．学期末はいろいろなことが重なりますので，計画的に進めて下さい．
  • 今回の内容は難しかったのですが，例がたくさんあって理解できました．T_{v, x} が木の向き付けであるというのも不変条件になっているのですね．
    -- そのとおりですね．$T_{v,x}$ が木の向き付けである，というのも不変条件ですね．
  • 僕には好きな人がいます。ですが、今の関係が崩れてしまうかもしれないと考えると、なかなか告白する勇気を持つことができません。どうすればいいですか。
    -- グラフ準同型によれば，アクションのあと (準同型写像で写したあと) でも，関係 (辺) は保たれるそうです．グラフ準同型のように告白すれば，関係が崩れることはないことになります．ぜひ試してみて下さい．
• 1/11 (12) アルゴリズム (2)：整合性
  • コメントありがとうございました．
  • 「完全対称多型写像と冪グラフ：証明 3 → 1」において，アリティ 2|V(H)| という条件がどのように用いられているのか理解できませんでした．
    -- 質問ありがとうございます．$g(X)$ から $g(Y)$ に弧があることを証明するとき，$|X|=p$，$|Y|=q$ であるとしていましたが，このとき，$p \leq |V(H)|$ と $q \leq |V(H)|$ が成り立ち，場合によっては，$|X|=|Y|=|V(H)|$ になります．そのため，$f$ のアリティを $2|V(H)|$ (以上) にしておかないと，この証明の方法 (たとえばスライド31ページの最後の部分) では，うまく準同型 $g$ を作ることができなくなってしまう，という都合です．
  • 整合性検査はH彩色問題を解くための前処理として使い、最終的に指数関数アルゴリズムで解く感じなのですね。聞き逃してしまったのかもしれませんが、整合性検査はそもそもH彩色可能かを判断するために使う感じなのでしょうか？
    -- そもそものことをいえば，前処理の方が先であるはずです．いろいろな種類の整合性検査はWikipediaの記事にも書いてありますので，参考にして下さい (ただ，ここではH彩色問題よりも一般的な制約充足問題の文脈で書かれています)．
  • 本日の講義の後半の内容が講義内では理解しきれなかったため、復習をしたい
    -- はい，分からない所があればご質問をお願いします．
  • ありがとうございました.レポートに向けてしっかり復習します.
    -- はい，しっかりと復習をお願いします．
  • レポート課題２のこと心配しているから、ちゃんと復習します。
    -- はい，ちゃんと復習をお願いします．
• 1/4 (11) アルゴリズム (1)：例
  • コメントありがとうございました．掲載が遅くなり，すみません．
  • 明けましておめでとうございます。
    -- あけましておめでとうございます．
  • あけましておめでとうございます。本年もよろしくお願いします。
    -- あけましておめでとうございます．
  • ありがとうございました。今年もよろしくお願いします。
    -- こちらこそよろしくお願いします．
  • 現在23才ですが、学生だと主張したら親戚からお年玉がもらえました。大学院に入ってよかった！
    -- それはおめでとうございます ;-)
  • 第1回レポートを解きなおして再提出することは可能でしょうか。
    可能な場合、簡単でよいのですが解き方があっているかどうかの添削はしていただけるのでしょうか。
    また、再提出することによって評価が変わることはあるのでしょうか。
    成績の質問ばかりで申し訳ないです・・・
    -- そのような質問でも全然問題ありません．:-)
    再提出することは可能ではありません．既に提出されたもののみに基づいて採点を行ないます．よろしくお願いします．
  • 中間レポートですが、問1が問われていることに答えられていないとのことでしたがなぜそのように言われたのか分かりませんでした…。
    -- そのようなこともあるかと思います．なお，書いてあるメモは私の個人的なメモなので，フィードバックを意図したものではありません．その点はご了承ください．
  • 期末レポートの期限が卒論発表の翌日ということでできる気がしませんが頑張ります。対戦よろしくお願いします。
    -- こちらこそよろしくお願いします．
  • 対整合性検査アルゴリズムは、多項式時間なので指数時間などに比べれば圧倒的に速いとはいえ、7乗オーダーというのは、H彩色問題はかなり難しい問題なのだなと思いました。
    -- 対整合性検査は頑張れは3乗オーダーまで落とすことができると知られています．また，これらの計算量は最悪時のものなので，実際はもっと早く実行できる可能性もあります．
    弧整合性検査や対整合性検査は，それだけでH彩色問題を解こうとするというよりは，H彩色問題を解くための前処理として使われるというイメージの方が正しいのかもしれません．その意味では，指数関数アルゴリズムの中で使われるサブルーチンであるということになるので，速ければ速い方が望ましいのは確かですが，他の部分が計算のボトルネックとなることの方が多いのではないかと推測します．
  • 新しいアルゴリズムを知って、やはりアルゴリズムは面白いなと思いました。
    次週に向けてしっかりと復習したいです。
    -- はい，復習をよろしくお願いします．
• 12/21 (10) 準同型が導く半順序 (2)：構造
  • コメントをありがとうございます．稠密性の部分は補足動画としますので，皆さんは自習で確認して下さい．
  • ありがとうございました。
    -- こちらこそありがとうございました．
  • 本年度はありがとうございました。
    全くの専門外でこの講義を受講したのですが、回を重ねるごとにグラフの奥深さを知ることができ有意義でした。
    また来年度もよろしくお願いいたします。
    -- それはとても有難いです．準同型の話の奥深さをすべて伝えることはできませんし，すべてを私が理解できているとも思えないのですが，それでも何かをお伝えできていることが分かり，うれしいです．
    ちなみに「年度」は4月に始まり，3月に終わるので，まだ本年度は終わっておりません．今年度の残りもよろしくお願いします．
  • 稠密さのお話が面白かったので証明の補足動画も楽しみです
    -- お楽しみに ;-)
  • 準同型写像は辺を移すイメージなので、辺が存在して頂点数最小のグラフK_2がスタートとして、そこから先が稠密になっていくのは自然に感じました。
    -- 私は自然な部分と不思議な部分が混在するように感じています．例えば，完全グラフの列 $K_1 \to K_2 \to K_3 \to \cdots$ において，($K_1$ と $K_2$ の間を除いて) 円完全グラフを考えることで，この列の間を埋めて稠密にすることができます．その意味で稠密であるというのは自然に思えます．一方で，稠密性の議論は ($K_1$ と $K_2$ の間を除く) どのグラフの間でも成立します．これは割と不思議だと思います．$K_1$ と $K_2$ の間を除くどのグラフの間にも，無限のグラフからなる稠密なスペクトルが見られるわけです．
    もう一つ不思議な点を挙げます．この稠密性の話は有向グラフではもっと多くの箇所で成り立たなくなります．つまり，有向グラフ $G$，$H$ で $G < H$ であるけれども，$G < X < H$ を満たす有向グラフ $X$ が存在しないような $G$ と $H$ の組が無限にあります (無向グラフのときは，$K_1$ と $K_2$ のみでした)．
  • アルゴリズムの部分を楽しみにします。
    -- はい，お楽しみに．
• 12/14 (9) 準同型が導く半順序 (1)：構成
  • コメントをありがとうございます．コメントの提出数が少なくなってきていますので，皆さん必ずコメントを提出するようによろしくお願いします．
  • ありがとうございました。
    --こちらこそありがとうございました．
  • ありがとうございました。
    --こちらこそありがとうございました．
  • 復習します。
    --はい，しっかりと復習をして下さい．
  • 商集合や同値類に関しては以前学習したことがあったので，今回の内容はよく理解できました．
    --そうですね．商集合や同値類は離散数学で扱っていることもあるかと思いましたが，忘れていることもありそうですので，復習も兼ねて紹介しました．
  • 講義ありがとうございました。レポート課題1の採点結果はいつ頃Classroomに反映される予定でしょうか。
    --採点が終わり次第，お返しします．
  • 第二回のレポートは本日の講義以降の問題が多く出題されると思うので、第一回レポートが終わったからと言って気を抜かずに学習を続けていきたいです。
    --はい，分からない部分は質問をして下さい．よろしくお願いします．
  • 人はなぜこんなにも愚かなのでしょう。何度経験しても、レポートが〆切ぎりぎりになるし、記憶違いでミスを犯す。完璧には程遠い...
    --完璧であろうとする必要はないのだと思います．できる限り完璧に近づこうとする努力は必要だと思いますが，完璧でなかった過去を省みるよりも，次は完璧により近づけるように考えることが重要なのではないかと思いました．
• 11/30 (8) グラフのコア
  • コメントをありがとうございます．
  • ありがとうございました.
    -- こちらこそありがとうございました．
  • 今週もありがとうございました．
    -- こちらこそありがとうございました．
  • 復習頑張ります
    -- はい，よろしくお願いします．
  • 午前中の講義は寒くておっくうになりがちです
    -- 暖かくしてご出席ください :-)
  • ややこしかったけど一応理解はできた（気でいる）
    -- 動画もありますので，ぜひ活かして下さい．
  • 課題は難しいと思います。。ちゃんと復習します。
    -- はい，復習しながら取り組んで下さい．
  • 来週レポートの提出期限なので、よく考えたうえで提出したいと思います。
    -- 忘れずに提出するようにして下さい．
  • 授業中に聞く性質などの証明は理解できますが、いざレポートで未知の問題を自分で証明をしようとすると難しいですね...
    -- それだから，レポートがあるのです ;-)
  • グラフのコアは研究で役立ちそうな内容でした。しっかり復習して身につけたいです。
    -- ぜひ役立ててみて下さい．
  • グラフのコアを見つけるのと、グラフをそのまま彩色していくのとでは、どの程度計算量に違いがあるのですか？
    -- 理論上，グラフのコアを見つけるという問題はNP困難です．より細かくいうと，グラフがコアであるか判定することがNP困難です．実用上は，コアでなくてもレトラクトを見つけることができれば，それによって計算量を削減することができます．ただ，(コアでなくても) 小さなレトラクトを実用上見つけようとすることは一般的に難しいことだともいます (これは推測です)．ただ，うまく見つけることができれば，強力な方法になると思います．
  • ゲーム理論にもコアと呼ばれる概念が存在しますが，ゲームのコアは空集合になることがあるのに対し，グラフ理論では任意のグラフにコアが存在し，しかもそれが同型になるというのは同じ用語を使っているのにかなり差があるな，と感じました．
    -- そうですね．異なる概念に同じ用語が使われることがあるので，混乱のないようにお願いします．グラフにおいても，社会ネットワークの文脈で全く別のものがコアと呼ばれることがあります．
• 11/16 (7) グラフの商と引き込み
  • コメントをありがとうございます．11月23日にレポート課題1を出題しますので，しっかりと取り組んで下さい．
  • ありがとうございました。
    --こちらこそありがとうございました．
  • 復習します。
    --はい，よろしくお願いします．
  • レトラクトのあたりからあまりついて行けませんでした
    --すみません，「商」のところで時間を使い過ぎたような気がしています．まずは定義をしっかりと理解するようにして下さい．それができれば，証明のなかで行っていることは案外単純です．
  • コアの一意性の証明がよくわからなかったので復習します．
    --そうですね．ここはあまりうまく説明できなかったような気がします．まずはその事実が重要なので，それ自体は受け入れられるように理解して下さい．
  • 「準同型写像の拡大」の辺りの図はまさに可換図式という感じがしますね。
    --そうですね．この授業は圏論をやっているわけではないので，可換図式をあまり意識しないようにしていますが，完全に避けるのは難しいようです．;-)
  • 🤔 <- これ好き
    --私も好きです．皆さんも，分からない所があればどんどん使って下さい．できれば，何が分からないのかということもコメントで流して頂けると，私も答えやすいので助かります．
  • 大学に直接行けてないので調布祭が近いという実感がわかないです...
    --分かります．特に，オンサイトのイベントがないので，雰囲気を感じ取ることが難しいですね．
  • 本格的に寒くなってきました。寒さが苦手なのでしんどいです。
    --季節の変り目は体調を崩しやすいので，ご注意ください．
  • 来週は休校ということで、今週と来週のレポートで講義前半部分の理解度をより深めたいです。
    --はい，よろしくお願いします．
• 11/9 (6) グラフの積と準同型
  • コメントありがとうございます．
  • ありがとうございました！
    --こちらこそありがとうございました．
  • 毎回何かしらコメントしようとして忘れてしまいます。
    どうすればいいでしょうか？
    --コメントは授業開始時点から13:00まで，いつでもできます．コメントを思いついたら，その都度提出するということもできますので，ぜひ活かして下さい．フォームからは何度でも提出できるはずです．(もしできなかったら，私の設定が間違っていることになるので，お知らせください．)
  • 最近、何をやるにもやる気がないです。どうしたらいいですか？
    --電気通信大学には「学生何でも相談室」があります．ぜひそちらで相談して下さい．私が変なアドバイスのようなものを行うよりも，専門家に相談する方がよいに違いありません．
  • そういえば本講義では演習問題がないんですね
    --はい，演習問題はありませんので，皆さん自身で復習を行なって下さい．
  • 累乗の部分は確かにややこしいとおもいますから、復習します。
    --復習をよろしくお願いします．
  • 補足動画もしっかり見直します.
    --はい，補足動画も準備できていますので，ご覧ください．
  • グラフの演算の定義が分かりやすかった。
    --ぜひ皆さん自身でも例を作って確認してみて下さい．
  • グラフの累乗が講義内の説明では理解できなかったので、講義動画を振り返って復習したいです。
    --確かにややこしくて，私自身もあまり理解できているような感じがしません ;-)
  • 無向グラフHと無向グラフGに対してH^Gが無向グラフに関係してくるのが準同型というのが思いもよらなくて興味深かったです。
    --実をいうと，無向グラフというのは案外扱いにくい対象なので，授業でも述べたように，有向グラフとして扱うということが多いです．例えば，グラフを表現するためのデータ構造として隣接リストというのがありますが，これは有向グラフに対して定義してから，無向グラフに対してはそれを有向グラフに一旦変換して定義する，という方法で導入することもあります．他にも，平面グラフを表現するためのデータ構造であるdoubly connected edge listやcombinatorial mapも無向グラフを有向グラフに変換して考えていると見なせます．
  • 集合の演算を考えていくのかと思っていたので、グラフでも演算ができることに感心しました。
    --そうですね．このような演算を考えることは圏論でよく行い，その操作をグラフに限定して説明すると，今回のような紹介の仕方になります．興味がありましたら，ぜひ圏論も勉強してみて下さい．
  • 「H の G 乗」なのに写像は V(G) から V(H) に取るのが不思議でした．ところで，スライド21ページのグラフでは，例えば頂点 11 から頂点 13 へは弧が引かれないのでしょうか？
    --はい，ご指摘ありがとうございます．スライド21ページの図は間違っています．それに伴って26ページの図も間違っています．直しておきます．誤解を生んでしまい，すみませんでした．
    HのG乗と書くことで，HのG乗の頂点数 = Hの頂点数のGの頂点数乗 ($|V(H^G)| = |V(H)|^{|V(G)|}$) という直感的な等式が成り立つという利点があります．また，一般に，集合 $X, Y$ に対して，$X$ から $Y$ への写像全体の集合を $Y^X$ と書くので，それにも対応しています．
  • グラフの累乗が面白かったです。ここまでくると対数も考えてみたくなりました
    --例えば，$H^G \simeq K$ であるとき，$K$ と $H$ から $G$ を定めることができるならば，$G$ が $\log_H K$ であると見なすことはできそうですね．圏論を使う型システムの理論ではそのような概念を考えることがあるようです．
  • 何か新しい概念が定義されるたびに、色々な性質が成り立ってうれしいなあと思うのですが、ある程度都合の良い定義を考えるものなのでしょうか。
    --都合の良いように定義を考えています．例えば，授業でも述べた通り，グラフの積の定義にはいろいろなものがあるのですが，準同型と相性がよいのは授業で紹介した圏論的積になります．
    数学においては，「都合の良いように定義をする」ということはとても重要です．つまり，何かを定義したときに，それが満たしている性質や満たすべき性質が何であるのかを明らかにすることがとても重要なのです．それを使うことで，様々な事項を証明したり導出することができるようになります．
• 11/2 (5) グラフの分数彩色
  • コメントありがとうございます．次回は今回の続きから行います．
  • ありがとうございました。
    --はい，こちらこそありがとうございました．
  • ありがとうございました。復習頑張ります。
    --はい，分からない所がありましたら，質問をお願いします．
  • ちゃんと復習したいと思います
    --動画もありますので，ぜひ活かして下さい．
  • 定義などが頭から抜けていることがあり、証明の途中で理解できない部分が増えてきたので、過去の資料などを参考に見直したいと思います。
    --まず，授業中にも述べましたが，覚えようとしないで下さい．覚えようとしてもどうせすぐ忘れますから．授業の途中で忘れてしまったら，過去の資料を見返すか，その場で質問して下さい．いろいろなことを忘れるのは当然ですから，忘れたことで怒られる心配は全然ありません．安心して下さい ;-)
  • 手書きグラフの作成時間が気になりました.
    --KG(7, 3)の図は2時間ぐらいかかってると思います．頂点の配置など，いろいろな部分で試行錯誤があります．
  • KG(n, k) \to KG(n-2, k-1) という性質の証明が正しいことは理解できましたが，この写像 f の構成は自分には思いつきそうにないです．
    --自分で思いつくのは難しいかもしれません．その前に，まずこれが正しいと思いつくことが難しいような気がします．Kneserグラフの間にどのような準同型が存在するのか，という点には不思議な部分が多く，未解決問題も多くあります．
  • 準同型の存在性 (3) の内容があまり理解できなかったのでもう一度よく見直したいと思います。
    --この部分は難しいですし，授業でもちゃんと説明できなかったので，ぜひ復習して下さい．そして，分からない部分がありましたら，ぜひ質問して下さい．
  • kneserグラフに関する証明がパズルゲームみたいで面白かったです
    --こういうのを面白く感じられるようになってくるのは，頭が組合せ論に支配されてきている証拠かもしれませんね．ご注意ください．
  • 自分が聞き逃してしまったのかもしれませんが、KneserさんはどうしてKneser グラフを研究しようと思ったのか気になります。
    --Kneser自身は，ある数学雑誌に「問題」としてあるグラフの染色数に関する問いを出題しました．これは1955年のことで，そのグラフがKneserグラフと今日呼ばれるものになりました．Kneserグラフの染色数を決定するという問題自体は，長いこと未解決だったのですが，Lovászが1978年に解決しました (これについては次回述べます)．なぜKneserがKneserグラフの染色数を知りたがったのか，ということはよく分かりません．私の限られたドイツ語の能力によると，1955年の論文には問題が書いてあるだけで，なぜその問題に至ったのかという経緯は書いてないように見えました．しかし，Kneserグラフは分数染色数と関係があることが知られ (当初，分数染色数はKneserグラフを使わず，線形計画法を用いて定義されたのですが，それがKneserグラフへの準同型と同じであるということが今では分かっているのです)，また，Kneserグラフ自体が高い対称性を持つ興味深い研究対象であることが分かり，現在では盛んに研究されることとなっています．
  • \mathfrak{A}をAと読むのに5秒くらいかかってしまいます。そのうちパッと出てくるようになるだろうと思ったまま2年が経ちました :-(
    --たしかに難しいですね．フラクトゥール体は数学でよく使うのですが，数学では文字や書体の不足にいつも悩まされています．日本語の文字を使うことができれば，その辺りの悩みはかなり解決されると思うのですが，あまり流行していません．残念です．
  • 最近、寒かったり暖かかったり、服装の最適解がわかりません。どのように定式化すれば良いでしょうか？
    --最適化問題としてモデル化する際には，まず「決定変数が何であるか」，「目的関数が何であるか」，「許容領域が何であるか (制約が何であるか)」を見極めることが重要です．モデル化の方法は様々あり得ると思います．ぜひ自分なりのモデルを考えてみて下さい．
• 10/26 (4) グラフの円彩色
  • コメントありがとうございます．今回は私の間違いが多く，ご迷惑をおかけしました．「円完全グラフの間の準同型写像」に関する証明について，授業では次回行う，と言いましたが，補足動画として別の動画で扱うことにしました．そのため，次回の授業で証明をしないことになりました．よろしくお願いします．また，最後の $\chi(G) = \lceil \chi_c(G) \rceil$ についても，補足動画で補足しながら証明を再び行いました．ぜひ参考にして下さい．
  • 来週もよろしくお願いします
    --はい，よろしくお願いします．
  • 最後の円染色数と染色数の証明がよくわからなかったので後で見直そうと思います。
    --補足動画で説明を追加したので，そちらもご覧ください．
  • 円染色数と染色数の性質の証明がよくわからなかったので、あとで見直そうと思います。
    --補足動画で説明を追加したので，そちらもご覧ください．
  • 難しくなってきたと感じるので復習を頑張ります！
    --はい，よろしくお願いします．
  • きちんと復習します。
    --はい，よろしくお願いします．
  • 理解はできますが少し難しいなと感じました。
    --確かに難しくなってきてると思います．前の講義で出てきた概念を気兼ねなく使うようになっているので，前の講義からのつながりを意識するようにして下さい．
  • あまり授業に付いて行けていなかったので復習します
    --はい，よろしくお願いします．
  • しっかり見直して復習しようと思います
    --はい，よろしくお願いします．
  • 本講義から本格的に円グラフを扱ったため、少し理解が及ばない部分がありました。
    なので、個人での復讐の時間を十分とり、来週の講義までには理解して臨みます。
    --実をいうと「円グラフ」ということばは円完全グラフとは違うものを指すことが多いです．日本語で「円グラフ」というと，英語のpie chartを表すことが多く，また，英語でcircle graphやdisk graphと呼ばれる概念もあるのですが，これらも円完全グラフとは違うものを指します．細かい区別になりますが，ご注意ください．
  • グラフを描画する際に、頂点に面積があったり辺に太さがあったりして見辛くなるの、気に食わないですね。もちろん、なければ人間の目には見えませんが。
    --同意します．これはかなり根深い問題であって，情報可視化における基本的な問題と切実に関係します．
    例えば，Wikipediaのリンク構造をネットワークだと見なして，それを描画したいと思ったとします．英語版Wikipediaの記事数は (2021年10月27日現在) 640万程度ですが，スーパーハイビジョンの画素数は大体330万ぐらいです．つまり，1つの記事を1画素で表そうとしても，スーパーハイビジョンをもってしても，そのようなネットワークは描画できないということになります．
    数学的に，点は大きさを持たず，線も太さを持たないことになっているのですが，現実にはそのように表現することができないので，大きさや太さを持たせることになります．しかし，そうした瞬間にいろいろな制約に見舞われることになるのです．理想化によって解析を単純化するというのは，物理学でもよく行われることですが，それによって失われる側面にも気をつけないといけないわけです．そうしないと，実世界のシステムをうまく設計できなくなります．
  • 円完全グラフの有理数っぽさが分かって楽しかったです
    --この点について，授業の中でちゃんと説明できなかったので，補足します．完全グラフの間には $K_1 \to K_2 \to K_3 \to K_4 \to \cdots$ という形の準同型の列が存在していました．これは $1 \leq 2 \leq 3 \leq 4 \leq \cdots$ という自然数の大小関係に対応しているように見えます．円完全グラフの間の準同型は，これらの自然数の間にある有理数の間の大小関係に対応していることになります．例えば，$K_{17/5} \to K_{7/2}$ という準同型は $\frac{17}{5} \leq \frac{7}{2}$ に対応し，$K_{7/2} \to K_{14/4}$ かつ $K_{14/4}\to K_{7/2}$ であることは $\frac{7}{2}\leq \frac{14}{4}$ かつ $\frac{14}{4} \leq \frac{7}{2}$，つまり，$\frac{7}{2}=\frac{14}{4}$ に対応します．しかも任意の有理数 $\frac{p}{q}$ に対して円完全グラフ $K_{p/q}$ を考えることができるので，例えば，$K_2$ と $K_3$ の間には $2$ よりも大きく $3$ よりも小さい有理数から作られる無数の円完全グラフの間の準同型の列が挟まっていることになるのです．前々回に，$K_2$ と $K_3$ の間には無数の奇閉路が挟まっていることを紹介しましたが，奇閉路同士の間にも無数の円完全グラフが挟まっていることになり，このような「無数の準同型の列が挟まっている」というような構造が「準同型が存在する」という二項関係 $\to$ にはあることになります．これは後の方の講義の主題と関係してきます．
  • 円完全グラフの定義K_{p/q}のp/qはうまく設定されていると思いました。
    -- そうですね．特に，$p/q = p'/q'$ のとき，$K_{p/q} \to K_{p'/q'}$ かつ $K_{p'/q'} \to K_{p/q}$ となるというのはとてもきれいな性質ですね．
  • 円完全グラフの間の準同型がすごい性質だと思います。証明が長いですね。
    -- 証明については，補足動画で説明し直しましたので，ぜひご覧ください．
  • 円完全グラフ、きれいですね
    --きれいに描くことには尽力しています :-) スピログラフというものをご存知でしたら，ぜひ遊んでみて下さい．円完全グラフではないですが，きれいな絵が描けます．
  • 円彩色に関する問題の計算複雑性についてはどの程度知られているのでしょうか？
    -- 実を言えば完全に分かっています．これはつまり，与えられた円完全グラフ $K_{p/q}$ への準同型写像が存在するかどうか判定する問題の計算複雑性を考えることになりますが，$K_{p/q}$ が二部グラフであれば多項式時間で解け，そうでなければNP完全になります．これは初回の最後に紹介した二分定理と関係します．
  • 言われてみれば納得ですが、=を示すのは難しいというのが今まで意識していなかったので印象的でした。
    --そうですね．まず無意識に行っていることを意識する，というのがコンピュータサイエンスにおいて非常に重要なプロセスだと思っています．それを踏まえて，等号を示すということが両向きの不等号を示すことだと意識することはとても重要で，その視点がうまく使えるようになると，証明できる事項の幅がぐっと広がると思います．
  • 「コードネーム」というゲーム、知らなかったので調べましたがやってみたいなと思いました。話は変わりますが、岡本先生は、完全解析された完全情報ゲームに未来はあると思いますか?私は、私たちのようなアマチュアが楽しむ分には全く問題ないとは思いますが、仮に将棋が完全解析された日にはプロ棋士同士の対局は面白さが半減するのではないかと思います。例えば、「振り飛車党が絶滅する」「後手が千日手を目指すという別のゲームに変わる」など。
    --後半のご質問について，いろいろな意見や考えがあると思いますが，私の意見をここでは書きます．
    完全解析が行なわれることで将棋や囲碁の神秘さは失われることになるかもしれません．しかし，ゲーム自体の面白さが変わるようにはあまり思えません．というのも，完全解析された結果を人間が記憶することは不可能だと思うからです．たとえ「先手必勝」だということが分かったとしても，必勝手順を生身の人間が逐一追っていくことは現実的だと感じられません．一方で，それによって「振り飛車党が絶滅する」とかそういうことはありうるかもしれません．しかし，それは完全解析がなかったとしても，戦術としての有効性に関する側面として起きうる事象だと思います．
    ただ，必勝手順を記憶できてしまうほどの規模のゲームであれば，面白さがなくなってしまうと思います．
• 10/19 (3) 準同型の基本性質 (2)：準同型の合成
  • コメントをありがとうございました．
  • ちゃんと復習したいと思います
    -- はい，よろしくお願いします．
  • 群論のようだと思っていたら実際に群論が始まって興味深く感じた
    -- 群が出てきただけなので，群論が始まったというのはちょっと大袈裟かもしれません．今後，もう少し群を掘ることになると思います．
  • モノイドの表のところがすぐには理解できなかったので今後復習を頑張ろうと思います。
    -- これは，自分なりに小さい例を作ってみるとよく理解できると思います．ぜひ試してみて下さい．
  • 逆元の説明が表のおかげでわかりやすかったです
    -- 群の理解の仕方には様々な方法があると思いますが，まず始めは表で理解するのが分かりやすいかと思い，そうしてみました．
  • 自己準同型モノイドと自己同型群の部分はちょっと複雑ですが、面白かったです。
    -- グラフに対して「すべての自己準同型写像」や「すべての自己同型写像」を考える必要があるため，複雑になるのは致し方ないですね．
  • 群の概念をサーチしてたくさんなものが出てきて興味深いと思いました
    -- ぜひ，勉強してみて下さい．
  • 単位元と恒等写像は同じそうと思いますし、意味の違う場合がありますか？
    自己同型写像 と 同型写像　は グラフの名前（GやH）以外の違いがありますか？
    For this part, I'm sorry to type in English, but no need to prepare an English translation of the answer!
    On page 13, is it correct that only 同型写像s can fulfill the 反対称性 property of 半順序? Are there other types of mapping that can fulfill that property too?
    While I am revising the definitions of 自己同型写像 and 同型写像, I am not sure if I understand the importance of these definitions because these mapping relations seem to be pointing back to the same graph. I suspect I might be missing a bigger picture of why 同型写像s are separately defined. Are there any sample use-cases where the concept of 同型写像 is indispensable?
    Please let me know too if you have explained this in a previous lecture and I've missed it. As usual, I will wait for the lecture recording to revise. Thank you for the great lecture!
    -- お言葉に甘えて日本語で回答します．複数の質問があるので，分けて回答します．
    (Q1) 単位元と恒等写像は同じそうと思いますし、意味の違う場合がありますか？
    (A1) 自己同型群ではない群に対しては，単位元が恒等写像であるわけではありません．そのためには，自己同型群以外の群を考える必要があります．授業では， $(\mathbb{R}, +)$ という群を紹介しました．この群では，考えている集合 $\mathbb{R}$ が写像の集合ではなく，恒等写像は $\mathbb{R}$ の要素ではありません．そのため，「恒等写像が単位元ではない」ということになります．実際，群 $(\mathbb{R}, +)$ の単位元は $0$ です．
    (Q2) 自己同型写像 と 同型写像　は グラフの名前（GやH）以外の違いがありますか？
    (A2) 違いはありません．つまり，同型写像 $f\colon G \to H$ において，$H=G$ であるとき，$f$ は $G$ の自己同型写像です．
    (Q3) On page 13, is it correct that only 同型写像s can fulfill the 反対称性 property of 半順序? Are there other types of mapping that can fulfill that property too?
    (A3) $G \simeq H$ かつ $H \simeq G$ であっても，$G = H$ であるとは限りません．その意味で，同型写像から反対称性は得られません．
    (Q4) While I am revising the definitions of 自己同型写像 and 同型写像, I am not sure if I understand the importance of these definitions because these mapping relations seem to be pointing back to the same graph. I suspect I might be missing a bigger picture of why 同型写像s are separately defined. Are there any sample use-cases where the concept of 同型写像 is indispensable?
    (A4) 同型写像 (同型) は第1回講義で，完全グラフや閉路を定義する際にも使われています．同型写像を使わずに，完全グラフや閉路を正確に定義するのは難しいので，ここで同型写像の使用は本質的だと思います．
  • 半順序や反対称性と聞いて、ソートの話が思い浮かびました。
    -- ソートができるのは順序のおかげですね :-)
  • 非準同型補題の証明が分かったような分からないようなフワフワした感じです
    -- 実をいうと，教科書ではこの証明に割かれている分量は7行程度です．(とても短いという意味です．) 授業では，それを補って説明しているので，ぜひ理解できるように復習して下さい．
  • 来週 よろしくお願いします
    -- はい．こちらこそよろしくお願いします．
  • 内容が多く感じて少し大変でしたが、きちんと復習すれば理解できると思うので頑張ります。
    -- はい，動画もありますので，ぜひ復習して下さい．
  • 新しく聞く用語が多かったので個人で今回の内容を振り返りながら学習を進めていくようになりそうと感じました。
    -- 新しい用語を覚える必要はないので，忘れたときに思い出せるように整理しておいて下さい．
  • 今まで講義で扱ってきたことが色々とつながりはじめ面白くなってきました。
    一層いままで扱ってきたことが重要だと感じたので復習をしっかりしたいと思います。
    -- 面白く感じていただけるようでしたら，何よりです．復習もしっかりと進めて下さい．
  • 院試で勉強した部分ともかぶっている箇所も多かったので，理解しやすかったです．モノイドあたりの理解が不十分なので，復習したいと思います．ありがとうございました．
    -- モノイドはこの授業で今後あまり出てくるわけではありません．その意味で，詳しく復習する必要はないかもしれません．しかし，重要な概念なので，「こういうものがあるのだな」という感覚は持っておいて下さい．
  • 代数との関連があって興味深かったです．
    -- このトピックは離散数学の様々な概念と深く関連するので，その点も味わって下さい．
  • ドイツのボードゲームといえば、ガイスターやカタンが思いつきます。岡本先生が好きなのは完全情報/ 不完全情報、確定/不確定の4つに分類したときにはどれですか?一度お手合わせ願いたいです。
    -- 私は深く読むことが苦手なので，完全情報ゲームは苦手ですし，あまり好きではありません．将棋や囲碁はまったくできないと思ってもらってよいです．おそらく私がはじめて遊んだドイツのボードゲームは『スコットランドヤード』だと思います (研究室にもあります)．分類するとすれば，スコットランドヤードは不完全情報確定ゲームということになるでしょうか．最近よくやっていたのは『コードネーム』です．ただ，これはチェコのボードゲームと呼ぶべきものなんかもしれません．
• 10/12 (2) 準同型の基本性質 (1)：部分構造
  • コメントをありがとうございました．残ってしまった「非準同型補題の証明」は次回の始めにやります．
  • 来週もよろしくお願いします
    -- はい，こちらこそよろしくお願いします．
  • グラフの基本的なことがわかり良かったです
    -- それはよかったです :-)
  • グラフは学部の一年以来なので懐かしいです
    -- この講義はグラフを扱うので，それを通して，ぜひグラフの扱いに慣れて下さい．
  • グラフについて初めて勉強していますが、頂点・辺と考える必要のあることが2つあるので、性質や定義なども複雑なように感じました。
    -- その通りだと思います．頂点だけを考えると，それはただの集合を考えているのと同じになります．そこに頂点どうしの関係を表す辺を考えることで，より複雑な構造が現れて，興味深い性質が出現します．
  • グラフに関する知識を思い出しながら理解することができました。
    -- この講義は割と定義が多いのですが，定義をいちいち覚える必要はありません．忘れた場合に，見直して思い出せれば，それで十分ですので，そのつもりで受講して下さい．
  • 定理がたくさん出てきて大変
    -- 今までに出てきた定理などを使うときには，それを復習するようにするので，定理も覚えなくてよいです．必要になったときに，調べて，思い出せるようにして下さい．
  • 最後の奇閉路間の準同型写像の証明についていけなかったので、あとで見直そうと思います。
    -- やっていることは単純なので，おそらく説明がうまくなかったのだと思います．自分で考えてみる方がよいのかもしれません．
  • ページ45からの証明はちょっとわかりませんから講義動画を復習します。
    -- 上の方と同じ部分ですね．定義をしっかりと見直しながら，復習してみて下さい．
  • 少し難しかったです。しっかり復習します。
    -- はい，動画もありますので，活かして下さい．
  • 大体は理解できたと思う
    -- それはよかったです．質問がありましたら，ぜひお願いします．
  • 各部分理解しやすかったです．単純に内容が多かったです．動画を見返します．
    -- 授業時間は90分もあるので，内容は多くなりがちです．しっかりと復習をして下さい．
  • リアルタイムで説明される証明を追うのは疲れますね
    -- 同意します．そのため，途中で休憩を入れています．ご活用ください．
  • 歩道と道の区別があいまいになっていました
    -- 歩道では頂点の繰り返しがあってもよいです．一方で，頂点の繰り返しのない歩道が道である，と思ってもよいです．
  • 具体例の説明で理解の確認ができて良かったです
    -- 具体例は重視しています．定義・定理・性質の説明をするときは，具体例を入れるようにしています．証明なども具体例を通して説明できるとよいのですが，うまく行く場合といかない場合があります．うまくいかない場合があるのは，私の能力不足または理解不足なのだと思います．
  • 「完全グラフと準同型」のところで、より一般に、グラフ $G=(V, E)$ に対して $|V| \leq n \Rightarrow G \to K_n$ だと思うのですが、これはあまり重要ではないのでしょうか。ここまで書いて、 $G \subseteq K_n$ が当たり前に成り立つのであまり面白くないかなと思いました。
    -- 「当たり前に成り立つのであまり面白くない」というのはその通りかもしれません．一方で，指摘して頂いた性質は重要なものだと思います．例えば，そこから，$\chi(G) \leq |V|$ であることが分かります．これは染色数の重要な性質です．
  • 非準同型補題で独立集合の大きさではなく、比が出てくるのが興味深いです。
    証明が理解できなかったので復習します。
    -- 少し補足します．無向グラフ $G$ の染色数 $\chi(G)$ に対して，$\chi(G) \cdot \alpha(G) \geq |V(G)|$ という不等式が必ず成り立ちます (これは，彩色における各彩色クラスが独立集合であることから言えます)．ここから，$\chi(G) \geq |V(G)|/\alpha(G) = 1/i(G)$ が得られます．仮に，$\chi(G) = 1/i(G)$ と $\chi(H) = 1/i(H)$ が成り立っているとすると，$i(G) \geq i(H)$ という不等式は，$\chi(G) \leq \chi(H)$ と同値になります．
    一方で，$G \to H$ ならば，$\chi(G) \leq \chi(H)$ が成り立ちます．なぜならば，$G \to H$ であり，$\chi(H) = k$ だとすると，$G \to H \to K_k$ となり，$\chi(G) \leq k$ が言えるからです．
    つまり，非準同型補題はここで挙げた「$G \to H$ ならば $\chi(G) \leq \chi(H)$」という性質と関係があることが分かります．つまり，$\chi(G) = 1/i(G)$ と $\chi(H) = 1/i(H)$ が成り立てば，「$G \to H$ ならば $i(G) \geq i(H)$」が成り立ちます．これは非準同型補題の見た目とかなり近いです．
    残念ながら，ここで仮定した $\chi(G) = 1/i(G)$ と $\chi(H) = 1/i(H)$ は多くのグラフで成り立ちません．しかしながら，そうであっても，$H$ が頂点可移であるならば，「$G \to H$ ならば $i(G) \geq i(H)$」は成り立つのです．
    ここで補足をしますが，$H$ が頂点可移であっても，$\chi(H) = 1/i(H)$ になるわけではありません．実際，非準同型補題の証明を行うときに，染色数はでてきません．これは次回の内容となります．
  • K2とK3の間に無数のグラフが存在していることが面白いと感じた。
    今後、証明などにもに要されることがありそうなので、しっかりと復習したいです。
    -- この性質はグラフの準同型を考えるうえでとても重要になります．後の授業では，例えば，「K3とK4の間にも無数のグラフがあるのか？」とか，「K4とK5の間にも無数のグラフがあるのか？」とか，そのような疑問にも答えていくことになります．
  • 頂点可移グラフの定義を見て，自分であれば「頂点対称グラフ」という名前を付けそうだなと思ったのですが，調べてみると「対称グラフ」は別の定義があることを知りました．また，次回の予告で群という単語を聞いて，なるほどとも思いました．
    -- 「対称である」という言い方をよくしますが，その正確な意味は，何をもって対称とするのか，に依存します．それを任意の2頂点の間のうつり合い方で定めたのが「頂点可移グラフ」になります．実を言うと「辺可移グラフ」(edge-transitive graph) というのもあります．これは任意の2辺の間のうつり合い方で対称性を定めたものになります．いわゆる「対称グラフ」(symmetric graph) は辺可移グラフに定義の上で似ていますが，辺可移グラフよりも強いうつり合い方を要求します．
    これらは，すなわち，「どのような自己同型写像が存在するのか」という問いに関係し，そこで「自己同型写像全体の集合」を考える動機が生まれます．そこでは群の考え方が有効になります．これについては次回の内容になります．
  • 岡本先生は何か趣味がありますか？私はいろいろありますが、映画やショッピング、ボドゲなどが好きです。
    -- 私もボードゲーム (主にドイツやヨーロッパのもの) は好きですが，最近はやる機会がなく，残念に思っています．なお，研究室にはボードゲームやカードゲームを多く揃えています．
• 10/5 (1) グラフの彩色と準同型
  • コメントをありがとうございました．以下のように掲載されます．
  • 授業後半の進みが速かったんです。
    -- すみません，時間配分がうまくいっていませんでした．速かったと感じる部分は動画で復習をして下さい．よろしくお願いします．
  • ありがとうございました。ついていけるか不安ですが頑張ります。
    -- 動画も残っていますので，それを活かして復習をして下さい．
  • 👍
    -- Unicodeを使って表示しているつもりですが，うまく表示できていなかったらすみません．
  • 生徒の質問や反応を促すためにcomment screenを用いて匿名でこれらを可能にしている手法はとてもありがたいと感じました。前向きな気持ちでコメントできるようになっていると思います。
    -- それはよかったです．CommentScreenをぜひ活かして下さい．
    別のことですが，皆さんは「生徒」ではありません．「学生」です．大学教員ですら，この違いを理解していない人がいるので，皆さんが間違えるのは仕方ないのかもしれませんが，この違いは大きなものです．まず学校教育法上，大学生や大学院生は「学生」です．ちなみに，短大生や高専生も「学生」です．中学生，高校生が「生徒」です．小学生は「児童」です．Wikipedia日本語版の在籍者 (学習者)の項目をご覧ください．
    また，デジタル大辞泉によると「生徒」は「学校などで教えを受ける者」で，「学生」は「学問をしている人」となっています．つまり，大学生は学問をしている，と見なされているのだと思います．皆さんもそのつもりで学修を行なって下さい．
  • 少し声が聞き取りずらかったです。
    -- ご指摘ありがとうございます．マイクの問題かもしれないので，次回は違うマイクを使ってみます．話すスピードの問題かもしれないので，スピードを調節します．なお，話すスピードが速いと思ったら，授業中に遮って「速い」と指摘して下さい．よろしくお願いします．
  • 初めて聞く概念もあったので、次回までに覚えられる様に復習します。
    -- 皆さんにお願いしたいのですが，覚えるための努力は一切しないで下さい．はっきり言いますが，それは無駄です．覚えるというのは，「自然と覚えてしまう」ものであって，努力して覚えても，それはすぐに忘れます．無駄な努力です．また，皆さんは今後いろいろな新しい概念にどんどん触れていきます．その度に覚えようとしては，時間が足りませんし，どうせ忘れるのですから，それも無駄な努力です．もっと有効に時間を使って下さい．
    いろいろな概念は「忘れたときに調べて思い出せる」ようにしておけば十分です．それをできるようにするためには，概念を自分で整理しておくことが重要だと思います．
    今一度いいますが，覚えようとしないで下さい．忘れたときに思い出せるようにして下さい．授業中に用語の定義などを忘れてしまったら，質問して下さい．何度忘れても，何度尋ねても構いません．
  • 中間発表が近くて胃が痛いです
    -- お大事に．
  • スライドを表示していたソフトは何ですか？
    -- Drawboard pdfのフリー版を使っています．
  • 毎年のテーマはどのように決定されているのでしょうか
    -- 基礎であるもの，あるいは将来的に基礎的になるものをテーマにしています．
  • スライドが分かりやすくいつも参考にしています
    今後ともよろしくお願いいたします。
    -- こちらこそよろしくお願いします．
  • グラフに対しての知見があまりないため、不安でしたが頑張って講義についていこうと感じました。できればもう少し例を挙げていただけると嬉しいです。
    -- できる限り例で理解できるようにしていくつもりです．よろしくお願いします．
  • よろしくお願いします。
    -- こちらこそよろしくお願いします．
  • 彩色の定義、準同型の定義とこれらの関係はよく分かりました。
    -- それはよかったです．自分でも例を作ってみて考えるとより理解が深まると思います．
  • 彩色ってどういった時に役立つのでしょうか？
    -- 競合がある状況を表現するためによく用いられます．例えば，wikipediaのgraph coloringに関するページを見ると，「応用」というものが書かれています．
  • 2類の学生です。初めてグラフについて学びましたが、先生のわかりやすいご説明で理解することができました。今後もよろしくお願いします。
    -- わからない部分がありましたら，遠慮なく質問して下さい．
  • 説明が詳しくて、いい授業です。
    -- 何かご要望がありましたら，ぜひお聞かせ下さい．
  • 準同型について理解できました。
    -- それはよかったです．:-)
  • 準同型写像とグラフの彩色の関係についてよく分かりました．
    -- 今日の目標が達成できた，ということですね．
  • グラフに関する知識の整理ができました.
    -- 今後も多くの概念が現れるので，その都度しっかりと理解していって下さい．
  • 定義から解説してくださりとても分かりやすかったです
    -- 定義を理解することが，すべての理解の出発点であるので，定義の理解は重要視しています．皆さんも，何かを説明するときに，ことばの定義を大事にして下さい．
  • 代数学の授業で扱った準同型や同型の具体例が出てきたので，興味深かったです．
    -- 代数系の準同型・同型とグラフの準同型・同型は違うものなので，それは気をつけて下さい．ただ，違うといっても，関連はあります．
  • 分かりやすかったです．
    2部グラフについては調べつつでした．
    -- 2部グラフの定義をすればよかったと，講義の後で反省しました．次回の講義では定義します．
  • 無向グラフ $G$ が2彩色可能であることと，$G$ が2部グラフであることは同値ということに気づきました．そういう意味で，$k$ 彩色可能であるグラフは2部グラフの拡張（$k$ 部グラフ？）と言えると思います．
    -- 実際「$k$ 部グラフ ($k$-partite graph)」という概念があり，それは $k$ 彩色可能であることと同値です．
    さて，今から私が困っていることを書きます．「ネットワーク科学」という分野があるのですが，そこでは「一部グラフ (unipartite graph)」という用語が使われています．しかし，これは「$k$ 部グラフ」の $k$ を1としたものとは違う概念です (おそらく数学的にまともな定義を持たない概念だと思います)．ネットワーク科学というのは割と新しい学問分野なのですが，そういう分野が歴史の長い学問分野の用語法を無視して，新しい用語法を勝手に開発して，平気な顔でいる，というのは学問上全くよくないと思っています．正直困っています．
  • グラフの彩色問題については以前調べたことがあったので、良い復習になりました。
    調べたときは、講義で染色数と言っていたものが彩色数と言われていたのですが、訳の問題ですか？それとも彩色数という言い方はしないんですか？
    -- 訳の問題である，と言い切ってもよいのだと思いますが，グラフ理論の専門家は「染色数」という訳語を用います (ちなみに私はグラフ理論について少し知っていますが，グラフ理論の専門家ではありません)．一方で，「彩色数」という訳語を用いている論文や書籍も多く存在するのですが，それらはグラフ理論の専門家が書いたものではないといってしまってよいと思います (かなりの暴言ではありますが)．
  • 無向グラフの完全グラフに向きを付けるとトーナメントになるという話は当たり前ですが、新たな気づきでした。
    -- 授業の中で紹介した通り，「トーナメント」という日本語の意味と「tournament」という英語の意味が異なることは，いろいろな場面で誤解を生みやすいので，皆さんも注意してください．
  • 二分定理に関して，H が二部グラフで G \to H である場合，多項式時間で G の H 彩色を具体的に示すことは可能なのでしょうか？
    -- 具体的に示すことは可能です．これについては，後の方の講義で扱う予定です．
  • グラフの準同型写像を、E(G)→E(H) のような辺から辺への写像としてうまく定義することはできますか？24ページの図を見るとそのほうが直観的かなという気持ちになりました。
    -- 考えたことがなかったので考えてみたのですが，結論としては「うまく定義できるかどうか分からない」です．
    例えば，次のようなグラフGとHを考えてみて，頂点は考えずに，辺だけを見て考えます．
    
    例えば，準同型写像を「Gで端点を共有している2辺は，写した先のHでも端点を共有している」という条件で定義すると，$g(1) = a, g(2) = b, g(3) = c$ で定義される写像 $g$ は準同型写像になってしまいますが，実際は $G \not\to H$ になっています (なぜそうなのかということは次回の授業の内容になります)．
  • 同型写像の間違った定義 (1) のところの説明が，$f$ がただの写像ではなく全射であった場合にどうなるのだろうかと思いました．先生の説明だと，$f$ が全射でないことを用いているのではないかと思いました．（この説明が，間違った定義 (1) が同型写像を与えることの反例になっていることは理解しています）
    -- 全射であるだけでも間違った定義になります．次のような例を考えて下さい．
    
    ここで，赤い矢印で示されているのが全射 $f$ を表していて，$\{u,v\} \in E(G)$ であることと $\{f(u), f(v)\} \in E(H)$ であることは同値です．しかし，$f$は全単射ではないので，同型写像ではありません．
  • レポートについて、どういったレポート課題が課されるのかが気になりました。
    難解なプログラミングが必要になったりするでしょうか？過去の例等があればうれしいです
    -- 「必要になる」ことはない予定です．過去の講義に関する情報はこのページの下の方から辿れます．
  • I am still improving my Japanese - is it acceptable if I submit the 2 reports in English instead?
    -- 英語で提出していただいて構いません．しかし，講義自体は日本語で行われますし，講義資料もレポート課題も日本語で作成されますので，その点はご了承ください．(English translation: The submission of English reports is no problem. However, please accept the policy that the lectures and materials are all based on Japanese.)

• 2回のレポート提出により成績評価を行います．
• レポート1 (50点満点)
  • レポート課題，提出要項
  • 要項説明：11月23日 (火)
  • 提出締切：12月8日 (水)
  • 提出自体はGoogle Classroomで行って下さい．
• レポート2 (50点満点)
  • レポート課題，提出要項 (2月22日修正)
  • 要項説明：1月18日 (火)
  • 提出締切：2月9日 (水)
  • 提出自体はGoogle Classroomで行って下さい．
  • すみません．問1が間違っていました．この問題については，全員に満点が与えられます．問題自体は，GとHが連結であるという仮定が抜けていました．上の「レポート課題」はそのように修正しています．

• こちらをご覧ください

• 10/5 (1) グラフの彩色と準同型
• 10/12 (2) 準同型の基本性質 (1)：部分構造
• 10/19 (3) 準同型の基本性質 (2)：準同型の合成
• 10/26 (4) グラフの円彩色
• 11/2 (5) グラフの分数彩色
• 11/9 (6) グラフの積と準同型
• 11/16 (7) グラフの商と引き込み
• 11/23 休み (調布祭片付け)
• 11/30 (8) グラフのコア
• 12/7 休み (国内出張)
• 12/14 (9) 準同型が導く半順序 (1)：構成
• 12/21 (10) 準同型が導く半順序 (2)：構造
• 12/28 休み (冬期休業)
• 1/4 (11) アルゴリズム (1)：例
• 1/11 (12) アルゴリズム (2)：整合性
• 1/18 (13) アルゴリズム (3)：双対性
• 1/25 (14) アルゴリズム (4)：多数決

• P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford University Press, 2004.
• C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001.
• G. Hahn and C. Tardif, Graph Homomorphisms: Structure and Symmetry, In: G. Hahn and G. Sabidussi (eds.) "Graph Symmetry", pp. 107-166, 1997.
• M. Bodirsky, Graph Homomorphisms and Universal Algebra Course Notes, TU Dresden, 2021. https://wwwpub.zih.tu-dresden.de/~bodirsky/Graph-Homomorphisms.pdf

• 離散最適化基礎論 (2020年度) テーマ：マッチング
• 離散最適化基礎論 (2019年度) テーマ：離散最適化における計算困難性
• 離散最適化基礎論 (2018年度) テーマ：理想グラフに対する組合せ最適化
• 離散最適化基礎論 (2017年度) テーマ：幾何的被覆問題
• 離散最適化基礎論 (2016年度) テーマ：グラフの木分解
• 離散最適化基礎論 (2015年度) テーマ：組合せ最適化におけるマトロイドの役割
• 離散最適化基礎論 (2014年度) テーマ：組合せ最適化における線形計画法の利用
• 離散最適化基礎論 (2013年度) テーマ：局所探索法の理論的側面
• 離散最適化基礎論 (2012年度) テーマ：ゲーム理論における離散構造とアルゴリズム