IsomorphicGraphQ

IsomorphicGraphQ[g1,g2]

グラフ g1と g2が同型であればTrueを，それ以外の場合にはFalseを返す．

詳細

  • IsomorphicGraphQは，グラフ同型問題としても知られている．
  • IsomorphicGraphQは，通常，2つのグラフが構造的に等しいかどうかの判定に使われる．
  • あるグラフの頂点の名前を変えることで他と等しいグラフが得られる場合，この2つのグラフは同型写像である．
  • IsomorphicGraphQ[g1,g2,…]は，すべての giが同型であればTrueを与える．

例題

すべて開くすべて閉じる

例  (1)

2つのグラフが同型写像かどうか調べる：

g を h にマップする同型写像を求める：

グラフ g の頂点名を変えると h と同じグラフになる：

スコープ  (4)

IsomorphicGraphQは無向グラフに使うことができる：

有向グラフ：

同型写像ではないグラフに対しては，IsomorphicGraphQはFalseを返す：

グラフではない式に対しても同様である：

IsomorphicGraphQは大きいグラフに使うことができる：

特性と関係  (10)

同型写像グラフには同数の頂点と辺がある：

同型写像のグラフの辺は同じ順序の次数列を持つ：

同じ次数列のグラフが同型写像ではないこともある：

FindGraphIsomorphismを使って頂点間をマップすることができる：

マッピングに従って2つのグラフをハイライトしラベルを付ける：

グラフ内の頂点を並べ替えると同型写像ができる：

隣接行列の並べ替えで生成されたグラフはそれ自身に対する同型写像である：

頂点リストの並べ替えサンプル：

巡回グラフ の線グラフは 自身との同型写像である：

経路 の線グラフは の同型写像である：

の線グラフの補グラフは，ペテルセングラフの同型写像である：

2つの連結グラフはその線グラフが同型写像であるときかつそのときに限り同型写像である：

1つの例外がある：

同型写像ではない有向グラフが，無向グラフの場合には同型写像になることもある：

Wolfram Research (2010), IsomorphicGraphQ, Wolfram言語関数， https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html （2012年に更新）.

テキスト

Wolfram Research (2010), IsomorphicGraphQ, Wolfram言語関数， https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html （2012年に更新）.

CMS

Wolfram Language. 2010. "IsomorphicGraphQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2012. https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html.

APA

Wolfram Language. (2010). IsomorphicGraphQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html

BibTeX

@misc{reference.wolfram_2024_isomorphicgraphq, author="Wolfram Research", title="{IsomorphicGraphQ}", year="2012", howpublished="\url{https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_isomorphicgraphq, organization={Wolfram Research}, title={IsomorphicGraphQ}, year={2012}, url={https://reference.wolfram.com/language/ref/IsomorphicGraphQ.html}, note=[Accessed: 22-November-2024 ]}