ブログ名

競技プログラミングやお歌のお話をする高菜です。

平面内にの pairwise disjoint な長方形3個の配置の分類(品目定理)とそのグラフ理論的証明

変な用語を普及させてしまってまた怒られそうなので、後世の方が「品目定理ってなんですか!?」になったときのために一応残しておきましょう。

主張

平面内にの pairwise disjoint な長方形3個の配置 が与えられているとします。このときこれは垂直な直線または水平な直線で $1$ 個と $2$ 個に分けることができます。

ただし長方形は空でない閉区間の直積であり、直線で分けられるというのは、平面に関する直線の補集合の $2$ つの連結成分に含まれるという意味であるとします。より正確にいうと長方形は

$$ R _ i = X _ i \times Y _ i \subset \mathbb{R}^2 \ (i = 1, 2, 3) $$

と表され、直線 $x = a$ で $1$ 個と $2$ 個に分けられるというのは開半平面 $x < a$ と $a < x$ のどちらの部分集合であるかで長方形を $1$ 個と $2$ 個に分類できるということです。

証明

頂点集合 $V = \left \{ 1, 2, 3 \right \}$ を考えます。さらに相異なる頂点 $i, j$ の間には $X _ i \cap X _ j \neq \emptyset$ のとき赤色の辺が、$Y _ i \cap Y _ j \neq \emptyset$ のときに青色の辺があるようなグラフを考えると、$2$ 頂点の間に赤色と青色両方の辺があることはないため、赤色の辺と青色の辺の少なくとも一方は $1$ 本以下しかありません。その色を $c$ としましょう。

すると色 $c$ の辺のみからなる誘導部分グラフは非連結です。このグラフの各連結成分に、その連結成分に所属する(長方形の射影である)区間の合併を対応させておくことで、連結成分の集合は pairwise disjoint な区間の集合に対応するので、これをソートして好きなところで分ければよいです。

様々な配置

ちなみにこのグラフ区間グラフと言って割と特徴が調べられていたりします ☞ 区間グラフ - Wikipedia

なぜこれが品目定理なのか

$1$ 個と $2$ 個に分けたらさらに $2$ 個の方も垂直か水平に分けましょう。あら不思議、漢字の「品」みたいな形か、漢字の「目」みたいな形になりましたね。(これで $6$ 通りに場合分けできたわけですけれども、複数の場合に該当するような配置も存在するため注意です。)

長方形 $4$ この場合

四畳半みたいな配置のときに分割できないのでダメダメです。$K _ 4$ の $6$ 個の辺をハミルトンパス $2$ 本に分解した形になっていて面白いですね。(余談ですけれどもこういう面白いお話もあります ☞ Complete GraphのHamilton cycle(path)への分割 - YKK++

品目定理の命名

たぶん↓が初出です。

発端の問題

F - Non-overlapping Squares