一、导论
数学史上的图论可以追溯到柯尼斯堡七桥问题（大约1730年代）。它提问是否可以在以下限制条件下遍历柯尼斯堡市的七座桥梁。欧拉于1736年研究并解决了此问题，他把问题归结为如“一笔画”问题，发表名为《柯尼斯堡七桥》的论文，同时开创了数学一个新分支---图论。
二、图的应用
在计算机科学中，图是最灵活的数据结构之一，很多问题都可以使用图模型进行建模求解。例如：生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。当图的边具有已分配给它们的价值/费用时，我们说我们有一个加权图。加权图的应用场景非常多，比如：
（1）航线交通
节点/顶点 = 机场
边=两个机场之间的直接航班
权重=两个机场之间的里程数
（2）GPS导航
节点=道路交点
边=道路
权重=两个路口之间距离所需时间
（3）网络路由
节点=服务器
边=数据链路
权重=连接速度
三、图的定义
我们先从最简单的定义入手，了解图的最基本表示方法，后续小编会陆陆续续分析并用代码实现图的搜索算法、最短路径算法、哈密顿回路、图着色等等。
其实，图的结构不复杂，由顶点集V和边集E组成，因此图就可以表示为G=(V,E)。图分为有向图以及无向图。
【注意：线性表可以是空表，树可以是空树，图不可以是空图，图可以没有边，但是至少要有一个顶点】
1、有向图
若E是有向边（简称弧）的有限集合时，则G为有向图。弧是顶点的有序对，记为<v,w>，其中 v，w 是顶点，v 是弧尾，w 是弧头。称为从顶点v到顶点w的弧。
图1
对于上图1的有向图，对应的顶点集合和边集合如下：
V（G）= {V1，V2，V3，V4，V5，V6}
E（G）= {<V2，V1>，<V3，V1>，<V4，V3>，<V4，V2>，<V3，V5>，<V5，V3>，<V2，V5>，<V6，V5>，<V2，V6>，<V6，V2>}
2、无向图
如果一个图结构中，所有的边都没有方向性，那么这种图便称为无向图。典型的无向图，如图二所示。由于无向图中的边没有方向性，这样我们在表示边的时候对两个顶点的顺序没有要求。例如顶点VI和顶点V5之间的边，可以表示为(V2,V6),也可以表示为(V6,V2)。
图2
对于图二无向图，对应的顶点集合和边集合如下：
V（G）= {V1，V2，V3，V4，V5，V6}
E（G）= {(V1,V2)，(V1，V3)，(V2，V6)，(V2，V5)，(V2，V4)，(V4，V3)，(V3，V5)，(V5，V6)}
3、顶点的度
顶点的度为以该顶点为一个端点的边的数目。
对于无向图，顶点的边数为度，度数之和是顶点边数的两倍。如上图2所示：顶点V5的度为3，而V6的度为2。
对于有向图，入度是以顶点为终点，出度相反。有向图的全部顶点入度之和等于出度之和且等于边数。顶点的度等于入度与出度之和。如上图1所示：顶点V5的入度为3，出度为1。因此，顶点V5的总度为4。
注意：入度与出度是针对有向图来说的。
4、子图
假设有两个图G= (V，{E})和G'= (V'，{E'})，如果V'是V的子集，且E'是E的子集，则称G'为G的子图。如下图3中的G2、G3、G4的图均为左侧无向图G1的子图。
图3
5、无向完全图
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。
6、有向完全图
如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n (n-1) 条边。
7、路径和路径的长度
从顶点v到顶点v'的路径是一个顶点序列。路径的长度是路径上的边或弧的数目。有向图的路径也是有向的。
8、回路或环
第一个顶点到最后一个顶点相同的路径称为回路或环。
9、简单路径、简单回路或简单环
序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
10、连通、连通图和连通分量
在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。 如果对于图中任意两个顶点vi、vj ∈G，vi，和vj都是连通的，则称G是连通图。 下图4的左图，它的顶点A到顶点B、 C、 D都是连通的，但显然顶点A与顶点E或F就无路径，因此不能算是连通图。而右图，顶点A、 B、 C、D相互都是连通的，所以它本身是连通图。
图4
无向图中的极大连通子图称为连通分量。注意连通分量的概念，它强调:
① 要是子图；
② 子图要是连通的；
③ 连通子图含有极大顶点数；
④ 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
11、强连通图和强分量
在有向图G中，如果对于每一对vi，vj属于E，vi不等于vj，从vi到vj和vj 到vi都有路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。
简单介绍了下图的一些基本性质，有关图的存储结构及其代码实现，小编下次进行分享。
网友评论