图论是近数十年来得到蓬勃发展的一个数学分支，它的 理论与方法在许多领域中得到广泛的应用并取得了丰硕的 成果成为运筹学一个重要分支。
线性规划、整数规划、运输问题等等，有时也可以用图 论的方法来构造模型并求解，而且由于图的结构的直观性， 更有助于我们分析问题和描述问题，何况有些研究对象， 如交通网，它本身就是一个大网络，用图论的方法研究更 方便。
数学描述： （1）G={V,E}，V={v1,v2, ···vn},E={e1,e2, ···en}
（2）G={(eij,(vi,vj))|i,j=1···n}
根据边有没有方向，将图分为无向图和有向图，下面分别讲解：
1.1.1 无向图
一、无向图定义
v1 v2
v5 v3
1．无向图
v4
设V是一个有n个顶点的非空集合，V={v1 ,v2 ,…,vn },E是
v1
v5
v3 v2
v4
v1
v5
1.1.1 无向图
v3
v2
二、无向图术语
v4
平简行单边图（：多图重中边无）平：行两边边有一样的端点，如e15和e51 完备图：图中任意两个端点之间有且仅有一条边 链：两个端点之间的连接路径 一个链的起始端点不为同一个称为开链，否则为闭链（圈）
简单链：一个链中无重复的边。
图的可达性（有向图）：若图G中从顶点u 到v之 间存在单向路径，则称u可达v。
强连通图：若图G内任两点之间相互可达，则称 图G为强连通图。
v1 v2
v1
v5
v4
v6
e3
e1 e4
e6
v3
v3
v2 v5
e5
e7 v4
e8
1.1.3 其它术语
