图

图是由一些点及一些点之间的连线组成的图形。

两点之间不带箭头的连线称为边，带箭头的连线称为弧。

如果一个图由点及边所构成，则称之为无向图(也简称为图)，记为G=(V,E)，式中V，E分别是G的点集合和边集合。一条连结点v_i，v_j的边记为[v_i,v_j](或[v_j,v_i] )。

如果一个图D由点及弧所构成，则称为有向图，记为D=(V,A)，式中V，A分别表示D的点集合和弧集合。一条方向是从v_i指向v_j的弧，记为(v_i,v_j)。

无向图G=(V,E)

若边e=[u,v]∈E，则称u，v是e的端点，也称u，v是相邻的。称e是点u(及点v)的关联边。

若图G中，某个边e的两个端点相同，则称e是环。

若两个点之间有多于一条的边，称这些边为多重边(或平行边)。

一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图；任意两顶点都相临的简单图称为完全图。

以点v为端点的边的个数称为v的度，记为d_G(v)或d(v)。（环在计算度时算作两次）。

称度为1的点为悬挂点，悬挂点的关连边称为悬挂边，

度为零的点称为孤立点。

给定一个点、边交错序列(v_i1, e_i1, v_i2, …, v_ik-1, e_ik-1, v_ik)。

如果满足e_it = [v_it, v_it+1] (t=1，2，…，k-1)，则称为一条联结v _i1,和v_ik,的链，记为(v_i1, v_i2, …, v_ik-1, v_ik)。称点为链的中间点。

链中，若v _i1 = v_ik，则称之为一个圈，记为(v_i1, v_i2, …, v_ik-1, v_i1)。

没有重复顶点的链称之为初等链；没有重复顶点的圈称之为初等圈。若链(圈)中含的边均不相同，则称之为简单链。以后说到链(圈)，除非特别交代，均指初等链(圈)。

图G中，若任何两点之间至少有一条链，则称G是连通图，否则称为不连通图。

若G是不连通图，它的每个连通的部分称为G的一个连通分图(也简称分图，连通支)。

给了一个图G=(V, E)，如果G’=(V’, E’)，使V=V’及E’∈E，则称G’是G的一个支撑子图。

设v∈V(G)，用G-v表示从图G中去掉点v及v的关联边后得到的一个图。

有向图D=(V,A)

从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记之为G(D)。

给定D中的一条弧a=(u，v)，称u为a的始点，v为a的终点，称弧a是从u指向v的。

有向图中，与顶点v出关联的边的数目称为出度，记作d⁺(v)；与顶点v入关联的边的数目称为入度，记作d^–(v)。

设(v_i1, a_i1, v_i2, …, v_ik-1, a_ik-1, v_ik)是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。类似定义圈和初等链(圈)。

如果(v_i1, a_i1, v_i2, …, v_ik-1, a_ik-1, v_ik)是D中的一条链，并且对t=1, 2, …, k-1，均有a_it,=(v_it, v_it+1)，称之为从v_it到v_it+1的一条路。若路的第一个点和最后一点相同，则称之为回路。类似定义初等路(回路)。

几个基本定理

1. 对图G=(V，E)，有∑d(v)=2|E|。
2. 度为奇数的顶点(奇点)有偶数个。
3. 对有向图，∑d⁺(v)=∑d^–(v)=|E|。