图的基本概念
从逻辑结构上讲，图是一种典型的非线性结构。
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为 G（V , E） ,其中, G表示—个图，V是图G中顶点的集合，E是图G中边的集合。其中：
顶点集合V={x|x属于某个数据对象集}是有穷非空集合
E={（x，y）|x，y属于V&&Path（x，y）}是顶点间关系的有穷集合，也叫做边的集合。
有向边和无向边
若顶点x到y之间的边没有方向则称这条边为无向边（Edge）,用**无序偶对（x,y）**来表示
若顶点x到y之间的边有方向则称这条边为有向边，也称为弧（Arc）。连接顶点x到y的有向边就是弧，x是弧尾，y是弧头，用<x,y>来表示
简单图
在图中，若不存在顶点到自身的边，且同一条边不重复出现则称这样的图为简单图。
如下两个图就不是简单图
有向图和无向图
- 在有向图中，顶点对 < x , y > <x, y><x,y> 是有序的，顶点对 < x , y > <x, y><x,y> 称为顶点 x 到顶点 y 的一条边（弧），< x , y > <x, y> 和 < y , x > 是两条不同的边。
- 在无向图中，顶点对 ( x , y ) 是无序的，顶点对 ( x , y ) 称为顶点 x 和顶点 y 相关联的一条边，这条边没有特定方向，( x , y ) 和 ( y , x ) 是同一条边。
如下图：
完全图
- 在有 n 个顶点的无向图中，若有 n * ( n − 1 ) / 2 条边，即任意两个顶点之间都有直接相连的边，则称此图为无向完全图。
- 在有 n 个顶点的有向图中，若有 n × ( n − 1 ) 条边，即任意两个顶点之间都有双向的边，则称此图为有向完全图。
如下图
稀疏图和稠密图
有很少条边或弧的图称为稀疏图，反之称为稠密图。
邻接顶点：
- 在无向图中，若 ( u , v ) 是图中的一条边，则称 u 和 v 互为邻接顶点，并称边 ( u , v ) 依附于顶点 u 和顶点 v 。
- 在有向图中，若 < u , v > 是图中的一条边，则称顶点 u 邻接到顶点 v，顶点 v 邻接自顶点 u ，并称边 < u , v > 与顶点 u和顶点 v 相关联。
顶点的度：
- 在有向图中，顶点的度等于该顶点的入度与出度之和，顶点的入度是以该顶点为终点的边的条数，顶点的出度是以该顶点为起点的边的条数。
- 在无向图中，顶点的度等于与该顶点相关联的边的条数，同时也等于该顶点的入度和出度。
权
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权( Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网( Network)。
下图就是-一张带权的图，即标志中国四大城市的直线距离的网，此图中的权就是两地的距离。
路径与路径长度：
- 若从顶点 vi 出发有一组边使其可到达顶点 vj ，则称顶点 vi 到顶点 vj的顶点序列为从顶点 vi 到顶点 vj的路径。
- 对于不带权的图，一条路径的长度是指该路径上的边的条数；对于带权的图，一条路径的长度是指该路径上各个边权值的总和。
简单路径与回路
- 若路径上的各个顶点均不相同，则称这样的路径为简单路径。
- 若路径上第一个顶点与最后一个顶点相同，则称这样的路径为回路或环。
子图
- 设图 G = ( V , E ) 和图 G 1 = ( V1 , E1 ) ，若 V1 ⊆ V 且 E1 ⊆ E ，则称 G1 是 G 的子图。
如下图：
连通图和强连通图
- 在无向图中，若从顶点 v1到顶点 v2有路径，则称顶点 v1与顶点 v2 是连通的，如果图中任意一对顶点都是连通的，则称此图为连通图。
- 在有向图中，若每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路，也存在一条从 vj到 vi 的路，则称此图是强连通图。
连通分支
无向图中的极大连通子图称为连通分支，注意：
- 要是子图
- 子图是连通的
- 连通子图含有极大顶点数
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边
例如下图中，图2图3是图1的两个连通分支，但是图四却不是，因为不是极大连通子图
生成树与最小生成树
- 一个连通图的最小连通子图称为该图的生成树，有 n 个顶点的连通图的生成树有 n个顶点和 n − 1条边。
- 最小生成树指的是一个图的生成树中，总权值最小的生成树。
有向树
如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一个有向树
生成森林
一个有向图的生成森林由若干棵有向树组成， 含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧文章来源：https://www.toymoban.com/news/detail-791000.html
文章来源地址https://www.toymoban.com/news/detail-791000.html
到了这里，关于图论相关基本概念的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
