maximal cliques の clique 同士は勝手には merge できない

SDP を細かい対角ブロックに変換するときに、 chordal graph を用いて maximal cliques を生成し、この cliques を用いて変換する方法がある。
このときに、clique があまりに細かく分類されたときには、clique tree に従って clique 同士を merge する。つまり、clique tree で隣同士の clique が merge される。

ここで、隣同士ではない clique を merge するとどうなるか調べてみたが、この場合はうまく変換できないことがわかった。
たとえば、cliques が {1,2},{2,3},{3,4},{4,5},{5,6} となっているとき、これらを順につなぐと clique tree が作れるし、これらは maximal cliques になっている。
このときに、{1,2},{5,6} を {1,2,5,6} に merge すると、maximal cliques でなくなってしまう。
(2,3,4,5 が 4 の長さの cycle になってしまうため)

ちなみに、clique  を merge できる簡単な場合は
(1) clique tree で隣同士
(2) clique tree で間にひとつだけ clique がある同士
であるが、他にもいろいろな条件で merge できる場合がある。

今日の作業内容：clique の性質調べ 4h + trilateration 1h
今日のランチ：らく　マグロのづけ丼
明日の予測作業時間：5h