首先是基本的一些概念，上个图先：图的定义 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V(vertex)是图G中顶点 首先是基本的
首先是基本的一些概念，上个图先：
图的定义
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V(vertex)是图G中顶点的集合，E(edge)是图G中边的集合。
有向边：若从顶点vi到vj的边有方向，则称这条边为有向边。也称为弧(Arc)。用有序偶来表示，vi称为弧尾（Tail）,vj称为弧头（Head）。顶点：一个个的数据元素，就像树中的数据元素叫结点。顶点的集合：有穷非空集合，我大天朝是这么强调的边的集合：可以为空
有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。图7-2-3就是啦
无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对(vi,vj)来表示。
无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）。图7-2-2就是啦
简单图：在图中若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。
完全有向图：在有向图中，任意两个顶点之间都存在方向互为相反的两条弧，则称该图为完全有向图。含有n个顶点的完全有向图就有n*(n-1)条边。
完全无向图：在无向图中，如果任意两个顶点之间都存在边，则称该图为完全无向图。含有n个顶点的完全无向图就有
有很少条边或弧的图称为稀疏图，反之称为稠密图。
权值：与图的边或弧相关的数。
网：带权的图。
子图：假设两个图G=(V,{E})和G'=(V',{E'})，如果集合V'⊆V，且集合E'⊆E，则称G'是G的子图。
图的顶点与边间关系
- 对于无向图G=(V,{E})，如果（v,v'）∈ E，则：
- 顶点 v 和 v' 互为邻接点，相邻接。
- 边（v,v'）依附于顶点 v 和 v' ，或者说相关联
- 顶点v的度（Degree）是和v相关联的边的数目，记作：TD(v)
- 而边数就是各个顶点度数之和的一半：
- 对于有向图，G=(V,{E})，如果∈ E，则：
- 顶点v邻接到顶点v'，顶点v'邻接自顶点v。
- 弧与顶点v和v'相关联。
- 顶点v的入度（InDegree）：以顶点v为头的弧的数目，记作：ID(v)
- 顶点v的出度（OutDegree）：以顶点v为尾的弧的数目，记作：OD(v)
- 顶点v的度（InDegree）：TD(v)=ID(v)+OD(v)，：
- 图G=(V,{E})中从顶点v到v'的路径（Path）是一个顶点序列（v=vᵢ,₀，vᵢ,₁，vᵢ,ⱼ=v' ），其中（vᵢ₋₁，vᵢ,ⱼ）∈ E，1<=j<=m，路径长度是路径上的边或弧的数目。
- 路径中第一个顶点到最后一个顶点相同的路径称为环或回路。 序列顶点中不存在重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点，其余顶点重复出现的回路，也称称为简单回路，也称简单环。
连通图的相关术语
- 在无向图G中，如果顶点v和v'是有路径的，则称v和v'是连通的，不是移动的，也不是电信的。
- 若对于图中任意两个顶点vᵢ、vⱼ∈E，vᵢ和vⱼ都是连通的，则称G是连通图（connected graph）
- 无向图中的极大连通子图称为连通分量。它强调：
- 要是子图
- 子图要是连通的
- 连通子图含有极大顶点数
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边
- 相对的在有向图G中，若对于每一对vᵢ、vⱼ∈E、vᵢ!=vⱼ，从vᵢ到vⱼ，vⱼ到vᵢ都存在路径，则称G是强连通图。
- 有向图中的极大强连通子图称作有向图的强连通分量。
- 连通图的生成树：是一个极小的连通子图，它包含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。若一个图有n个顶点和小于n-1条边，则是非连通图，若它多余n-1条边，必定构成一个环；不过有n-1条边并不一定是生成树。
- 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一颗有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。