MathLabs

第2問

PP を正 20062006 角形とする。PP の対角線は、その両端点が PP の周をそれぞれ奇数個の PP の辺からなる二つの部分に分けるとき、良いと呼ぶ。PP の辺もまた良いと呼ぶ。PP が、PP の内部で共有点を持たない 20032003 本の対角線によって三角形に分割されているとする。このような配置に現れ得る、二つの良い辺を持つ二等辺三角形の個数の最大値を求めよ。
ステップ 2/5: 三角形分割木から良い対角線を除く
前のステップ次のステップ
ざっくり言うと

20042004 個の三角形を頂点とし、二つの三角形が対角線を共有するとき辺で結んだものは木になる。kk 本の良い対角線を除くと、この木は k+1k+1 成分に分かれる。

T=dual tree of the triangulation,F=T∖{edges for good diagonals}T=\text{dual tree of the triangulation},\qquad F=T\setminus\{\text{edges for good diagonals}\}
詳しい解説

多角形の三角形分割の双対グラフ TT は 20042004 頂点の木である。使われる良い対角線の本数を kk とする。対応する kk 本の辺を除くと、FF は k+1k+1 本の木からなる森になる。