图的基本概念
定义：一个图（G）定义为G=V,E，其中，V是顶点的非空有限集合，记为V(G)；E是边的集合，记为E（G），其元素是图的边。将顶点集合为空的图称为空图。其形式化定义为G=V，E。
例如：图下。其中V={北京，济南，上海，南京，郑州，西安，成都，武汉}，E={北京-郑州，北京-济南…}
一、边是什么？
边（弧）
表示两个顶点v和w之间存在一个关系，用顶点偶对v,w表示。例如：北京到上海之间有高铁线路，表示为北京，上海。
通常根据图的顶点偶对将图分为有向图和无向图。
1，有向图：若图G的关系集合E（G）中，用顶点偶对v,w的v，w之间是有序的，则称图G为有向图。
在有向图中，若v,w∈E(G)中，则表示从顶点v到顶点w有一条弧，其中,v称为弧尾或起点，w称为弧头或终点。
2，无向图：若图G的关系集合E(G)中，顶点偶对v,w的v,w之间是无序的，则称图G为无向图。
在无向图中，若v,w∈E(G)，则必有w,v∈E(G)，即E（G）是对称的，则无序对v,w表示v和w之间的一条边。v,w和w,v代表的是同一条边。
二、完全无向图
1.完全无向图定义
对于无向图，给定顶点的情况下，边的数量是有范围的，若图中顶点数为n，用e表示边的数目，则e∈[0，n(n-1)/2]。具有n(n-1)/2条边的无向图称为完全无向图。完全无向图的直观解释是图中任意两个不同的顶点间都有一条边。
2，完全有向图
对于有向图，给定顶点的情况下，边的数量是有限范围的。若图中顶点数为n，用e表示弧的数目，则e∈[0，n(n-1)]，具有n(n-1)条弧的有向图称为完全有向图。完全有向图的直观解释是图中任意两个不同的顶点间都有一条弧（双向的边）。
注意
什么是简单图？不存在平行边或闭环的图是简单图。
三，稀疏图和稠密图
一般认为边enlogn时是稀疏图；否则是稠密图。
四，权
权表示从一个顶点到另一个顶点的距离或耗费。如果一个图中，每个边或弧都附加一个权值，就称为带权图，也称为网。
五，子图和生成子图
设有图G=(V,E)，G‘=（V’，E‘）,若V’V并且E’E，则称图G’为G的子图。
若V’=V并且E’E，则称图G’为G的一个生成子图。
六，顶点的邻接
对于无向图G=(V,E)，若边v,w∈E，则称顶点v和w互为邻接点，即v和w相邻接。
对于有向图G=(V，E)，若有向图弧v,w∈E，则称顶点v邻接到顶点w；反之一样，是一种相互关联的关系。
七，顶点的度，入度，出度
对于无向图G=（V，E），任意vi∈V,图G中依附Vi的边的数目称为顶点Vi的度，记为TD(Vi)。
在无向图中，所有顶点度的和是图中边数的2倍每条边会在两端各自计算一次。
对于有向图G=（V,E），对于任意Vi∈V，图G中以Vi作为起点的有向弧的数目称为Vi的出度，记为OD(Vi)；反之称为入度，记为ID(Vi)。
顶点Vi的出度和入度之和称为Vi的度，记为TD(Vi)。
即TD(Vi)=OD(Vi)+ID(Vi)。
八，路径，路径长度和回路
对于无向图G=（V，E），若从顶点Vi经过若干条边能到达Vi，则称顶点Vi和Vj是连通的，称为有路径。
对于有向图而言，则称为有向路径，路径上的边或弧称为路径长度。
起点和终点连接称为回路。