Diracの定理を夕食会で証明する

Dirac's Theorem at a Dinner Party

Diracの定理を夕食会で証明する

グラフ理論のHamiltonianサイクルに関するDiracの定理を、円卓を囲む夕食会の比喩で証明する記事。各ゲストを頂点、友人関係を辺と見なし、全員が十分な数の友人を持てば、隣同士が友人になるよう円卓に着席できることを示す。鍵となるのは「交差」と「フリップ」で、じゃがいもを回す思考実験で交差の存在を証明する。Barnette予想に関する次回記事の準備でもある。

もしすべてのゲストが少なくともn/2人の友人を持っていれば、どんな2人の他人同士でも、すべての隙間には交差が存在する。

この日のほかの記事

2026-11-22