类似的问题：一笔画问题图的一笔画： 可一笔画 不可一笔画字的一笔画：如“中、日、口、串”等可一笔画 而：“田、目”等不能一笔画图论的应用范围：1、中国邮路问题： 邮递员如何选择适当的投递路线，使每条街道至 少走过一次且所走的总路程最短？2、

支撑树最小支撑树【例】今有煤气站A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。EIA 3.52C24G51

例如：上图是3-正则图，且可以1-因子分解，但不存在Hamilton圈。定理9 若3-正则图有割边，则不可1-因子分解。 证明 若3-正则图G可1-因子分解，因去掉G的不含割边的1-因子 后，图中每个点均为2度，从而每条边均在回路中，特别地

v1v4v5v1P (G1 ) 1v2P (G ) 1v3v2v4v5v3删除v3后G2v1删除v1,v3后G3v4v5v1v4v5v2P (G 2 ) 2v3v2v3 P (G 3 ) 3因此，{v1}不是点割集，P(G1)=P(

{y2,x1} {y3,x3}{x4}{y2,y3} {y2,y3} {y2,y3}y2饱和 y3饱和{x4,x1} {y2} {x4,x1, x 3} {y2, y3}注意： （1）最小支配集必是一个极小支配集，反之不然。 （2）任一支配

定理2 欧拉通路的充要条件 连通图有欧拉通路而无欧拉回 路恰有两个奇数度顶点 证明：定理1的直接推论 有向图的欧拉通路和欧拉回路：类似与无向图5.5.2哈密顿图 定义2 哈密顿通路：含所顶点的基本通路（G中每个顶点 恰在此陆中出现一次）

例如， Г1 Г2 Г3M 可扩路取M = {红边}M 交 错 路可看出：对Г3 ，若取Г3中非 M 的边再连同 M 的不在 Г3中的边组成 M’，则 M’ 的边数比 M的边数多，这 表明 M 不是该图的最大匹配。定理1（Berge, 19

有向图中两点之间有不同方向的两条边，不是多重边。定义2：不含环和多重边的图是简单图，含有多重边的 图称为多重图。下图哪些是简单图，哪些是多重图？(a)(b)(c)(d)a,b为简单图，c,d为多重图。定义3: 每一对顶点间都有边相连的无向简

例4 假设连通图平面性简单图有20个顶点，每个顶点的度 都是3。这个平面性图的平面表示把平面分割成多少个区域？ 解 这个图有20个顶点，每个顶点的度都是3，所以 v=20。因为这些顶点的度之和3v=3*20=60是等于边数的两 倍2e，所以

• 运用空间叠合分析解决以下两个问题 （1）找出满足以上4个条件的最适宜的购房 地段。 （2）对整个城市区域从以上4个条件的住房 条件进行评价，划定不同等级，以供购房 者进行参考• 第一个问题 找出满足以上4个条件的最适宜的购房地段。 步

T(V4)=∞V4P(V1)=0V1 12 8T(V (V2) )=min( ( ∞, ,P(V (V1) )+d d12) =min(∞,0+6)=6 T(V3)

[例题] 1 2 带权图如右，求图的最小生成树 6 5 e 解： 4 3 选取含最大边(c,d)的回路cdec， b c 1 删去其中权数最大的边(c,d)，然后 再选取含最大边(

V1 c1 c2 c3饱和V1的每个顶点的匹配V2 s1 s2 s3 s 4 s592、Hall定理（相异性条件）取图 G 的一个顶点子集S，令 N (S) = { v | 存在 u∈S，且v与u 相邻} 称 N (S) 为 S 的邻集。v

解：由题：边 q 30, 面r 30, 故由欧拉公式得：点 p q r 2 12. 10 . 假定一个连通的平面性 二部图有 v个顶点和 e条边.证明：若 v 3，则 e 2v 4.证：由“连通平面二部 图”知：该图每个

例16. 在任何聚会中，与奇数个人握过手的人必定有偶数 个。 证明： 我们用点来表示聚会中的人，若两个人有握手， 则我们用一条边把表示这两个人的点连接起来。与奇数个 人握过手的那个人，在图上表示为他的度为奇数。由握手 定理，则可知这样的点应

deg (v) deg (v) e ，e=E。vVvV证明： 由定理1的握手定理，可知入度和出度之和为2e。对于任意一条边vivj来说，它若是vi入度边的话，也必 是vj出度边，反

421(1)31(2)3名次1{1，2，3}1 1{(1,2,3)}并列12(1)23 4(2)23 4(3)23 4(4)3名次{1, 2, 3, 4}{2,(1,3,4)}{(

破圈法： 任选一个圈，从圈中去掉权v3 56最大的一条边。在余下的图17中重复这个步骤，直到得到v1 5一不含圈的图为止。• 哥尼斯堡七桥问题 (欧拉回路)/环球旅行问题(哈密尔顿

第五章 支配集、独立集、覆盖集和 Ramsey 数本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的 图均为简单图。§5.1 支配集、点独立集、点覆盖集一、支配集(Domination set)定义 5.1.1 设

u例： v v1v2…vm u, 其中u为非饱和点T由于M*是最大匹配，从上节定理1可知：u为Z中唯一的M* 非饱和点 (否则将含 M * 可扩路) 。且任意一对配对点v和w, 若 v∈S, 则必w∈T, 反之亦然. 因此 | T |= |