[图](1)图的定义

图(Graph)的定义

  • 结点和联结结点的边所构成的离散结构
  • 记作G=<V,E>
  • 结点vertex集V:非空集合
  • 边edge集E:多重集合 (集合中可能存在相同元素,元素附带一个重数的属性)
  • 边集是多重集合表示图可以有多个相同的边(所谓相同边就是有相同联结的结点)
  • 有向边:用结点的二元有序组表示

    • 第一分量称作起点,第二分量称作终点
  • 无向边:用结点的两元素多重集表示

    • 无向边可以是多重集意味着允许无向环(loop)
    • 无向边的端点称作邻接结点

image-20210121193049894

上图所示的两个图中,他们的V是一样的,代表他们的结点是相同的,但是其E是不一样,就是他们的边集是不一样的,在左边的无向图中,他有四条无向边,可以看到有两个ac,有一个c到自身的环,在右边的有向图中,就清晰很多了,其中<c,c>的有序组是没有问题的。

图的基本概念

对于图G=<V,E>

  • 有限图:V,E都是有限集,否则称为无限图
  • 重边:E中重数大于1的边称为重边(平行边)
  • 重图:边集E中至少有一个元素重数大于1(也称若图中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则称为多重图)
  • 单图:每条边的重数都等于一
  • 简单图:没有环也没有重边的图
  • 无向图中,关联一对顶点的无向边如果多于1条,则称这些边为平行边,平行边的条数称为重数。在有向图中,关联一对顶点的有向边如果多于1条,并且这些边的始点与终点相同(也就是它们的的方向相同),称这些边为平行边。含平行边的图称为多重图,既不含平行边也不包含自环的图称为简单图

  • 完全图:任何两个不同节点间都有边关联的简单图,记作Kn

image-20210122021432833

  • 孤立结点:不是任何边的端点的结点
  • 零图:仅有孤立结点构成的图(E=空,边集为空的图)
  • 赋权图:在边或者结点上附加了权值的图(G=<V,E,f,g>)

    • 结点权函数:f:V->W
    • 边权函数:g:E->W
    • W可以是任何集合,常为实数的子集
    • 通常用于解决现实生活中较为复杂的问题
  • 普通的图研究结点和边之间的拓扑关系

    • 如:邻接,连通,通路,划分等性质
  • 赋权图给普通图附加了数量关系

    • 研究距离,成本,代价,规模等性质

image-20210122022154113

结点的度(degree)

端点v的d(v)定义为关联端点v的边的数目

有向图中,边是有方向的,度分为出度(out-degree)入度(in-degree)

  • 出度d+(v)是端点v作为有向边起点的数目 [从该结点出发有多少条出发向其他结点的边]
  • 入度d-(v)是端点v作为有向边终点的数目 [从结点来看有多少条边连接该结点]
  • 有向图中度d(v)=d+(v)+d-(v)

image-20210122023800415

image-20210122024353388

度的性质

  1. 度不是一个随便的自然数,由于边的存在,每条边正好关联了两个顶点,如果把所有的边加起来,必然是一个偶数,而且是边数目的两度
  2. 而在有向图中,出度的总和等于入度的总和
  3. 奇数度的结点必为偶数个(反证法:假设奇数度的顶点个数为奇数的话,那么其度数的总和也为奇数,而偶数度的结点不关其是奇数还是偶数,度的总和也为奇数,这与性质一相矛盾)
  4. 自然数序列(a1,a2,...an)是某个图度的序列,当且仅当序列中所有数的总和为偶数
  5. 一度的顶点称为悬挂点(pendant node)

正则图

所有顶点的度均相同的图称为正则图,按照顶点的度数称作k-正则图

image-20210122025507077

第一个图为三正则图(每个顶点的度都为3)

第二个图为二正则图(每个顶点的度都为2)

第三个图为5正则图(每个顶点的度都为5),同时他也是个完全图,可以知道,n个顶点的完全图它必然是一个Kn-1的正则图,对于K5来说,它就是一个4正则图

子图(subgraph)

image-20210122025826701

image-20210122025849368

子图是通过子集的关系来定义的

如上所示,红色的和蓝色的,其结点集(V)是相等的,蓝色有5条边,而红色有3条边,同时这3条边是蓝色的子集,所以称作红色为蓝色的子图

而红色与绿色,虽然他们的结点集(V)是相等的,但是他们的边集互不为子集(绿色的E不包含红色的E,红色的E也不包含绿色的E),则它们互不为对方的子图

如果G1!=G2,则G1是G2的真子图

生成子图

如果G1是G2的子图,且V1等于V2的话,那么G1就称之为G2的生成子图,所谓生成就是在G1中只需要添加若干条边,不需要添加结点,G1就能等于G2的话,就称作其的生成子图

如上:红色是蓝色的生成子图而绿色不是蓝色的生成子图。

总结子图概念:  

子图:从原图中删去一些点或删去一些线或既删去一些点又删去一些线,剩下的部分(当然必须仍然是图)。允许两种极端情况:什么都不删;删去所有点和所有线。

真子图:同“子图”,但不允许什么都不删。

生成子图:同“子图”,但只允许删去线,不允许删去点。

补图

image-20210122031629162

image-20210122031638600

蓝色为一个完全图,K5,红色和绿色的图的边集交集为空,它们若叠在一起,则是等于蓝色,是一个完全图,则称它们互为补图

图的同构iosmorphic

image-20210122031944823

先决条件:它们所包含的边数和顶点数要相等

如果可以将V1中所有的结点一一对应的置换为V2中的 结点名 后得到的图等于G2

image-20210122032206621

如上是两个不同的图,但是若将其结点改变以下位置,就能等同于对方,则称他们为同构

简单图的拓扑性质

拟路径(pseudi parh)

image-20210122033047050

先决条件,在拟路径中,其边的左右必须是以它相连的两个端点

路径

如果拟路径中的边各不相同,称作路径,也就是说,只要是边各不相同的拟路径,就是路径

通路

如果路径中的顶点各不相同,称作通路

闭路径

如果在路径中,第一个端点和最后一个端点相同的话,就称作闭路径

回路

如果头尾两顶点相同的通路,就称作回路,在回路中,除了第一个和最后一个之外,不允许包含相同的边和顶点

路径和通路的性质

路径和通路的定理

在有n个顶点的图G(简单图)中,如果有顶点u到v的拟路径,那么u到v必有路径,并且必有长度不大于n-1的通路

闭路径和回路定理

在有n个顶点的图G中,如果有顶点v到v的闭路径,那么必定有一条从v到v长度不大于n的回路

图的连通性

u可达v(accessible)

u=v,或者存在一条u到v的路径

连通的无向图:无向图中任意两个顶点都是可达的

image-20210122041852858

强连通的有向图:在有向图中,任意两个顶点都是相互可达的,所谓相互可达就是从u可以到v,从v也可以到u,不一定需要有双向的边,如下所示:

image-20210122041955764

单向连通的有向图:任意两个顶点,至少从一个顶点到另一个顶点是可达的

image-20210122042227709

弱连通的有向图:将有向图看作无向图时是连通的,弱两天即使不是单向连通也不是强连通

image-20210122042307294

连通分支

图G的连通子图G‘ ,而且G’ 不是任何其他连通子图的真子图(最大性)

image-20210122042438178

本文链接:

https://nullcode.fun/121.html
1 + 6 =
1 评论
    HuhuChrome 88Windows 10
    1月23日 回复

    123566654466