隣接行列談義

指圧マット @shiatsumat

隣接行列が A である連結な無向グラフ G において以下が同値になるのを知った。面白い。 (1) d は G の直径である。 (2) d は A^d + A^(d-1) の全成分が非零になる最小の正整数である。 (3) d は (A+I)^d の全成分が非零になる最小の正整数である。

きゅうり @kyuridenamida

@shiatsumat 考えてみれば確かに...感ありますけどこの性質が本質的に重要なオモシロ問題とかあったりするんですかね

指圧マット @shiatsumat

@kyuridenamida 少なくともグラフの直径を求めるお手軽アルゴリズムには使えるみたいです（繰り返し自乗法を使って d-1 を上の桁から順に決定できます）

きゅうり @kyuridenamida

@shiatsumat やってる操作もだいぶ似ているしワーシャルフロイドして最短経路の最長求めるO(N^3)で誤魔化すのはダメだろうか(ところで元々の主張ってAは重み無しですよね?

指圧マット @shiatsumat

@kyuridenamida 確かに冷静に考えるとその点はふつうにワーシャルフロイトのほうが優秀そうですね…… 隣接行列で普通の環を入れる場合は、多重辺を認めるが重みはないということになって、行き方の総数を求めていることになります

きゅうり @kyuridenamida

@shiatsumat あーなるほど隣接行列の定義を忘れてました。多重辺のことを考えると要素の値を重みとして解釈するのはナンセンスでしたね