title: 图论基础 author: BbiHH tags:

(原创)

参考自https://www.cnblogs.com/jeavenwong/p/8204271.html 参考自https://oi-wiki.org/graph/ 图论概述

图论（graph theory） 是数学的一个分支，它以 图 为研究的对象。

图论本身是应用数学的一部分，历史上图论曾经被很多数学家各自独立建立过。关于图论的最早文字记载最早出现在欧拉 1736 年的论著中，也就是著名的柯尼斯堡（Konigsberg）问题（七桥问题）。

一个图可以形式定义为一个二元组： G = ( V, E )，其中：

（1）V 是顶点（结点）的有穷集合。

（2）E是连接V中两个不同顶点（顶点对）的边的有限集合。 如果E中的顶点对是有序的，即E中的每条边都是有方向的，则称G为有向图。如果顶点对是无序对，则称G是无向图。

下图是一个有向图，可以描述为：G = (V, E)，其中 V = {v1,v2,v3,v4,v5} E = {,,,,,, }

下图是一个无向图，可描述为：G = (V, E)，其中V = {v1,v2,v3,v4,v5, v6}E = {(v1, v2),(v1, v6),(v2, v5),(v2, v6),(v3,v5),(v3, v4),(v4, v5)}

无向图：每条边都是无向边的图。

有向图：每条边都是有向边的图。

混合图：在一个图中，有些边是有向边，另一些边是无向边，则该图为混合图。

有限图：一个图的点集和边集都是有穷集的图。

零图：边集为空集的图。

平凡图：仅有一个结点而没有边构成的图。

关联：若有ei = (u,v) 且 ei ∈ E 则称 u 是和 v 相关联的。

孤立点：无边关联的点。

自环：若一条边所关联的两个结点重合，则称此边为自环。

邻接：关联于同一条边的两个点 u 和 v 称为邻接的；关联于同一个点的两条边 e1 和 e2 是邻接的（或相邻的）。

1.对于无向图而言，假若顶点v和顶点w 之间存在一条边(v,w) ，则称v 和w是相邻的，顶点v 和w 互为邻接顶点。边(v,w) 和顶点v 和w 相关联。（对于有向图，称为邻接到和邻接自。）

2.对于无向图而言，从顶点v到顶点w的路径指的是一个顶点序列(v = v0v1…vm= w)，其中(vi,vi+1)∈E。路径的长度指的是路径上的边的数目。（对于有向图，也可以定义路径，且路径是有向的。）

3.若路径中的顶点没有重复，称为简单路径。

4.第一个顶点和最后一个顶点相同的路径称为环或回路。

5.在无向图中，如果从顶点v到顶点w有路径，则称顶点v和顶点w是连通的。

6.如果无向图G中任意两个顶点都是连通的，则称图G是连通图。

8.如果一个无向图不是连通图，则其中的每个极大连通子图称为无向图的连通分量。

9.如果有向图G中任意两个顶点间都存在有向路径（对任意两个顶点v和w，既存在v到w的有向路径，也存在w到v的有向路径），则称有向图G是强连通图。

10.其各个极大强连通子图称作它的强连通分量。 如果不考虑有向图中边的方向所得到的无向图是连通图，则有向图称为弱连通图。

11.对于无向图而言，和顶点相关联的边的数目称为顶点的度。

12。对于有向图而言，从顶点出发的边的数目称为顶点的出度，到达该顶点的数目称为顶点的入度。 边上带有权值的有向图或无向图分别称作有向网或无向网。