離散最適化基礎論

岡本 吉央

テーマ：エクスパンダ

注意：テーマは毎年変わります

実施形態

学生の皆さんの受講形態としては，「教室で授業を受ける」形を推奨しますが，自宅や研究室等からオンラインでリアルタイム受講しても構いませんし，オンデマンド型の受講をしても構いません．ただ，オンデマンド型では，質問をする機会が限られることにご注意ください．

内部シラバス (学務情報システムから見ることができるシラバス) で，Google Classroomのコードを確認し，参加をしてください．

• 10/20 (3) グラフの等周定数とエクスパンダ
  • スライド (10/21修正)
  • 講義動画
• 10/13 (2) グラフのスペクトル
  • スライド
  • 講義動画
• 10/6 (1) グラフ理論速習
  • スライド
  • 講義動画

• 10/20 (3) グラフの等周定数とエクスパンダ
  • 日本シリーズは横浜を応援することにします。贔屓はいつになったら日本シリーズに行ってくれるのか、、、2008年以来出てないです。
    --応援できるものがあるということは素晴らしいことだと思います．あきらめずに応援し続けてください．
  • 先日、キングオブコントの決勝が行われました。自分が応援していたコンビは惜しくも優勝とはなりませんでしたが、どの出場者も面白く、楽しい夜でした。先生の好きな芸人さん/芸能人などがいたら知りたいです。
    --いわゆる「お笑い」に明るいわけではないですが，
  • 今年のスーパーエルニーニョ（気象用語としては，南米太平洋岸沖合の平均海面水温が平年より2℃以上高いことをさします）は本当に凄まじいらしく，南米太平洋岸沖合の平均海面水温が平年より5℃近くも高くなることが予想されているらしいです．エルニーニョだと，日本は暖冬傾向になるそうですが，今年はどんな冬になるんだ…
    --3ヵ月予報によれば，今年の日本の冬は暖かいとのことです．私は寒いのが苦手なので，ありがたいことだとは思います．
  • 先週はインフルエンザで倒れていた。思いの外熱が上がったが、ワクチンのおかげか症状は軽めだった。
    --ご自愛ください．私も今週予防接種を受ける予定でいます．
  • 国際学会緊張します。
    --なにごともはじめてのことは緊張するものだと思います．なお，「大学院技術英語」という授業は国際学会の発表を想定しています．その内容を思い出して活かしてください．
  • 今からテストが怖いです
    --試験においては，何かを覚えているということが重要であるようにはならないので，その点は安心してください．
  • 3週後忘れてないようにしたい
    --私も忘れてしまいそうです．;-)
  • 二週間空いてしまうので内容を忘れない様にしたい。
    --毎回，はじめに必要な復習を行いますので，あまり心配しなくても大丈夫です．
  • 3週間後となると結構忘れそうなので復習しておきたいです
    --はい，ぜひ復習をしてください．
  • また後で証明を追いたいと思います。
    --式で書いて証明する方が (自分で確かめるには) 案外わかりやすいかもしれません．試してみてください．
  • Cheegerのところはちょっと復習しないといけないかも知れない。
    --分からないところがありましたら，ぜひ聞いてください．
  • だんだん難しくなっていってついていけるか不安
    --使っている数学は基礎的なものだけですから，基礎が大事だと思ってください．
  • 前回と比べて、新しいことが多くて定義も難しく感じた。復習していきたい。
    --定義などを覚える必要はないので，その点はご注意ください．
  • 個人的に今回の内容は難しかったので、丁寧な復習をしなければいけないと感じた。
    --スライドも動画もありますので，ぜひ活かして復習を進めてください．
  • 前回に比べて非常に難しい内容に感じた
    --難しく感じた理由は私の説明が悪かったからだと思います．線形代数の部分はもう少し式を使って説明していく方がよいようにも思いました．
  • 証明を再度読み直し、しっかり理解して次の授業に臨みたいと思います。
    --証明は文章として書いていない場合もあるので，自分で文章として書き下すことも復習として有効だと思います．ぜひ試してください．
  • 線型代数と初等的な数え上げを使うだけで（だけというには，真面目に計算を追うとそれなりに手間ですが）正則グラフに対するCheegerの不等式の下界側は証明できちゃうんですね．
    --そうですね．数え上げのところは慣れていないと難しいかもしれませんが．
  • エクスパンダの定義が非形式的(誤った使い方であればすみません)だったものから、厳密な定義にものになるかと思っていたのですが、あまりピンとこなかった……。
    私の理解が甘いのか、これから先も定義が続くのか……。
    --厳密な定義 (数学的な定義) は今回行ったものですべてです．別の言い方をすれば，これが厳密な定義です．そのように思って，改めて定義を見てみてください．
  • エクスパンダの定義についてまだあまり理解できていないので復習したい．
    --はい，ぜひ復習してください．
  • なんだかまだ伸ばしにくいからなんだとかいうのが何に役立つのかさっぱりわからない。
    --次回と次々回はエクスパンダの重要な性質（何に役立つのか）ということを扱います．お楽しみに．
  • 授業内容が面白そうだったので第3回から参加しました
    エクスパンダの定義がわかったので、この制約においてなにが利点になるのかをきちんと考えてみようと思いました
    --第1回の授業でどのような応用があるのかということをキーワードだけご紹介していますので，そのキーワードで調べてみてください．
  • エクスパンダってなんだか動物のパンダの一種みたいで名前がかわいいですよね。
    --カタカナにするときに「エクスパンダ」とするか「エクスパンダー」とするかということは，悩みどころで，今のところ定訳はないように思います．一方で，英語の発音としては「パンダー」のように延ばすわけではないので，「パンダ」の方が適切であるような気もします．
  • 勉強不足で申し訳ないですが、エクスパンダは初めて聞きました。伸ばしにくいという性質から、圏論のように関係性のみでグラフを記述する、なんてことも何らかの意義があるのかもしれないなと思いました。
    --エクスパンダを紹介するのがこの半年の目的であるわけですから，エクスパンダを初めて聞くことに問題はありませんし，むしろそれは私が想定していることです．ご心配なく．
  • 等周定数という言葉について授業中に調べたところ，同じ周の大きさなら例えば四角形や三角形，丸を比べてどれが一番大きいかという等周問題から来てることが分かった．どちらも点と線の話ではあるが直感的にはつながりを感じることが出来ずもやっとした．
    --等周問題というのはそのとおりのものですが，どちらも「かたちの境界」に着目していることが重要です．連続的なかたちの場合には境界の長さ (高次元になれば面積や体積) を測ることになります．離散的なかたちの場合には境界にあるものの総数を数えることになります．連続的な等周問題では「周の長さが同じかたちの中で面積がもっとも大きいものは何か」ということを考えるわけですが，等周定数の定義は「面積が同じかたちの中で周の長さがもっとも小さいものは何か」というものを考えているようなことになっています．平面における形においては，どちらも円が答えになります．実際の等周定数の定義では，面積が同じかたちだけを考えるわけではなく，かたちの面積を分母に持ってきて，かたちの選択を柔軟に行えるようにしています．この意味で，等周問題と等周定数は関係があります．
  • •　閉路や完全グラフにおける等周定数の性質を発見するのはすごいと思った。
    •　最後の証明の式変形を理解するのが難しかった。
    --閉路や完全グラフは構造が単純であるため，その等周定数を具体的に与える (公式を与える) ことは授業で扱えるぐらい簡単なことであると言えます．一方で，より一般的に，与えられたグラフの等周定数を計算することは，計算複雑性理論的に難しい問題であることが知られています．その意味では，等周定数というものはあまり扱いやすいものではないとも言えます．
  • ボトルネックについて、グラフのどの部分に着目して判断すればよいのかが難しかった。
    --定義は直感的なのですが，実際にどこにボトルネックとなるところがあるかを判断するのは，上のコメントの回答で述べたとおり，計算複雑性理論的に難しい問題であることが知られています．そのため，判断が難しいという感想を持つのも無理はないと思います．
  • 等周定数を直接計算するのは大変そうですが、固有値計算に置き換えられるのが便利だと感じました。
    --固有値の計算を厳密に行うことは難しいです．計算には数値計算と記号計算（数式処理）があり得ますが，数式処理においては，次数の高い多項式の根を求めることになるため，これは難しいです．(たとえば，5次方程式の解の公式は知られていません．) 一方で，数値計算では厳密に求めることができません．ただ，近似的でよいならば，数値計算で十分ではあります．エクスパンダの性質を数学的に考察するときには，等周定数を考えるほうが都合のよい場合と固有値を考えると都合のよい場合が分かれていて，うまく使い分けています．
  • 等周定数ってなんだと思っていたのですが，edge expansion (あるいはCheeger constant) のことだったんですね．個人的に，グラフの頂点一つから出る辺の本数（頂点の次数）のように，頂点部分集合から出る辺の本数と関連がある概念としてedge expansionは聞いたことがあったのですが，ボトルネックを測るという幾何的な話題からつながることは知らなかったです．
    --解釈にはいろいろなものがあると思います．自分なりの解釈を編み出すと，そこから他の概念とのつながりが気になり，新しい発見があるかもしれませんね．
  • グラフのボトルネックを数式で示すための考え方が興味深かったです
    --直感的な考えをどのように数学を使って表現するか，ということは，数学を使うという立場においてはとても重要なことになります．その例を今回は扱ったとも考えることができます．
  • 辺の数が小さく、かつ強い連結だと嬉しいエクスパンダという理解でよいのですかね？雰囲気でしかまだ理解できていないのを感じる。
    --雰囲気はそれでよいと思います．雰囲気の理解と数学としての理解を並行して考えられるとよいと思います．
  • dを3以上の定数にしたとき，頂点数をどんどん増やしてもエクスパンダとしての性質を保てるという点が興味深いと思いました．実際にどのような方法でグラフにすれば，この性質を維持できるのか疑問に思いました．
    --エクスパンダの構成法はこの半年の授業の後半の内容になります．すみませんが，そこまでお待ちください．
  • 授業の進みが速いので、後から見返せる映像があることがとてもありがたいです。
    --はい，ぜひ動画も活用して復習してください．
  • ブロック行列の扱いを完全に忘れていた
    エクスパンダの定義があまり理解できていないので次回以降深めたい
    --ブロック行列はとてもよく使います．ぜひ慣れてください．
  • Rayleigh商を初めて知ったが面白いと思った。
    --Rayleigh商は固有値と固有ベクトルを扱うときによく使う道具です．とても有用です．
  • Courant-Fischerの定理を用いて固有値を評価する部分や、頂点集合を分割して行列の計算を進める部分が複雑で、理解するのが難しかった
    --計算の部分は自分なりにやってみると，わりとすんなりと分かるかもしれません．
  • 第3回のpg 53/58
    「d − λ が大きい」というのがありますが、これはd − λが取り得る値の範囲において比較的大きいという意味ですか。
    λがむしろ負であることが望ましいので、今後はλ_2が負であることを証明する流れになるですかね
    --「$d-\lambda$ が大きい」というのは直感あるいは雰囲気に寄った言い方なので，あまり正確な意味は考えていないと思ってください．そうであっても，この部分は正確な意味を与えることもできます．それは以下のとおりです．まず，$n,d$ は固定します．このとき，「$d-\lambda$ が大きい」というのは文字通りその値が大きいということを意味します．固定した$n,d$に対して，$d-\lambda$ が大きくなるような $(n,d,\lambda)$-エクスパンダがうれしいという意味になります．
    なお，何回か後にAlon-Boppanaの定理を扱いますが，それによると，$n\to \infty$において，$d$-正則エクスパンダ族の第2最大固有値 (の列) は負の値に収束しないことが言えます．本当は第2最大固有値が負になるとうれしいわけですが，それは望めないということになります．これについては後の方の講義で扱います．
  • レイリー商を利用して等周定数の下界を考えるという考えが面白かったです．ただ，まだ突拍子感があって，レイリー商を使う動機みたいなのを感じ取れません...
    2つ質問があります．
    1. Cheegerの不等式における下界の証明の冒頭でh(G) = |\partial S|/|S|となるSを考えるといっていましたが，そのようなSを必ずとってくることはできるのですか？
    2. こちらもCheegerの不等式の証明なのですが，レイリー商の二次形式の計算で，A_Gの要素が要素が1のものが...みたいに話していた(つまりA_Gの要素が0か1だけの様な印象を受けた)のですが，2とか3の場合はないのでしょうか．つまり，今回考えているグラフは多重辺グラフであるため隣接行列の要素が1より大きい場合もあると思うのですが，その場合は考えないのでしょうか？
    --まず質問に回答します．(1) そのようなSは必ずとれます．それは，等周定数の定義において考えるべきSが有限個しかないからです．なお，Gの頂点数が2以上であることは暗に仮定しています．(2) これは私の口が滑りました．隣接行列の要素に1より大きい整数が入ってくることはあります．そのとき，MやNは対応する部分行列の成分和を表すことになります．そうすれば，証明そのものは同じように進めることができます．
    次に「レイリー商を使う動機」の回答をします．レイリー商は固有値に対する不等式を導くときにとても役立ちます．例えば，適当な単位ベクトル $x$ を持ってきて，$x^T A x$ を考えると，最大固有値 $\lambda_1$ に対して，$\lambda_1 \geq x^T A x$ の成立が言えます．これは最大固有値の定義だけ ($Ax = \lambda x$ を満たす最大の $\lambda$) から導出するのは難しいと思います．
  • 行列の固有ベクトルに関して、行列を線形変換と捉えたときに元のベクトルと同一直線上に写されるベクトルが固有ベクトルであるといったイメージを持っています。しかし、グラフの隣接行列とその固有ベクトルに関して、そのようなイメージで考えることは難しそうです。行列の固有ベクトル、固有値について、一般的な(線形変換の文脈やグラフの文脈によらない)イメージを持つとしたらどのように考えるのがよいのでしょうか。
    --グラフの隣接行列とその固有ベクトルをそのようなイメージでとらえる方法があります．そのためには，実をいうと，隣接行列ではなく，ラプラス行列 (ラプラシアンとも呼ばれる) を考える方がよいです．$d$-正則グラフ $G$ のラプラス行列 $L(G)$ は $dI-A(G)$ で定義されます ($I$ は単位行列)．このとき，$A(G)$ の固有値が $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ であることと $L(G)$ の固有値が $d-\lambda_n \geq \cdots \geq d-\lambda_2 \geq d-\lambda_1$ であることが同値になり，$\lambda_i$ に対する $A(G)$ の固有ベクトルは $d - \lambda_i$ に対する $L(G)$ の固有ベクトルであり，逆も成り立ちます ($Ax = \lambda x$ であることと，$Lx = (dI - A)x = dx - \lambda x = (d-\lambda)x$ となることが同値なので)．ラプラス行列はグラフの上で拡散方程式を書くとその係数行列として現れます (拡散方程式を離散化して，グラフの上で考えると思ってください)．このとき，$L(G)$ の固有値や固有ベクトルがいわゆるモードに対応することになります．
  • 今回の講義で，グラフの新たな見方ができるようになって面白かったです．
    話は変わりますが，最近息抜きの仕方に悩んでいます．先生のおすすめの息抜き方法とかってありますか？
    --おすすめを提案するほどいろいろな息抜きを試したわけではないので，おすすめではなく，私が試したことがあるものという意味で答えます．ぼーっと動画を見るとか，テレビを見るとか，音楽を聞くとか，散歩するとか，とにかくぼーっとすることです．あまり考えないことが大事かなと思います．
  • 何か悩んだときは、ひとまずやってみるのが良いのか、一旦立ち止まるほうが良いのか、どちらの方が良いでしょうか？
    --場合によると思いますが，他の人に迷惑がかからないなら，ひとまずやってみるとよい気がします．
  • 世の中の研究者たちの功績を見てると、自分の研究に自信がなくなってきます…
    --上には上がいます．気にしないことだと思います．
  • 他の方へのコメント返信を見て、AIとしてGeminiとChatGPTを使っているとのことですが、AIによって回答の精度だけでなく、文章の組み立て方のクセなどが違って面白いですよね。AIを比較して指示の出し方などを変えると楽しいです。
    --同じAIでも日によって違う答えを言ったりするので，それがよい場合もありますし，悪い場合もあって，困ることもあります．まあ，人間も一貫性があるわけではないので，そういうものだと思っています．
• 10/13 (2) グラフのスペクトル
  • 前回は提出し損じていました、半年間よろしくお願いいたします
    --よろしくお願いします．フォームは13:00に閉じますので，ご注意ください．
  • 就活が憂鬱です
    --憂鬱である気持ちは分からないでもないです．もうそろそろ就職活動に関するガイダンスがあるか，既にあったと思います．電通大では就職活動に関するサポートがいろいろとありますので，ぜひ活用してください．
  • dataが複数形なの初めて知りました
    --授業でも述べたとおり，もともとはdatumが単数形，dataが複数形です．ただ，dataという単語には不可算の用法もあり，その場合は「this data」のようにいうこともできるようです．技術的な文書では，dataを複数として扱う方が無難であるように思います．
    情報系に関係のあるところでは「software」や「information」も (基本的に) 不可算なので，例えば「softwares」や「informations」のようにいうことは (例外を除いて) できないことになります．ご注意ください．
  • "datum"と"data"の話は初耳でした．「"aquarium"と"aquaria"」や「"maximum"と"maxima"」もこの仲間だそうです．授業中に，身の回りの知見を広げられる時間が好きなので，今後もあると嬉しいです．（もちろん授業の本編も知見を広げられる時間ですが）
    授業webページのタイトルが「2025年度後学期」になったままです．
    --「2025年度」のご指摘ありがとうございます．修正しました．
    複数形の例外 (s以外のものをつけたり，そもそも何もつけない場合) は語源にも関わり興味深いように思います．数学に関わりが深いところだと「formula」(公式) の複数形として「formulae」を使うことがあります (最近は「formulas」も複数形として許容されているように思います)．「formula」も元はラテン語のようです．ギリシャ語由来のものとして，例えば多面体を表す「polyhedron」があり，その複数形は「polyhedra」です．
  • 今年は6月くらいが1番熱く感じた．急に寒くなると朝がつらい．
    --急に寒くなると，体調を壊しやすいので，気を付けてください．
  • 授業でGeminiを使って考えたという話がありましたが、先生はGeminiをよく使うのですか。色々なAIツールがありますが、それを使う決め手のようなものはあるのでしょうか。
    --Geminiをよく使います．電通大のUECクラウドアカウントでProまで使えるので，それを使っていますが，いまのところflashの使い心地が一番よいです．それとは別に，Codexを使ってみたくなったので，最近課金してChatGPTを使い始めました．ただ，まだ使いこなせていません．
  • 冒頭で前回のクイズの解説があると嬉しいです
    --特にクイズの解説は予定していません．そのうち，採点結果をClassroomでお知らせするようにするので，そこで提出した解答が正しかったかどうかぐらいは分かることになるようにします．
  • 先週末に昭和記念公園に遊びに行きました。園内でもらえるマップにて、代表的な地点間の移動にかかる時間の目安がグラフで表されているのでありがたかったです。でも、あまりにも広いので園内で自転車をレンタルするほうがおすすめです。日本庭園がきれいです。
    https://www.showakinen-koen.jp/pamphlets/
    --昭和記念公園の横 (IKEAの辺り) は稀に歩くのですが，中には入ったことがないです．今度入ってみます．:-)
  • 集合やグラフについて結構忘れてしまっていて，早くもすんなりと分からないところが出てきてしまったのでしっかり復習しようと思います．
    --集合の記法にはぜひ慣れてください．目がちかちかするかもしれませんが，こういう数式とか記号というか，そういうものは見ているうちに慣れていくものだという気もします．この授業が慣れるための機会になれればうれしいです．
  • 性質として綺麗で面白いですね．
    --よくないことを言うかもしれませんが，数学というのは綺麗な性質を追い求めているような気がします．皆さんは「整備された」数学しか見ていないので，数学というのはそもそも綺麗であるように感じるかもしれませんが，もともと世界はとらえどころがなく，混沌としているものだと思います．それを整理して，綺麗にしていくのが学問としての体系化（つまり研究）だと思っています．
  • 線形代数を久々に使いましたが復習が必要そうです…
    --線形代数はいろいろな場面でよく使います．ぜひ復習してください．
  • 固有値の範囲なんて考えたことなかった．
    --固有値の範囲を考えることはよくあります．今回の授業で扱っている固有値は必ず実数なので，数直線上に配置して考えていますが，一般に固有値は複素数なので，複素平面の上で考えます．(なお，「複素数平面」ではなく「複素平面」という用語がふつうの数学用語です．高校の教科書であえてふつうではない数学用語を使うのはやめてほしいと思っています．) 複素平面の上で固有値の範囲を考えるためによく使う定理にGershgorinの定理 (ゲルシュゴリンの定理) があります．
  • 正則グラフの固有値のところでペロン・フロベニウスの定理を連想した．
    --連想できますね．ペロン・フロベニウスの定理は，グラフの文脈でもよく使います．この授業では正則グラフだけを扱いましたが，そうではないグラフにおいてはペロン・フロベニウスの定理が活躍します．
  • 固有値への感覚的理解が足りないから、固有値周りの性質が理解しにくいんだろうなと思った。空間がつぶれるイメージってやはりしにくい。
    --私は「空間がつぶれるイメージ」というのを固有値に持っていないので，すみませんが，よくわかりません．ひとそれぞれいろいろなイメージの仕方があり，自分なりの理解ができることは大事だと思いました．
  • 固有値や基底の話が懐かしかったです
    --「実対称行列の固有ベクトルで正規直交基底を作る」という性質を次回は使います．お楽しみに．
  • 固有値がグラフにおいていくつか性質を示すことが分かった。知っている知識の復習から新たな定義や性質を理解する流れが分かりやすく感じた。
    --グラフのスペクトルがグラフ自体の情報をどれくらい持っているのか，ということは興味深い研究対象です．今回の授業では少しだけ性質を紹介しましたが，もっとたくさんのことが長い研究の歴史の中で知られてきています．
  • さまざまな行列の固有値の求め方がとても面白いと感じた。
    --特定の性質を持った行列の固有値を求めることは，わりと技巧的なことがありますが，それはそれで面白いことのように思います．固有値λと固有ベクトルxを知っていれば，ただ単にAx=λxが成り立つことを確認すればよいのですが，それが分からないときに試行錯誤するのは，パズルのようで楽しいときもあります．
  • 各グラフの隣接行列の固有値に求めるための公式があるのは面白いと思いました。だが、証明に関してはまだ理解しきれていないので、自習でゆっくりやってみようと思います。
    エクスパンダと固有値の関係を次回やるとのことで、とっても楽しみです。
    --はい，ぜひゆっくりと考えてみてください．
  • 固有値の計算ミスをしないようにしたい
    --手で計算するのはわりと大変です．コンピュータにやってもらってください．
  • 実対称行列の固有値の証明に感動したのですが、u^{T}Avを使うところに自力で辿り着けるかと言われたら辿り着けないなと思いました。
    また、線形代数を久しぶりに扱ったため想像より忘れているところも多く、固有値と固有ベクトルで若干苦戦しました。次回までによく復習しておこうと思います。授業自体はとてもわかりやすかったです。
    -- u^{T}Avは双一次形式や双線形形式 (bilinear form) と呼ばれるもので，線形代数ではよくでてきます．慣れると線形代数を道具として使える幅が広がると思います．
  • グラフに苦手意識があるが、まだ線形代数の復習的な内容が多いので授業内容を追うことができた
    --苦手意識はしかたのないものかもしれませんが，そうであってもそれに慣れられるとよいと思います．視野が広がりますから．
  • 意外と固有値の計算、性質で忘れているところがあったので良く復習したい
    --はい，ぜひ復習してください．大学生のときの教科書を見てみると，こんなことも書いてあったのか，と新たな発見もあると思います．
  • pg35/58 で脱落しました
    pg22/58 「x が λ に対する A の実固有ベクトル」と「 y が µ に対する A の実固有ベクトル」はCurly bracketsでまとめた方がいいと思いました。矢印が二行の真ん中じゃなくて一行目に来ていますので。
    完全グラフの隣接行列みたいな単純なグラフでも、巡回行列である事実を利用してそれの性質を導出しているの感動しました。
    --ご提案ありがとうございます．このような場合私はたいてい波かっこをつけるのですが，ここではレイアウトの関係ではずしてみました．つけたほうがよかったかもしれません．なお，左側の3行が波かっこをつける対象なので，矢印の位置は正しいです．紛らわしくてすみません．
    隣接行列が巡回行列であるようなグラフは対称性が高いグラフであると見ることもできます．そのようなグラフはcirculant graphと呼ばれ，これ自体もよく研究されています．
  • •　ξのkj乗のkが非ゼロのときのj=0からj=n-1までの和がnが2以上の場合で0になるのがすごいと思った。
    •　二部グラフの定義のとこで辺{u, v}と頂点集合{u, v}の表記が同じなのがややこしいと思った。
    --辺は頂点の(多重)部分集合であると定義されているので，「辺{u, v}」と書くとき，それは集合を意味していることになります．その意味では一貫しているのですが，ややこしいことには変わりないかもしれません．
    授業ではごまかしたので，ここで，$k=1, 2, \dots, n-1$ のとき，$\xi^{kj}$ の和 $\sum_{j=0}^{n-1}\xi^{kj}$ が$0$ になることを証明します．ただし，$\xi = \exp(2 \pi \mathrm{i}/n)$ です．
    $k$ は $1,2,\dots,n-1$ のいずれかであるとして，それを固定します．$\xi$の定義から，$\xi^{n} = 1$であるので，$\xi^{kn} = 1$ であることが分かります．つまり，$\xi^k$ は方程式 $z^n -1 = 0$ の解の1つです．この方程式の左辺を因数分解すると $(z-1)(z^{n-1}+z^{n-2}+\dots + 1)$ となります．$\xi^k \neq 1$ なので，$\xi^k$ は $\xi^{k(n-1)}+\xi^{k(n-2)}+\dots + 1 = 0$ という等式を満たすことが分かります．これは $\sum_{j=0}^{n-1} \xi^{kj} = 0$ に他なりません．
  • 離散数学で隣接行列を扱った際には、紹介どまりだったので、実際に使用していると授業がつながった感じがして良いと思った。
    -- それはよかったです．授業などで定義だけを紹介すると，それがなぜ重要であるのか，とか，なぜ考えなくてはならないのか，といったところまで踏み込めずに，むずむずとした気持ちになったりします．今回はまだグラフのスペクトルを定義しただけですが，この後の授業で，それを使っていきます．
  • 単純無向グラフに限ってしまうと意味が薄れる？
    --そういうわけではないです．今回の内容は単純無向グラフに対しても成り立ちます．一方で，多重無向グラフとして扱う方が自然だと思うので，この授業ではそのようにしています．
  • エクスパンダって，必殺技ぽくて叫びたくなります．「エクスパンダーーーー！！」ってだれか叫んでくれないかな？
    ところで，離散数理工学のコメント返しを見ていたら，先生のコメント返しは業界視聴率が高いという文言を目にしました．かく言う私も業界視聴者の一人であるのですが，どんな人が見ているのでしょうか？
    またまたところで，今回の話はかなり行列が対称であることが強く効いている印象を受けました．一方で，有向グラフの話になると，隣接行列が対称行列であることが保証されなくなるので，今回の結果をそのまま流用するということが難しそうだと感じました．
    --私の周辺の研究者が見ています．全員ではないですが，「見ている」と直接言われることはよくあります．
    有向グラフになると，話がややこしくなります．有向グラフの隣接行列も定義できますが，対称行列ではないので，固有値が実数であるという性質が保証されなくなります．そのため，固有値の代わりに特異値を用いるという手法があります．特異値は必ず実数であるという保証があるので，都合がよいのです．
  • グラフの定義や隣接行列は以前にも学んだ内容だったが、多重辺や自己閉路まで含めて改めて整理でき、よい振り返りになった。自分の研究でもグラフ理論の考え方を使っているので、定義を正確に押さえ直した上で論文等を読んでみたい。
    --「定義を正確に押さえる」というのは大事ですね．ぜひ励行してください．
  • 今回の授業では、グラフの構造を隣接行列の固有値から考える点が面白いと感じました。特に、つながっていない二つのグラフのスペクトルが、それぞれの固有値を合わせて求められることが分かり、グラフと線形代数のつながりを感じました。また、固有値の間隔からグラフの広がりやすさまで分かることも印象に残りました。
    --私も感じます．その視点が次回につながっていきます．
  • ちょっとついていくのに出遅れたので、よく復習する。エクスパンダはまだ雰囲気でしか理解できていないのが気がかり
    --エクスパンダの定義は次回扱いますので，いまは雰囲気だけで問題ありません．
  • 全体を通して証明がわかりやすいので掴みやすかったです。
    また、エクスパンダにおいて最大固有値と2番目に大きい固有値との差が大事というのは不思議に感じたので次回が楽しみです。
    --次回を楽しみにしていてください．:-)
  • 固有値がこのように応用されると知ってとても興味深かった．院試ではひたすら固有値を求めていたが，実際にエクスパンダの定義に関わると知り，これ以降の講義も楽しみです．
    --試験を受けるために固有値を勉強しているわけではないですからね．実際に研究や仕事の中で使っていけることが重要だと思います．
  • 隣接行列の固有値を見ると、グラスの性質がわかる、という話でした。固有ベクトルにはどのような意味があるのか知りたいです。
    --意味にはならないかもしれませんが，固有ベクトルを用いてグラフを描く手法が知られています．よくspectral embeddingと呼ばれています．そのように描いた空間でクラスタリングを行う手法をspectral clusteringと呼んだりします．どちらもよく使われる手法です．
  • 最大固有値と２番目に大きい固有値の間の距離がエクスパンダがどう関係していくのか気になりました。ず
    --私も気になります．次回をお楽しみに．
  • 感想
    院試対策では線形代数の固有値や固有ベクトルについて学習したが、それらをグラフの構造の解析に利用するという視点は持っていなかった。
    言われるがままといていた固有値だった出てきた値によってグラフの性質を見極められるから、最適化問題で固有値が絡む理由のイメージが固まった感じがする。
    ただし次回定義するというエクスバンダが今回の授業で繋がっていくイメージはまだ湧いていない。前回で復習が終わりテンポよく今回は進んで行ってるので、分からない部分の量に対して進むスピードが速い授業だと感じた。そのため置いていかれないようにしたい。
    --動画もありますので，わからないところは復習をしてください．質問もお待ちしています．
  • 閉路のスペクトルの値や重複度が図形と関連しているのが面白いと感じた。
    --そうですね．巡回行列の固有値は複素平面上で表した方がイメージが湧きやすかったかもしれません．皆さんもいろいろな理解の仕方を試してみてください．
  • グラフの隣接行列の固有値からグラフの性質を調べられることを学んだ．ただ，固有値やスペクトルがエクスパンダの性質と関係があるのか不思議に思った
    --これは確かに不思議です．次回，証明も少ししますが，そこで「伸ばしやすさ」がどう固有値と関係するのか分かってくるかもしれません．
• 10/6 (1) グラフ理論速習
  • コメントをありがとうございました．以下のように掲載されます．
  • 半年間よろしくお願いします
    --こちらこそよろしくお願いします．
  • 半年間よろしくお願いします
    --こちらこそよろしくお願いします．
  • 半年間よろしくお願いします
    --はい，よろしくお願いします．
  • よろしくお願いします!
    --こちらこそ，よろしくお願いします．
  • 今回の内容について、質問はありません。これから半年間、よろしくお願いします。
    --はい，よろしくお願いします．ただ「質問なし」だけだと，次回からはコメント提出に対して点を与えられないかもしれません．何もない場合は雑談でもしてください．よろしくお願いします．
  • ありがたいことに，西地区にもキッチンカーが来るようになりましたね．昨日は13時直前になっても多少並ばないといけないぐらい賑わっていて，西地区ってこんなに人がいたんだって思いました．
    --はい，人はいますよ ;-)
  • 来週(10/13)、先行履修申請用紙の署名をいただくことは可能でしょうか？
    --はい，書類を忘れずにお持ちください．
  • 事情で授業に参加できなかった場合は、正当な理由であれば欠席届の提出をしたほうが良いですか？
    --欠席届を提出する必要はありません．提出していただいたとしても，例えば，クイズ＋コメントの1点が自動的に与えられるということはありません．
  • 以前，学習したことがある範囲だったが，不安だったので復習になってよかった．
    --はい，一部の方にとって今回は復習のような内容だったと思いますが，グラフに関する知識は前提としていないので，それを紹介しました．
  • 成績の評価方法が例年と変わってて驚きました
    --理由はいくつかありますが，ひとつは生成AIの高性能化のためです．そのため，レポートで成績評価を行うことが難しくなってきたと感じていますし，実際そうだと思います．今回は期末試験を主に成績評価を行うことになります．よろしくお願いします．
  • 概ね復習をさせていただいた。多重のものについても自然な気がする。それにしても、いつになっても歩道やら道やらはややこしい。
    --はい，確かにややこしいと思いますし，私も混乱します．覚えるようなものではないと思ってください．
  • グラフにおいて、経路にも種類があり、しっかり定義されていたのが印象的でした。グラフについて復習しつつ受講したいと思います。
    --経路（歩道，小道，道）の区別はややこしいので，忘れたときに調べて思い出せるというぐらいの気持ちで，気楽にとらえてください．
  • 歩道、小道、道を混同してしまうのを思い出した。
    --覚えるものではないと思うので，忘れたり混乱したときに，調べて思い出せるようにしてください．
  • わかりやすい講義、ありがとうございます。
    疑問:
    頂点間の距離の定義で、dist_{G}(c, c,) = 0 となっていました。つまり、ある頂点から自分自身への距離は 0 と考えるわけです。グラフが何を表現しているか、にもよるのですが、何かが、必ず自分自身と繋がっている、と決めてかかることはできないように感じます。自分自身を繋ぐ辺の存在を許すことの意味とも関係してくるような気がします。別の定義もあってよいのでは?
    感想:
    グラフの直径を円との類推で議論していたのを面白く感じました。同様な類推で、半径、中心といった概念も作れるのでは。ここからグラフの興味深い性質が導けると面白いのだけれど。
    雑談:
    歩道、小道、道というネーミングが ? と感じました。概念的には
    　　道　⊂ 小道　⊂ 歩道
    のようなのだけれど、私が直感的に思っているイメージと全く整合性が無いです。
    --それぞれお答えします．[疑問への回答] そのとおりだと思います．ただ，ここで「距離」と呼んでいるものは数学における「距離空間」を意識して定義していると思ってください．グラフG=(V,E)が連結であるとき，授業で定義した距離dist_Gを使うと，組(V, dist_G)は距離空間になります．そのためには，dist_G(c,c)=0となっている必要があるのです．一方で，距離空間であるという性質や意識を考えなくてもよい場合は，ご提案どおりの考え方もありうると思います．[感想への回答] グラフにおいて半径や中心といった概念を定義することができ，実際に調べられています．例えば，木と呼ばれるグラフがありますが，木の中心は木に対する分割統治アルゴリズムを設計する際に重要な役割を果たします． [雑談への回答] 歩道，小道，道という用語自体はわりと適当に作られていると考えるのがよいと思います．言葉自体から包含関係や含意を想起するのは難しいように感じます．
  • グラフの用語についてのよい復習になりました。今後の講義もよろしくお願いします。
    --一部の人にとっては，今回の内容は復習だったと思います．次回から新しい内容が増えてくると思いますので，楽しみにしていてください．
  • グラフの基礎を扱ったが、以前の授業で習ったことを再確認できたのでとてもよかった。
    またエクスパンダーの定義があいまいなので、今後どのように厳密に扱うのか気になった
    --エクスパンダの定義は第3回で行う予定です．気になりますが，少々お待ちください．
  • 具体と抽象のバランスがちょうどいいと感じた。
    --例を重視しています．定義や性質に書かれている条件だけを読んで，理解できるということはあまりないと思っています．例を通して定義や性質が理解できるものだと思っています．皆さんもぜひ励行してください．
  • 定義について、非形式的な説明があったお陰で、感覚的に理解しやすかったです。
    また、休憩時間があるのが個人的にありがたかったです。
    --「形式」と「非形式・直感」の両方を大事にしているつもりです．数学というものが形式に寄りすぎるために，分かりにくくなったり，使いにくくなっているという側面があるように感じています．この授業では形式的な理解と直感的な理解の両方を大事にしていきたいと思っています．
  • 自分には批判的思考が足りていないと常々思います
    --それが足りていないと知るところからまず始まると思います．この授業も含めて，いろいろなところで批判的思考を鍛えていってください．
  • 毎年違うトピックを扱っていることにとても驚いた。研究に関係すると思うので、講義を頑張って理解したい
    --皆さんの研究に生かされることは私の願いなので，ぜひ生かしてください．
  • 来年からセキュリティに携わるので、攻撃グラフ、依存関係の脆弱性伝搬といったものとものの関係を理解するのに応用したいと思っています。
    --はい，ぜひ応用できるように勉強してください．
  • 自分が使うことになる配置最適化問題でもグラフ化するプロセスを参考とする論文でたくさんみた。
    数理最適化のイメージが変数、制約、目的だったところからグラフの問題でもありそれを扱う授業の必要性を前より強く感じるようになった。
    gptにその関連で質問をしたところ
    「グラフ構造が分かると、一般的な整数計画として力ずくで解かなくても専用アルゴリズムで高速に解ける場合がある」
    という回答から
    グラフ理論を学ぶ目的が
    最適化問題を見たときに「あ、これは最短路型だ」「これはマッチング型だ」「これはフロー型だ」と構造を見抜いて、適切な解法を使えるようにする
    というイメージを今更ながら持った。
    --「構造を見抜いて，適切な解法を使えるようにする」というのはとても大事なことだと思います．この授業でその視点が強調されることはあまりないかもしれませんが，その視点で授業の内容を理解しようとすると，新しいことができるようになるかもしれないので，ぜひ試してみてください．
  • グラフ理論という言葉を聞いたことがあったが思いのほか難しそうだった．正直なところ用語が多すぎて覚えられず次回出てきたときに思い出せるかどうかわからない．もし可能であれば次その用語が出てきたときに軽く触れて頂きたい．また私の研究室では不定期にゼミが行われていて，この時間に行われていることもある．もしオンデマンド形式で受講する場合クイズとコメントに答えることはできないのだろうか．期限を13:00までではなく本日中にしていただけないだろうか．
    --コメントの内容が大きく分けて2つありますので，それぞれに回答します．(1) 用語は覚える必要がないものだと思ってください．忘れたときに，調べて思い出せればよいものだと思ってください．ただ，思い出せるように整理しておくことは重要だと思います．その一方で，ご要望どおり，用語が再登場したときに復習するようには心がけます．(2) オンデマンドの方ですが，録画したものを編集して公開するまでに，最低でも1日はかかると思っていてください．そのため，クイズやコメントの期限をその日の間に延ばしてもご要望には対応できない形になります．それも考慮して，クイズやコメントの期限は延ばさないこととします．この授業は教室で受講することを基本想定としていて，リアルタイムのZoomミーティングとオンデマンドのYouTube動画は補助的なものであると思ってください．
  • 大学院先行履修を考えているものです。グラフ関連はある程度覚えている自信がありますが、線形代数はかなり怪しいので復習して臨もうと思います。
    --線形代数はいろいろな場面で使われます．ぜひ復習をしてください．
  • 今まで全く触れてこなかった内容だったため、受講前は少し難しそうだと感じていましたが、先生の説明がとても分かりやすく、話し方も面白かったため、履修したいと思いました。次回の講義も楽しみにしています。
    --だんだんと難しくなっていくと思いますので，油断しないようによろしくお願いします．
  • エクスパンダは直径を小さくするものだと知れて興味がますます湧きました
    --授業の中でも述べましたが，グラフの直径は通信ネットワークなどの重要な評価指標となります．直径については第4回の授業で集中的に扱う予定です．
  • はじめのこの講義の導入部分がすごくおもしろかった。ひとつのテーマを半期通して学ぶ講義は初めてなのでとても楽しみです。
    --導入部分をお楽しみいただけて，私もうれしいです．
  • 昨年度の離散数理工学に引き続き，今年度もよろしくお願いします．
    学域で学んだやつらが，アベンジャーズみたいな雰囲気で出てくる感じがして，面白そうでした．
    --たしかにアベンジャーズみたいですね！ それらがどのように結びついていくのかということを味わってください．
  • 情報可視化の研究をしており、ネットワーククラフを扱っているため、グラフについて改めて基礎を確認することができました。
    --今回は復習でしたが，次回から新しい内容も出てくると思います．お楽しみに．
  • •　"教員がまじめにプログラミングをしたことがない"とありましたが、まじめにプログラミングをするとはどういうことでしょうか?
    •　単純なグラフだけではなく、多重辺や自己閉路を含めたグラフを扱う気がしていて楽しみです。多重辺や自己閉路は自分がこれまでグラフを扱う場面であまり考えなかったので。
    --分けて回答します．(1) 私にとって「まじめなプログラミング」は，公開して他の人に使ってもらえるプログラムを作ること，と，論文に書くことができる計算機実験を行うためにプログラムを作ることです．私にはそのような経験がないということです．(2) 多重辺や自己閉路を扱うのはなかなか厄介なのですが，この授業の内容ではむしろ積極的に扱っていくほうが自然なので，そのようにしていきます．
  • 多重集合を想定したのはなぜなのかが今後分かるのかなと思いました。また、閉路になるグラフはn角形に限られるのか、例外があるのか気になりました。そして、閉路においてn=1, 2のグラフは定義はしているが、実際はあまり議論されないのかなと思いました。
    --多重集合を想定していることはあまり本質的でないかもしれません．ただ，今後の話の中で扱いやすいはずなのでそうしています．また，閉路について，n=1, 2の場合をあまり議論しないというのはそのとおりだと思います．今後もnの範囲は注意すべきことになっていきます．閉路がn角形になるかどうかというのは描き方によります．むしろ「nが3以上のとき，閉路はn角形になるように描ける」と言うのが正確なのかもしれません．
  • 次数の数え方の感覚(注目する頂点の近くを見てそこから出ている辺の総数を考える)は理解できたと感じています。しかし、自己閉路の際に2回数えるということに対して、すぐには納得感がなかったです。ですが、握手補題から考えて辻褄を合わせると確かに自己閉路は2の方が良さそうだと感じています。
    --はい，握手補題を成り立たせるために，そのように次数を定義していると考えるのがよいと思います．多重集合を使わない場合に定義したグラフに対して成り立ついろいろな性質が，そのまま多重集合版でも成り立つようにすると，都合がよいのです．
  • どういうものに応用されているのか簡単に知れてよかった。
    非連結のグラフの場合、必然的に直径は∞になる。
    ラマヌジャンは天才すぎるという話をよく聞きますが、今回初めてエクスパンダについて聞いて、ここにもいるんだと知って驚きました。
    --「ラマヌジャン・グラフ」というものをラマヌジャンが定義したわけではなく，ラマヌジャン・グラフの構成の中でラマヌジャンの功績を使っているために彼の名がつけられているのだと思っています．
  • 半年間よろしくお願いします。グラフは研究でも使っていて身近に感じます。ここでの話は無向、有向はあまり考えないのでしょうか。
    --この授業では有向グラフが登場しない予定です．この授業であつかうエクスパンダは無向グラフです．一方で，エクスパンダの有向グラフ版も研究されています．
  • pg36/43ですが、u, v\in X を示すG[X]の例を提示した方がいいと思いました。
    --この例でお伝えしたかったことが伝わっていないかもしれないので，再度説明します．この例はX={a, b, c}のときのG[X]です．定義に現れるu, vは一般の頂点であり，特定の頂点を指しているわけではないことに注意してください．
  • 約8年ぶりに岡本先生の授業を受けます。今回の内容はグラフ理論の基本の復習が主だったと思いますが、以前教わってから忘れていたことも多かったので次回はよく復習してから授業に来ることに決めました。年数が経ってから知識の定着
    --8年ぶりとはかなりお久しぶりです．忘れていること自体はかまいませんので，思い出しやすくなるように整理しておいてください．

• 毎回のクイズと1回の期末試験により評価を行う予定でいます．

• こちらをご覧ください

• 10/6 (1) グラフ理論速習
• 10/13 (2) グラフのスペクトル
• 10/20 (3) グラフの等周定数とエクスパンダ
• 10/27 休み
• 11/3 休み (文化の日)
• 11/10 (4) グラフの等周定数と直径
• 11/17 (5) グラフの等周定数とランダムウォーク
• 11/24 (6) Cheegerの不等式
• 12/1 休み (秋ターム試験)
• 12/8 (7) Alon-Boppanaの定理： 第1の証明
• 12/15 (8) Alon-Boppanaの定理： 第2の証明
• 12/22 (9) ジグザグ積： 定義
• 12/29 休み (冬季休業)
• 1/5 (10) ジグザグ積： 証明
• 1/12 (11) エクスパンダの構成
• 1/19 (12) リフト： 定義
• 1/26 (13) リフト： 性質の照会
• 2/2 休み (修士論文発表会)
• 2/9(?) 期末試験

• M. Krebs, A. Shaheen, Expander Families and Cayley Graphs: A Beginner's Guide. Oxford University Press, 2011.
• F.R.K. Chung, Spectral Graph Theory, AMS, 1997.
• C. Godsil, G. Royle, Algebraic Graph Theory, Springer, 2001.
• B. Nica, A Brief Introduction to Spectral Graph Theory, 2018. (邦訳あり)
• T. Checherini-Silberstein, F. Scarabotti, F. Tolli, Discerete Harmonic Analysis, Cambridge University Press, 2018.
• G. Davidoff, P. Sarnak, A. Valette, Elementary Number Theory, Group Theory, and Ramanujan Graphs. Cambridge University Press, 2003.

• 離散最適化基礎論 (2025年度) テーマ：高速指数時間アルゴリズム
• 離散最適化基礎論 (2024年度) テーマ：ジョブ・スケジューリングのアルゴリズム
• 離散最適化基礎論 (2023年度) テーマ：ネットワークフロー
• 離散最適化基礎論 (2022年度) テーマ：整数計画法
• 離散最適化基礎論 (2021年度) テーマ：グラフの準同型
• 離散最適化基礎論 (2020年度) テーマ：マッチング
• 離散最適化基礎論 (2019年度) テーマ：離散最適化における計算困難性
• 離散最適化基礎論 (2018年度) テーマ：理想グラフに対する組合せ最適化
• 離散最適化基礎論 (2017年度) テーマ：幾何的被覆問題
• 離散最適化基礎論 (2016年度) テーマ：グラフの木分解
• 離散最適化基礎論 (2015年度) テーマ：組合せ最適化におけるマトロイドの役割
• 離散最適化基礎論 (2014年度) テーマ：組合せ最適化における線形計画法の利用
• 離散最適化基礎論 (2013年度) テーマ：局所探索法の理論的側面
• 離散最適化基礎論 (2012年度) テーマ：ゲーム理論における離散構造とアルゴリズム