フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

2017-07-13から1日間の記事一覧

完全有向グラフはハミルトンパスを持つ

頂点の完全グラフの各辺に向きが与えられたものを頂点の完全有向グラフといいます。例えば下の図のようなものです。 実は完全有向グラフには必ずハミルトンパスが存在します。ハミルトンパスとは全ての頂点を1回ずつ通る道のことです(閉路でなくても構いま…