小特集 6. グラフ同型性判定問題への招待

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 6.

グラフ同型性判定問題への招待

Invitation to the Graph Isomorphism Problem

大舘陽太

大舘陽太 正員 熊本大学大学院先端科学研究部環境科学部門

Yota OTACHI, Member (Faculty of Advanced Science and Technology, Kumamoto University, Kumamoto-shi, 860-8555 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.267-271 2018年3月

©電子情報通信学会2018



本会誌では,用語は①文部省(文部科学省)学術用語集電気工学編,②本会編の改訂電子情報通信用語辞典,③本会編のエンサイクロペディアハンドブック,に基づき統一している.本稿中の「同型」は,上記②,③に従うと「同形」であるが,ここでは著者の希望により「同型」で掲載した.

abstract

 二つのグラフが「同じ」構造かどうかを判定する問題をグラフ同型性判定問題と呼ぶ.これは,グラフアルゴリズムにおける基本的なものであるにもかかわらず,その計算量が判明していない珍しい問題である.本稿では,この問題に対する既存結果や未解決問題,最近の進展などを紹介する.

キーワード:グラフ同型性判定問題,GI完全性

1.は じ め に

 グラフは様々なものの構造を抽象的に表すものである.一見違うものに見えても,グラフによって抽象化されると本質的には同じ構造だったと分かる場合がある.では,「二つのグラフが表す構造が同じ」,またはより直接的に,「二つのグラフが同じ」とはどのように定義されるべきだろうか.グラフの同型性は,グラフが「同じ」であることを表す最も自然な概念であり,以下のとおり定義される.

 グラフmathmathを考える.全単射mathがあり,

math

が成り立つとき,mathmathは同型であるといい,mathと書く.また,このときmathmathからmathへの同型写像と呼ぶ.

 直感的には,「もの同士のつながりを表す」というグラフの機能において,mathmathが同等であることがmathにより保証されており,多くの場面では,mathmathを「同じ」とみなすことが自然である.

 例えば,図1の二つのグラフが同型であることは,中列の2頂点の上下を入れ替える写像を作れば示すことができる.

fig_1.png


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電信情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電信情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。