图论的概述
图论(Graph Theory)是离散数学的一个分支，是一门研究图(Graph)的学问。
图是用来对对象之间的成对关系建模的数学结构，由”节点”或”顶点”(Vertex，复数为Vertices）以及连接这些顶点的”边”（Edge）组成。
图的顶点集合不能为空，但边的集合可以为空。
图的类型
图的分类：无权图和有权图，连接节点与节点的边是否有数值与之对应，有的话就是有权图，否则就是无权图。
图的表达形式
- 连接矩阵
邻接矩阵：1 表示相连接，0 表示不相连。 - 邻接表
邻接表：只表达和顶点相连接的顶点信息。
邻接表适合表示稀疏图 (Sparse Graph)，邻接矩阵适合表示稠密图 (Dense Graph)。
图的特性
图的连通性：在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点 i 到顶点 j 有路径相连（当然从j到i也一定有路径），则称 i 和 j 是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图的连通性是图的基本性质。
连通图：无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。
判断图是否是连通的，可以通过深度优先遍历的方法判断。 具体实现为：在图中选定任一一个顶点，对该顶点进行深度优先遍历，如果在这个遍历过程中所有的顶点都被遍历到，则该图为连通；反之，若存在没有被遍历到的顶点，则说明该图是非连通的。
图的其他特性
完全图：完全是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。
自环边：一条边的起点终点是一个点。
平行边：两个顶点之间存在多条边相连接。
(完)