Xmas Contest 2020 G: Graph Products 解説

Xmas Contest 2020

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_g

問題概要

無向単純グラフ H, H' に対し，"Cartesian product" H \mathbin{\square} H' と "tensor product" H \times H' が同型か判定せよ．

考察

サンプルは全然あてになりません．クリスマスだから許されている (許されていますか？) 無みたいなサンプルシリーズも久しぶりですね (2010 G, 2012 D, 2014 C)．

小さいグラフで同型になるものを探してみると，まずは H, H' が 1 点というのがありますね．そして孤立点が複数並んでいても同型です．もうちょっと探すと H, H' ともに三角形にすると同型になることが見つかるかもしれません (図を書いてみてもそんなに明らかではないと思います)．三角形がいくつか並んでいるもの同士でも OK です．

辺の数に着目するというのも思いつきやすい考察だと思います． N M' + M N' = 2 M M'，したがって (N - M) M' + M (N' - M') = 0 のような式が得られます．これだけで直接嬉しいことはなさそうですが， N = M のグラフが怪しいというヒントにはなるかもしれません．

結論

a \ge 3 に対し， a 頂点の閉路を C_a と書きます．

結論を述べると， H \mathbin{\square} H' と H \times H' が同型であるための必要十分条件は，以下のいずれかを満たすことです：

  1. H も H' もすべての頂点が孤立点である (辺がない)．
  2. ある奇数 a \ge 3 が存在して， H も H' もすべての連結成分が C_a である．

これは線型時間で判定できます．元の問題も，各グラフについて前計算することで入力について線型時間でできます．

十分性

1. の場合は，頂点数が等しくて辺がないので同型です．

2. の場合を考えます． H の連結成分と H' の連結成分の組それぞれに対し， H \mathbin{\square} H' および H \times H' に対応する C_a \mathbin{\square} C_a および C_a \times C_a が (誘導部分グラフとして) 含まれるので，結局 C_a \mathbin{\square} C_a と C_a \times C_a が同型であることを示せばよいです．

C_a の頂点集合を \mathbb{Z}/a\mathbb{Z} とみなし， u, v \in \mathbb{Z}/a\mathbb{Z} を結ぶ辺があることを v - u = \pm 1 と同値であるようにできます ( \operatorname{mod} a で隣り合うものを辺で結ぶということ)．写像 \colon \mathbb{Z}/a\mathbb{Z} \to \mathbb{Z}/a\mathbb{Z}; (u, u') \mapsto (u + u', u - u') を考えると，逆写像 (v, v') \mapsto \left(\frac{v+v'}{2}, \frac{v-v'}{2}\right) があるので全単射であり， C_a \mathbin{\square} C_a の (u, u') と (u + 1, u') を結ぶ辺， (u, u') と (u, u' + 1) を結ぶ辺を，それぞれ C_a \times C_a の (u + u', u - u') と (u + u' + 1, u - u' + 1) を結ぶ辺， (u + u', u - u') と (u + u' + 1, u - u' - 1) を結ぶ辺に移せるので，そして逆の対応も同様なので・あるいは辺の数が 2 a^2 で等しいので， C_a \mathbin{\square} C_a と C_a \times C_a は同型です．

平たく言えば，図を書いて片方を 45 度回転させてよく見ると同型になっています．足したり引いたりしているところに両方とも同じ \mathbb{Z}/a\mathbb{Z} であることを， 2 で割っているところに a が奇数なことが使われています．

必要性

以下の順で検討します：

  1. 最大次数
  2. 次数
  3. 連結成分の個数
  4. 二部であるような連結成分の個数
  5. 含まれる最小の奇閉路の大きさ

もちろんこれはある程度整理された道筋なので，実際に解くときにこのようにきれいにできるべきという話ではありません．

H \mathbin{\square} H' と H \times H' が同型とします．

1. H の頂点の次数を d_1 \le \cdots \le d_N， H' の頂点の次数を d'_1 \le \cdots \le d'_{N'} とします．すると， H \mathbin{\square} H' の頂点の次数は d_u + d'_{u'} たち， H \times H' の次数は d_u d'_{u'} たちとなります．特に， H \mathbin{\square} H' と H \times H' で最大次数は等しいので， d_N + d'_{N'} = d_N d'_{N'} となります． 1 = (d_N - 1) (d'_{N'} - 1) となるので， (d_N, d'_{N'}) = (0, 0), (2, 2) のみがあり得ます．前者の場合は辺がないのでこれでよいです．以下後者であると仮定します．

2. H に次数 1 の頂点があるとすると， H \mathbin{\square} H' には次数 1 + 2 = 3 の頂点がありますが H \times H' にはなく矛盾します．よって H には次数 1 の頂点がなく， H' も同様です．するとさらに， H に次数 0 の頂点があるとすると， H \mathbin{\square} H には次数 0 + 2 = 2 の頂点がありますが H \times H' にはなく矛盾します．よって H には次数 0 の頂点がなく， H' も同様です．以上より， H, H' ともにすべての頂点の次数が 2 であり，すなわちすべての連結成分が閉路です．

H の連結成分を C_{a_1}, \ldots, C_{a_l}， H' の連結成分を C_{a'_1}, \ldots, C_{a'_{l'}} とすると， H \mathbin{\square} H' は C_{a_i} \mathbin{\square} C_{a'_{i'}} たちを並べたもの， H \times H' は C_{a_i} \times C_{a'_{i'}} たちを並べたものです．

a, a' \ge 3 とします． C_a, C_{a'} の頂点集合を十分性を示したときと同様に \mathbb{Z}/a\mathbb{Z}, \mathbb{Z}/a'\mathbb{Z} とみなし，差が 1 の頂点が辺で結ばれているとします． C_a \mathbin{\square} C_{a'} について，

  • a, a' ともに偶数のとき，連結で，二部である ( (x, y) \in \mathbb{Z}/a\mathbb{Z} \times \mathbb{Z}/a'\mathbb{Z}) に対し ( (x \bmod 2) + (y \bmod 2) ) \bmod 2 が well-defined でこれで二部に塗り分けできる)
  • a, a' の一方のみ奇数のとき，連結で，二部でない ( C_a, C_{a'} を部分グラフとして持つため)
  • a, a' ともに奇数のとき，連結で，二部でない ( C_a, C_{a'} を部分グラフとして持つため)

また， C_a \times C_{a'} について，

  • a, a' ともに偶数のとき，非連結である ( (x, y) \in \mathbb{Z}/a\mathbb{Z} \times \mathbb{Z}/a'\mathbb{Z}) に対し ( (x \bmod 2) + (y \bmod 2) ) \bmod 2 が well-defined で，これで連結成分が分かれる)
  • a, a' の一方のみ奇数のとき，連結で，二部である ( a が奇数として，各頂点から (+1, +1) と (+1, -1) を繰り返し辿ると (+1, 0) ができるので (+1, +1) と合わせて連結． (x, y) に対し y \bmod 2 が well-defined でこれで二部に塗り分けできる)
  • a, a' ともに奇数のとき，連結で，二部でない (上と同様に各頂点から (+1, 0) や (0, +1) ができるので連結．ある頂点から (+1, +1) を繰り返し辿ると C_{\mathrm{lcm}(a,a')} を部分グラフとして持つことがわかるので二部でない)

ということがわかります．

3. C_{a_i} \mathbin{\square} C_{a'_{i'}} はすべて連結なので， H \mathbin{\square} H' の連結成分は l l' 個． H \times H' もそうであるためには C_{a_i} \times C_{a'_{i'}} もすべて連結であることが必要で，よって a_i, a'_{i'} がともに偶数とはなりません．

4. a_i, a'_{i'} がともに偶数とはならないので， C_{a_i} \mathbin{\square} C_{a'_{i'}} はすべて，二部でないです．よって H \mathbin{\square} H' の連結成分はすべて，二部でないです． H \times H' もそうであるためには C_{a_i} \times C_{a'_{i'}} もすべて，二部でないことが必要で，よって a_i, a'_{i'} はすべて奇数です．

5. a, a' \ge 3 を奇数とするとき，

  • C_a \mathbin{\square} C_{a'} が含む最小の奇閉路の大きさは \min\{a, a'\} (閉路に沿って移動した \pm 1 の和がどちらかの成分で奇数なので，どちらかの成分は ( \operatorname{mod} a あるいは \operatorname{mod} a' で) 1 周以上しなければならない． C_{\min\{a, a'\}} を含むのは明らか)
  • C_a \times C_{a'} が含む最小の奇閉路の大きさは \max\{a, a'\} (閉路に沿って移動した \pm 1 の和が両方の成分で奇数なので，両方の成分が 1 周以上しなければならない． C_{\max\{a, a'\}} は， (+1, +1) を \min\{a, a'\} 個と残りを (+1, -1) または (-1, +1) で作れる)

ということがわかります．よって \min\{a_i, a'_{i'}\} たちの多重集合と \max\{a_i, a'_{i'}\} たちの多重集合が等しい必要があります．対応する各元ごとに \le なのですべて等号でなければならず， a_i, a'_{i'} がすべて等しいことが従います．

統計情報

正解者：チーム YdeOgwSasUshPunO (0:52:16) はじめ 12 チーム

コメント

白状すると，わたしは最初異なる奇閉路の積の場合を勘違いしていました…… (嘘の同型を作っていた上に，見直しのときは場合分けが漏れました)．maroon さんに test-solve してもらったときに気づいて，証明を書き直してチェックを受けました．直感が働きにくい問題なので，気を付けましょう．危ないところでした．