null图论概述图论概述图论(Graph Theory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。如，通信系统、交通运输系统、信息网络系统、生产工艺
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
以及军事后勤保障系统等的问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
常用图论模型来描述。第七章 图论与网络规划网络规划概述网络规划概述网络规划(Network Programming )是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。七桥问题七桥问题B七桥问题图形原 理 及 方 法 原 理 及 方 法 七桥问题是图论中的著名问题。1736年，Euler巧妙
地将此问题化为图的不重复一笔画问题，并证明了
该问题不存在肯定回答。原因在于该图形有顶点连
接奇数条边。§7、1 图的基本概念§7、1 图的基本概念一个图(Graph) 定义为二元有序组
G=(V(G),E(G))，
V(G)是图的顶点集合，E(G)是于的边集合。记图的端点图的端点设G是一个图(Graph)
G=(V(G),E(G))，则称e连接u和v，称u和v是e的端点。若称端点u，v与边e是关联的，
称两个顶点u，v是邻接的。平面图平面图一个图称为平面图，如它可以画在平面上，使得边与边仅在顶
点相交。下图就是一个平面图。基本概念基本概念端点重合为一点的边称为环。
连接同一对顶点的多条边称为多重边。
在下图中，e5 是一个环，
e1 与e2 是多重边。 简单图和多重图简单图简单图一个图称为简单图，如果它既没有环也没有多重边。
下图是简单图。
本书只限于讨论有限简单图，即顶点集与边集都是有限集的简单图。u1u2u3u4e1e2e6e3e5e4只有一个顶点的图称为平凡图；边集是空集的图称为空图。邻接矩阵邻接矩阵设G是一个图， G=(V(G),E(G))
定义图G的邻接矩阵A(G) =(aij)
为m×m矩阵, aij是顶点vi与边vj相邻接的边数。其中关联矩阵关联矩阵
设G是一个图， G=(V(G),E(G))定义图G的关联矩阵M=(mij)为m×n矩阵；其中mij是顶点vi与边ej相关联的次数，
取值可能为0、1、2。注：注：图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机中。关联矩阵和邻接矩阵统称图的矩阵表示。顶点的度顶点的度设G是一个图， G=(V(G),E(G))
定义图G的顶点v的度为与顶点v相关联的边数，记作d(v)。 例称度为奇数的顶点为奇点；称度为偶数的顶点为偶点。例例22222224+3+3+4=14=2×7关联矩阵的性质关联矩阵的性质图G的关联矩阵的每行元素之和等于相
应顶点的度；每列元素之和等于2。因此，图G的关联矩阵M所有元素之和
既等于所有顶点的度之和，
又等于边数的2倍。定理 设G是一个图，则推论 图中奇点的数目为偶数。完全图Kn完全图Kn完全图是每一对不同顶点都恰有一边的简单图；
具有n个顶点的完全图记为Kn.K5二分图二分图二分图是一个简单图，其顶点集合可分划成两个子集X与Y，使得每条边的一个端点在X，另一个端点在Y; (X,Y)也称为图的二分划。x1x2x3y1y2y3完全二分图完全二分图完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连；记为K m,n,
其中K 3,3特殊图例特殊图例K5K 3,3都是极小的非平面图子图 子图 称图H是图G的子图，图G及其支撑子图称H是G的支撑子图，如果称H是G的真子图，若如果记为顶点导出子图顶点导出子图设W是图G的一个非空顶点子集,以W为顶点集，以二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为G[W]。导出子图G[V- W]记为G-W，它是从G中删除W中顶点 以及与这些顶点相关联的边所得到的子图。边导出子图边导出子图设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为G[F]。
记G-F表示以E(G)\F为边集的G的支撑子图，它是从G中删除F中的边所得到的子图。
如F={ e }，则记 。
子图图例子图图例v2v1v3v4v5e1e3e2Gv1v2v3v4v5e2G的支撑子图
G-{ e1 , e 2 , e 3}子图图例2子图图例2v2v2v3v4e2G-{v 1,v 5 }v1v2v5G[v 1,v 2 ,v 5 ]v1v3v4e1e3e2G [ e1 , e 2 , e 3]v1v2v3v4v5e1e3e2G图的并与交图的并与交设G1与G2都是图G的子图；图径图径顶点vk叫W的终点，
顶点v0 称为w的起点，
整数k称为W的长度。
在简单图中，图径可由顶点序列表示。图G的一个有限的点边交错序列称为从v0到vk的图径；其中vi与v i+1是边ei的顶点 。路、链路、链如果图径W的边不相同，则称W为一条链，如果W顶点互不相同，则称W是一条路。链长是W中边的个数k。记路长uvwxyabdefgh链：w c x d y h w b v g y
路：x c w h y e u a vc圈(回路)圈(回路)如果径W的起点和终点相同且有正长度，则称它是一个闭径；
如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。
称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。uvwxyabdefgh圈：uavbwhyeuc定理一个图是二分图当且仅当图中不存在奇圈。定理定理一个图是二分图当且仅当图中不存在奇圈。Euler圈Euler圈Euler圈是指过所有边一次且恰好一次的闭径。
Euler链是指过所有边一次且恰好一次的链。uvwxyabdefghEuler链:y d x c w h e u a v f y g v b wc图例图例下例给出了一个图的径，链和路。uvwxyabcdefgh径：u a v f y f v g y h w b v链：w c x d y h w b v g y路：x c w h y e u a v圈：u a v b w h y e uEuler链:y d x c w h e u a v f y g v b wEuler图定理Euler图定理定理2 设G是连通圈，则G是Euler图的充要条件是G没有奇次数的顶点。
推论1 设G是一个连通图，则G有Euler链当且仅当G最多有两个奇数次数的顶点。
浙公网安备 33021202002483