Name: Password: Sign in
离散数学 · 图 中的文章
  • [Lecture 1] 图和图模型
  • [Lecture 2] 图的表示与同构
  • [Lecture 3] 连通性
  • 本文在 署名-非商业性使用-相同方式共享 3.0 版权协议下发布, 转载请注明出自 kyleslight.net

    [Lecture 2] 图的表示与同构

    1 图的表示

    1.1 邻接表

    邻接表规定顶点与相邻的顶点。

    例如对于简单图:

    可以构建邻接表:

    Vertice Approximal Point
    a b,c,e
    b a
    c a,d,e
    d c,e
    e a,c,d

    对于有向图:

    Start End
    a b,c,d,e
    b b,d
    c a,c,e
    d
    e b,c,d

    1.2 邻接矩阵

    G=(V,E) 为简单图,|V|=nG 的邻接矩阵 A=[aij] (或 AG)是 n×n 的 0-1 矩阵,满足:

    aij={1:(vi,vj)E0:(vi,vj)E

    邻接矩阵可以表示带环与含有多重边的图,自成环时只需让 aii 加 1 即可,含有多重边只需让 aijaji 加 1 即可

    简单图是对称的;有向图不一定对称

    邻接表邻接矩阵 的取舍:

    • 当一幅图较为 稀疏 使用邻接表可以节省更多的空间;例如每个点的度 c 都远小于顶点的个数 n
    • 稠密 时,例如边数超过所有可能边数的一半,那么邻接矩阵更适合(考虑获得某条边是否存在的复杂度,邻接矩阵为 1,邻接表为 |V|

    1.3 关联矩阵

    G=(V,E) 是无向图,v1,v2...vn 是顶点,e1,e2...em 是边,那么 VE 顺序的关联矩阵是 n×m 矩阵 M=[mij],其中:

    mij={1:vkV((vi,vk)=ej)0:vkV((vi,vk)ej)

    例如对于无向图:

    可以作关联矩阵:

    2 图同构

    简单图的 同构(isomorphism)G1=(V1,E1)G2=(V2,E2) 是简单图,若存在 一对一映上 的从 V1V2 的函数 f,且 f 具有性质: 对于所有的 vivjvivjG1 中相邻当且仅当 f(v1)f(v2)G2 中相邻,那么我们说 G1G2 是同构的,函数 f 称为 同构

    一个简单的例子来说明同构关系,判断下图中 GH 是否同构:

    通过观察(根据度与相邻关系)我们知道 deg(u1)=2 且相邻的顶点度为 3,H 中有 v4v6 有相同的条件,因而假设 f(u1)=v4

    类似的道理我们可以构建几条映射:f(u2)=v3f(u3)=v6f(u4)=v5f(u5)=v1f(u6)=v2,为了保证 f 满足边,我们检查邻接矩阵:

    AG=AH,所以 f 是保持边的,因而 f 是一个同构,即 GH 同构;

    注意到,如果 AGAH 那么 f 不是同构,但 GH 仍然有可能是同构的

    Copyright (c) 2014-2016 Kyles Light.
    Powered by Tornado.
    鄂 ICP 备 15003296 号