数学-グラフ理論

Prüfer sequence

ラベル付き木から prüfer sequence(プリューファ列)と呼ばれる整数列への一対一対応を説明します.

再構成問題

グラフ理論の有名な未解決問題である再構成予想について紹介します.

頂点被覆問題のNP完全性

頂点被覆問題がNP完全であることを示します.頂点被覆問題のNP完全性から独立集合問題とクリーク問題がNP完全であることが導かれます.

DAGの最小道被覆問題

問題. DAGの最小道被覆問題 DAG が与えられる. の最小道被覆を求めよ.

比較可能グラフは理想グラフ

比較可能グラフが理想グラフであることを示します.

グラフ描画用のツール

グラフを描画するためのツールをまとめておきます.他に知っている方は教えてくださると喜びます.