グラフ同型

ウィキペディア

グラフ同型

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/07/28 08:38 UTC 版)

グラフ同型（グラフどうけい）とはグラフ理論における概念の一つである。

概要

${\displaystyle G=(V,E),G'=(V',E')}$ ${\displaystyle a\mapsto 1}$

${\displaystyle b\mapsto 6}$

${\displaystyle c\mapsto 8}$

${\displaystyle d\mapsto 3}$

${\displaystyle g\mapsto 5}$

${\displaystyle h\mapsto 2}$

${\displaystyle i\mapsto 4}$

${\displaystyle j\mapsto 7}$

このとき、隣接する頂点に対応する頂点は隣接していることがわかる。 このように ${\displaystyle G}$ と ${\displaystyle G'}$ が「同一」の頂点を持ち、同一の辺のつながりかたをしているときにそのグラフを同型というのである。

グラフ同型性判定問題

与えられた二つのグラフが同型か否かを判定する問題である。この問題がNPに属することは分かっているが、P, co-NP, BPPに属するかどうかは分かっていない。NP完全に属するかどうかも分かっていないので、量子計算機を用いて多項式時間で解けるかどうかに関しても、さかんに研究されている。より詳しい状況は英語版のWikipediaを参照されたい。

脚注

1. ^ ディーステル 2000, p. 3 (p. 32)

参考文献

• ディーステル, R. 著、根上生也・太田克弘 訳『グラフ理論』（原書第2版）シュプリンガー・フェアラーク東京、2000年。ISBN 978-4-431-70876-6。https://books.google.co.jp/books?id=CZq8AAAAQBAJ。 
• 戸田誠之助：「グラフ同型性判定問題」，富山房（2001）．