图的表示与图同构

图论中的图的同构与同构问题在图论中，同构是一个重要的概念。

图的同构指的是两个图结构完全相同，只是节点的标签或者边的标签不同。

而图的同构问题则是判断两个给定的图是否同构的问题。

本文将详细探讨图的同构与同构问题。

一、图的同构图的同构是指两个图结构完全相同，只是节点的标签或者边的标签不同。

为了更好地理解图的同构，我们先来了解一些基本概念。

1.1 图的定义在图论中，图由节点（也称为顶点）和边组成。

通常用G=(V, E)来表示一个图，其中V是节点（顶点）的集合，E是边的集合。

边可以用有序或无序对(u, v)来表示，表示节点u和v之间存在一条边。

1.2 同构图的定义给定两个图G1=(V1, E1)和G2=(V2, E2)，如果存在一一对应关系f: V1→V2，使得对于每条边(u, v)∈E1，有(f(u), f(v))∈E2，则称图G1与G2同构。

其中，f被成为同构映射。

二、图的同构问题图的同构问题是判断两个给定的图是否同构的问题，它是图论中的一个经典问题。

在实际应用中，图的同构问题非常重要，对于计算机视觉、网络安全等领域都有广泛应用。

2.1 图的同构问题的定义给定两个图G1=(V1, E1)和G2=(V2, E2)，判断它们是否同构。

2.2 图的同构问题的解决方法图的同构问题是一个NP问题，目前还没有确定的多项式时间解决算法。

在实际应用中，为了解决图的同构问题，通常采用以下方法：（1）特征向量法：通过计算图的特征向量，并比较两个图的特征向量来判断是否同构。

（2）图分类器法：通过训练一个图分类器，将同构和非同构的图进行分类。

（3）哈希算法法：通过为图节点和边生成一个唯一的哈希值，并比较两个图的哈希值来判断是否同构。

以上方法都有各自的优缺点，在不同的应用场景下选择合适的方法。

三、图的同构性质图的同构性质是指图的某些特征在同构映射下保持不变。

在判断图的同构性质时，可以利用这些性质来简化问题。

3.1 路径在判断图的同构性质时，路径是一个重要的性质。

图论中的图的同构与同胚图论是数学中的一个分支，研究了如何描述图以及图的性质和特征。

在图论中，同构和同胚是两个重要的概念，它们用来描述不同图之间的关系。

本文将介绍图的同构和同胚的概念、定义以及应用。

一、图的同构在图论中，如果两个图具有相同的结构，即结点和边的对应关系相同，但结点和边的标签可以不同，那么这两个图被称为同构的。

图的同构关系可以理解为，它们具有相同的拓扑结构，只是标签的不同。

二、图的同构的定义设G=(V,E)和G'=(V',E')是两个图，如果存在一个双射函数f:V→V'，使得(u,v)∈E当且仅当(f(u), f(v))∈E'，则称G和G'是同构的。

其中，V和V'分别表示两个图的结点集合，E和E'分别表示两个图的边集合。

三、图的同构的判断方法判断两个图是否同构是图论中一个典型的问题，有很多方法可以判断两个图是否同构，以下是几种常用的方法：1. 度序列法：图的度序列是指将图中结点按照度的大小排列得到的序列。

如果两个图的度序列相同，则它们可能是同构的。

2. 邻接矩阵法：将图用邻接矩阵表示，即一个n×n的矩阵，矩阵中的元素a[i][j]表示结点i和结点j之间是否有边。

如果两个图的邻接矩阵相同，则它们可能是同构的。

3. 搜索法：通过对图进行深度优先搜索或广度优先搜索，得到图的某种特征序列。

如果两个图的特征序列相同，则它们可能是同构的。

四、图的同胚在图论中，如果两个图具有相同的结构，即结点和边的对应关系相同，并且结点和边的标签也相同，那么这两个图被称为同胚的。

同胚可以理解为同构的一个特殊情况。

五、图的同胚的判断方法判断两个图是否同胚是图论中的一个难题，其复杂性在于需要同时考虑结点和边的对应关系。

目前还没有有效的算法可以快速地判断两个图是否同胚，只能通过试探的方法进行判断。

六、图的同构与同胚的应用图的同构和同胚在实际应用中有许多重要的应用，以下是几个典型的应用场景：1. 化学分子结构的比较：化学分子可以用图来表示，通过对比不同分子的图的同构关系，可以判断它们的相似性以及化学性质的差异。

第3章图的基本概念与性质一、概念图——图可以用集合的形式表示，即图可以表示为一个三元组，包含结点集、边集，以及边与结点对集间的映射．如果用结点对来表示边，则图可以表示成一个由结点集与边集组成的二元组．定义3.1.1图G是一个三元组<V（G），E（G），ϕG>，其中V（G）是一个非空的结点集（或称顶点集），E（G）是边集，ϕG是从边集E（G）到结点偶对（无序偶或有序偶）集上的函数．图定义中的结点偶对可以是有序的，也可以是无序的．有向边、端点——若图中的边e所对应的结点偶对是有序的，记为<a，b>，则称e是有向边（简称弧）．a，b分别称为弧的始点与终点，并均称为e的端点．称e是关联于结点a 和b的，结点a和结点b是相、邻的，或称结点a和结点b是邻接的．无向边、端点——若图中的边e所对应的结点偶对是无序的，记为（a，b），则称e是无向边（简称棱）．a，b称为e的端点．称e是关联于结点a和b的，结点a和结点b是相、邻的，或称结点a和结点b是邻接的．有向图——每一条边均为有向边的图称为有向图．无向图——每一条边均为无向边的图称为无向图．底图——如果把有向图中每条有向边都看作无向边，就得一个无向图，此无向图称为原有向图的底图．底图只表示出结点间的连接关系而没有表示出连接边的方向．弧立结点——图中不与任何相邻的结点称为弧立结点．零图——全由孤立结点构成的图称为零图．自回路（环）——关联于同一结点的一条边称为自回路或环．重边（平行边）——在有向图中，两结点间（包括结点自身间）若多于一条边，则称这几条边为重边或平行边．多重图——含有重边的图称为多重图．线图——非多重图称为线图．定义3.1.2（简单图）无自回路的线图称为简单图．定义3.1.3（结点的度数、最大度、最小度）图G=<V，E>中，与V中结点v（v∈V）相关联的边数，称为该结点的度数，记作为deg(v)．记∆（G）= max{deg(v)| v∈V（G）}，δ（G）= min{deg(v)| v∈V（G）}，分别称为G=<V，E>的最大度和最小度．定义3.1.4（出度、入度、度数）在有向图中，对于任何结点v，以v为始点的边的条数称为结点v的引出次数（或出度）；以v为终点的边的条数称为结点v的引入次数（或入度）；结点v的引出次数和引入次数之和称为v的次数（或度数）．定义3.1.5（二部图）设G=〈V，E>是n阶无向图，若能将V分成两个互不相交的子集V1与V2使得G中任一边的两端点都不在同一个V i（i=1,2）中，则称G为二部图．记G=<V1,V2，E>．定义3.1.6（完全图）简单图G=<V，E>中，若每一对结点间都有边相连，则称该图为完全图．有n个结点的无向完全图记为K n．定义3.1.7（k-正则图）若无向简单图中，每个结点的度均为某个固定整数k，则称该图为k-正则图．定义3.1.8（赋权图）赋权图G是一个三重组<V，E，g>或四重组<V，E，f，g>，其中V是结点集合，E是边的集合，f是定义在V上的函数，g是定义在E上的函数．定义3.1.9（补图）设图G=<V，E>有n个顶点，图H=<V，E’>也有同样的顶点，而E’是由n个结点的完全图的边删去E所得，则图H称为图G的补图，记为H=G，显然，G=H．定义3.1.10（子图、真子图、生成子图）设G=<V,E>和G’=<V’,E’>是两个图．(1)若V’⊆V且E’⊆E，则称G’是G的子图；(2)若V’⊂V或E’⊂E,则称G’是G的真子图；(3)若V’=V和E’⊆E,则称G’是G的生成子图；(4)若子图G’中没有孤立结点，G’由E’唯一确定，则称G’为由边集E’导出的子图；(5)若子图G’中，对V’中的任意两个结点u，v，当u，v∈V’时有[u，v]∈E’，则G’由V’唯一确定，则称G’为由结点集V’导出的子图．定义3.1.11(补图) 设G’=<V’，E’>是G=<V，E>的子图，若给定另外一个图G’’=<V’’，E’’>，使得E’’=E-E’，且V’’中仅包含E’’的边所关联的结点，则称G’’是子图G’的相对于G 的补图．定义3.1.12(同构) 设G=〈V，E>和G’=<V’,E’>是两个图，若存在从V到V’的双射函数f，使对任意[a，b]∈E，当且仅当[f(a)，f (b)]∈E’，并且[a，b]和[f(a)，f (b)]有相同的重数，则称G和G’是同构的．定义3.1.13(路径) 在图G=<V，E>中，设v0，v1，…，v n∈V，e1，e2,….,e n∈E，其中e i是关联于结点v i-1，v i的边，交替序列v0 e1 v1 e2…e n v n称为联结v0到v n的路径（或称路）．v0与v n分别称为路的起点与终点，边的数目n称为路的长度．孤立点——长度为0的路定义为孤立点．简单路径——若序列中所有的边e1，e2,…., e n均互不相同，则称此路径为简单路径．基本路径——若序列中所有的点v0，v1，…，v n均互不相同，则称此路径是基本路径．回路——若v0=v n，即路径中的终点与始点相重合，则称此路径为回路．简单回路——没有相同边的回路称为简单回路．基本回路（圈）——各结点均互不相同的回路称为基本回路（或圈）．奇圈（偶圈）——长度为奇（偶）数的圈称为奇（偶）圈．定义3.2.1（可达、连通）在图G=<V,E>中，设有结点v j与v k，若从v j到v k存在任何一条路径，则称结点v k从结点v j可达，也称结点v j与v k是连通的．定义3.2.2（连通图、非连通图、分离图）若G是平凡图或G中任意两个结点都是连通的，则称G是连通图，否则称G为非连通图或分离图．定义3.2.3（连通分支）设G=<V,E>是图，连通关系的商集为{V1,V2,…,V m}，则其导出的子图G(V i)（i=1,2,…m）称为图G的连通分支（图），将图G的连通分支数记作W（G）．定义3.2.4（短程线）设u与v是图G的两个结点，若u与v连通，则称u与v之间的长度最短的路为u与v之间的短程线，短程线的长度可作为结点u与v间的距离，记作d(u,v)，其满足下列性质：d(u,v) ≥ 0，u=v时，d(u,v) =0 （非负性）d(u,v) = d(v,u) （对称性）d(u,v) + d(v,w) ≥d(u,w) （三角不等式）若u与v不连通，则通常记d(u,v) = ∞．定义3.2.5（单向连通、强连通、弱连通）在简单有向图中，如果在任何结点偶对中，至少从一个结点到另一个结点可达的，则称图G是单向（侧）连通的；如果在任何结点偶对中，两结点对互相可达，则称图G是强连通的；如果图的底图（在图G中略去边的方向，得到无向图）是连通的，则称图G是弱连通的．定义3.2.6（极大强连通子图、极大单向连通子图、极大弱连通子图、强分图、单向分图、弱分图） 在简单有向图G =<V ，E >中，G’是G 的子图，如G’是强连通的（单向连通的，弱连通的），且没有包含G’的更大的子图G’’是强连通的（单向连通的，弱连通的），则称G’是极大强连通子图（极大单向连通子图，极大弱连通子图）又叫强分图（单向分图，弱分图）．定义3.2.7（点割集、割点） 设无向图G =<V ,E >为连通图，若有点集V 1⊂V ，使图G 删除了V 1的所有结点后，所得的子图是不连通图，而删除了V 1的任何真子集后，所得的子图是连通图，则称V 1是G 的一个点割集．若某个结点构成一个点割集，则称该结点为割点．定义3.2.8（点连通度） 若G 为无向连通图且不含Kn 为生成子图，则称k (G )=min{|V 1| ∣V 1是G 的一个点割集}为G 的点连通度（简称连通度）．规定：完全图Kn 的点连通度为n ，n ≥1．非连通图的点连通度为0．若k (G ) ≥k ，则称G 为k -连通图．定义3.2.9（边割集、割边、桥） 设无向图G =<V ,E >为连通图，若有边集E 1⊂E ，使图G 删除了E 1的所有边后，所得的子图是不连通图，而删除了E 1的任何真子集后，所得的子图是连通图，则称E 1是G 的一个边割集．若某个边构成一个边割集，则称该结点为割边（或桥）． 定义3.2.10（连通度） 若G 为无向连通图，则称λ(G )=min{|E 1| ∣E 1是G 的一个边割集}为G 的边连通度．规定：非连通图的边连通度为0．若λ(G ) ≥k ，则称G 为k 边-连通图．定义3.3.1（邻接矩阵） 设G =<V ，E >是一个简单图，其中V ={v 1，v 2，…， v n }，则n 阶方阵A （G ）=（a ij ）称为G 的邻接矩阵．其中各元素⎪⎩⎪⎨⎧==ji v v v v a j i j i ij 不相邻或与相邻与01 定义3.3.2（可达性矩阵） 设G =<V ，E >是一个简单图，|V |=n ,假定G 的结点已编序，即V ={v 1，v 2，…， v n }，定义一个n ⨯n 方阵P =（p ij ）．其中⎪⎩⎪⎨⎧=不存在一条路与从至少存在一条路到从j i j i ij v v v v p 01 则称矩阵P 为图G 的可达性矩阵．最短路径的数学模型——给定一个网络N （有向或无向赋权图），u 0与v 0是N 中指点的两个顶点，在N 中找一条从u 0到v 0且权最小的路．规定N 中的一条路P 的权w (P )称为p 的长度．若N 中存在从u 到v 的路，则将N 中从u 到v 且权最小的路称为u 到v 的最短路，其长度称为u 到v 的距离，记为d N （u ,v ）．二、定理定理3.1.1（握手定理） 设G 是一个图，其结点集合为V ，边集合为E ，则∑∈=V v E v ||2)deg(定理3.1.2 图中次数为奇数的结点有偶数个．定理3.1.3 在任何有向图中，所有的入度之和等于所有结点的出度之和．定理3.1.4 有n 个结点的无向完全图K n 的边数为n (n -1)/2．定理3.1.5 在具有n 个结点的简单图G =<V , E >中，若从结点v j 到结点v k 有一条路，则从结点v j 到结点v k 有一条长度不大于n -1的路．定理3.1.5推论在一个具有n个结点的图G=<V, E>中，如果从结点v j到结点v k有一条路，则从结点v j到结点v k必有一条长度小于n的通路．定理3.1.6在具有n个结点的图G=<V,E>中，如果经v有一条回路，则经v有一条长度不超过n的回路．定理3.1.6推论在具有n个结点的图G=<V,E>中，如果经v有一条简单回路，则经v 有一条长度不超过n的基本回路．定理3.2.1一个有向图是强连通的，当且仅当G中有一个回路，其至少包含每个结点一次．定理3.2.2在有向图G=〈V，E〉中，G的每一结点都在也只在一个强（弱）分图中．定理3.2.3在有向图G=〈V，E〉中，G的每一结点都处在一个或一个以上的单向分图中．定理3.2.4（Whitney）对于任何一个图G，有k(G) ≤λ (G) ≤δ(G)其中k(G)、λ (G)、δ(G)分别为G的点连通度、边连通度和最小度．定理3.2.5一个连通无向图G中的结点v是割点的充分必要条件是存在两个结点u与w，使得结点u与w的每一条路都通过v．三、方法1．两图同构的必要条件：（1）结点数相等；（2）边数相等；（3）度数相同的结点数相等．2．邻接矩阵运算特征（1）图G=<V,E>的邻接矩阵不唯一，而与V中的元素标定次序有关．对V中各元素不同的标定次序可得到同一图G的不同邻接矩阵．但这些邻接矩阵经过适当地交换行和列的次序，就从一个邻接矩阵变到另一个邻接矩阵．根据不同邻接矩阵所作的有向图都是同构的．因此，可选V元素的任一种标定次序所得出的邻接矩阵．（2）当有向线图代表关系时，邻接矩阵就可看作是一种关系矩阵．有向图是自反的，矩阵的对角线元素全为1．有向图是非自反的，矩阵的对角线元素全为0．有向图是对称的，对所有i和j，矩阵是对称的．有向图是反对称的，对所有i和j，矩阵是以主对角线对称的元素不可能同时为1．（3）零图的邻接矩阵的元素全为零，并称其为零矩阵．（4）图的每一顶点都有自回路而再无其它边时，图的邻接矩阵是单位矩阵．（5）设有向线图G=<V，E>的邻接矩阵是A，则A的逆图的邻接矩阵是A的转置矩阵．3．可达性矩阵的计算方法一般地，可以由图G的邻接矩阵A得到可达性矩阵P．即令B n=A+A2+…+A n，在从B n中将不为0的元素改为1，而为零的元素不变，这样改换的矩阵即为可达性矩阵P．也可以将矩阵A，A2，…，A n分别改为布尔矩阵A，A(2)，…，A(n)，简化计算，故P= A∨A(2)∨…∨A(n)，其中A(i)表示在布尔运算下A的i次方．4．求最短路径的Dijkstra算法步骤（1）置l(u0)=0，对v∈V-{ u0}，l(v)= +∞，S0 ={ u0}，i=0．（2）对每个v∈ N G-Si（u i），用min{ l(v)，l(u i)+ w（u i，v）}代替l(v)．若l(v)取到l(u i)+w（u i，v），则在v旁边记下(u i)．计算min(v∈G- S i ){ l(v)}，并将达到最小值的这个顶点记为u i+1．置S i+1= S i⋃{ u i+1}．（3）若i=|G|-1，则算法停止，否则用置i 为i+1，并转入第（2）步．算法结束时，从u0到v的距离由最终的标号给出l(v)，并且可根据各个顶点旁边的（u i）追回出从u0到v的最短路径．若为求某个特定的顶点v时，则可以在u j= v时使算法停止即求得结果．。