FindGraphIsomorphism
FindGraphIsomorphism
FindGraphIsomorphism[g1,g2]
通过重命名顶点找到将图 g1 映射到 g2 的同构.
FindGraphIsomorphism[g1,g2,n]
找到至多 n 个同构.
FindGraphIsomorphism[{vw,…},…]
使用规则 vw 指定图 g.
更多信息和选项
- FindGraphIsomorphism 也称为保边双射.
- FindGraphIsomorphism 通常用于识别等效结构和验证各种表示的等效性.
- FindGraphIsomorphism 给出一个关联列表 Association[v1->w1,v2->w2,…]，该列表可使得若wi 和 wj 为 g2 中的相邻顶点，则 vi 和 vj 为 g1 中相邻顶点，且反之亦然.
- 如果找不到同构则 FindGraphIsomorphism 会给出空列表.
- FindGraphIsomorphism[g1,g2,All] 给出全部同构.
范例
打开所有单元 关闭所有单元基本范例 (2)
范围 (8)
规范 (5)
FindGraphIsomorphism 适用于无向图：
FindGraphIsomorphism[[image], [image]]FindGraphIsomorphism[[image], [image]]FindGraphIsomorphism[{1 -> 2, 1 -> 3, 1 -> 4}, {"a" -> "b", "a" -> "c", "a" -> "d"}]FindGraphIsomorphism[CycleGraph[3], CycleGraph[4]]FindGraphIsomorphism 适用于大型图：
g = GridGraph[{10, 10, 10}];h = VertexReplace[g, Thread[VertexList[g] -> RandomSample[VertexList[g], VertexCount[g]]]];FindGraphIsomorphism[g, h]//Short//Timing应用 (1)
g = PetersenGraph[4, 1, VertexLabels -> "Name", ImagePadding -> 10, VertexSize -> Large];v1 = {"a", "b", "c", "d"};v2 = {"e", "f", "g", "h"};edge = Table[(v1[[i]]#)& /@ Delete[v2, 5 - i], {i, 4}]//Flatten;h = Graph[Join[v1, v2], edge, VertexLabels -> "Name", ImagePadding -> 10, VertexSize -> Large, AbsoluteOptions[CompleteGraph[{4, 4}], VertexCoordinates]];map = (Normal /@ FindGraphIsomorphism[g, h])[[1]]a = First /@ map;b = Last /@ map;highlightGraph[g_, v_] := HighlightGraph[g, Table[Style[Labeled[v[[i]], v[[i]]], ColorData["TemperatureMap"][i / VertexCount[g]]], {i, VertexCount[g]}]];{highlightGraph[g, a], highlightGraph[h, b]}属性和关系 (3)
{g, h} = {PetersenGraph[4, 1], HypercubeGraph[3]}FindGraphIsomorphism[g, h]VertexCount[g] == VertexCount[h]EdgeCount[g] == EdgeCount[h]使用 IsomorphicGraphQ 检验两个图是否是同构的：
{g, h} = {CycleGraph[4], Graph[{23, 34, 41, 12}]}FindGraphIsomorphism[g, h]IsomorphicGraphQ[g, h]g = [image];h = [image];FindGraphIsomorphism[g, h]CanonicalGraph[h] == CanonicalGraph[g]
Wolfram Research (2010)，FindGraphIsomorphism，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindGraphIsomorphism.html （更新于 2015 年）.
文本
Wolfram Research (2010)，FindGraphIsomorphism，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindGraphIsomorphism.html （更新于 2015 年）.
CMS
Wolfram 语言. 2010. "FindGraphIsomorphism." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2015. https://reference.wolfram.com/language/ref/FindGraphIsomorphism.html.
APA
Wolfram 语言. (2010). FindGraphIsomorphism. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/FindGraphIsomorphism.html 年