第十章图与网络优化,图论概述,图论(GraphTheory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。,如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。,网络规划概述,网络规划(NetworkProgramming)是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。,七桥问题,七桥问题图形,原理及方法,七桥问题是图论中的著名问题。1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答。原因在于该图形有顶点连接奇数条边。,10.1图的基本概念,一个图(Graph)定义为三元有序组V(G)是图的顶点集合E(G)是图的边集合,记,是关联函数,图的端点,设G是一个图(Graph)G=(V(G),E(G)，,则称e连接u和v，称u和v是e的端点。,若,称端点u，v与边e是关联的，称两个顶点u，v是邻接的。,设G是一个图，,图的几何实现,一个图可用一个几何图形表示,称为图的几何实现，其中每个顶点用点表示，每条边用
