分からない問題はここに書いてね195
■ このスレッドは過去ログ倉庫に格納されています
0207132人目の素数さん
NGNG最長パスを2つ用意して、共通点が無いとする。
A-B
C-D
とする。
それぞれのパスから途中の点を1点ずつとって
A-P-B
C-Q-D
とする。
PとQは端点A,B,C,Dと重複してもよい。
この時、P,Qを上手く取れば、A-B, C-DとP,Q以外で交わらないパスで
P,Qを結べる。
途中で交わった場合は、A-Bと交わっているならば、その交点をPの代わりに
C-Dと交わっているならば、Qの代わりに取り直せばよい。
A-P-Q-D
A-P-Q-C
B-P-Q-C
B-P-Q-D
のうち少なくとも一つは 最長パスより長い。
■ このスレッドは過去ログ倉庫に格納されています