2009-7-26 1
运 筹 学 Operations Research
§ 6.1 图的基本概念图（ graph）,用顶点代表对象，顶点之间的边表示对象之间的关系,
注：图与几何图形不同,
2009-7-26 2
运 筹 学 Operations Research
图的表示,),( EVG?
顶点集：
边集：
V
E
顶点 (vertex)：
边 (edge)：
Vv?
Euve
顶点数：
边数：
V
E
2009-7-26 3
运 筹 学 Operations Research
三种关系：
顶点与顶点相邻（邻接）（ adjacent）；
边与边相邻（邻接）；
顶点与边关联（ incident）,
空图（ empty graph）,0,1
平凡图（ trivial graph）,0,1
2009-7-26 4
运 筹 学 Operations Research
连杆 （ link）,两个端点不重合的边；
环 （ loop）,两个端点重合的边；
重边 （ multiedge）,具有相同端点的若干条边,
简单图（ simple graph）,不含有重边和环的图,
赋权图（ weighted graph）,边带有权 （ 表示 距离，长度，流量，费用等 的数字 ） 的图,
2009-7-26 5
运 筹 学 Operations Research
无向图 （ graph）,边无方向的图；
有向图（ digraph）,otherwise.
图的同构（ graphic isomorphism）,结构完全一样的图,
如
2009-7-26 6
运 筹 学 Operations Research
2009-7-26 7
运 筹 学 Operations Research
例 1（ 1） 试画出顶点数为 3的所有不同构的简单图,
（ 2）试画出顶点数为 4的所有不同构的简单图,
解：（ 1）
（ 2） …… ▌
2009-7-26 8
运 筹 学 Operations Research
完全图（ complete graph）,任两个互异顶点之间均恰好有唯一一条边相连的图,
表示：
K
)2(;)1( 2 何时取是简单图，则若性质 CG
2009-7-26 9
运 筹 学 Operations Research
二分图（ bipartite graph）,),( YXG?
2009-7-26 10
运 筹 学 Operations Research
一个二分图：
3-方体
2009-7-26 11
运 筹 学 Operations Research
完全二分图（ complete bipartite graph）：
nmK,
.,, nmnYmX其中
2009-7-26 12
运 筹 学 Operations Research
性质,(1) mnK
nm?)(,?
(2)
4)(
2?
GG 是二分图，则若
(3)何时取等号？
证：（ 1） …
(2)
4)2()2()()(
2
22
,
nmmnKG
nm
(3)
2,2
2
4)(
KGG ▌
2009-7-26 13
运 筹 学 Operations Research
顶点的度（ degree）：
)(
)(
环算两次相关联的边的条数与顶点 vvd G?
最小度（ minimum degree）：
最大度（ maximum degree）：
)}({m i n vdVv
)}({m a x vdVv
奇顶点 （ odd-degree vertex）,度为奇数的顶点偶顶点 （ even-degree vertex）,度为偶数的顶点,
悬挂点 （ suspended vertex）,度为 1的顶点,
悬挂边 （ suspended edge）,与悬挂点相关联的边,
孤立点（ isolated vertex）,度为 0的顶点,
2009-7-26 14
运 筹 学 Operations Research
正则图（ regular graph）,所有顶点的度有相同的图,
如
nnKK,,?
.||||),(2 YXYXG 是正则二分图，则求证：若例正则图，则是证：不妨设?kG
||||||)()(|| YXYkvdvdXk
YvXv


▍
Th1（ 图论第一定理）
2)(
Vv
vd
▍
Corollary（ 握手定理） 任一图中奇顶点的个数为偶数,
2009-7-26 15
运 筹 学 Operations Research
，则偶顶点奇顶点证：令 }{},{ 21 VV



21
)()()(2
VvVvVv
vdvdvd?
.||)()( 1
12
为偶数是奇数，故是偶数,Vvdvd
VvVv



▍
由来：某次宴会上，熟人见面互相握手,求证：握过奇数次手的人的个数必为偶数,
例 3 某次宴会上，共有 28769个人,熟人见面互相握手,求证：若每个人都至少握手一次，则其中必至少有 1人至少握手两次,▍
2009-7-26 16
运 筹 学 Operations Research
.24求证：例


22)(
Vv
vd证,▍
例 5 图的各顶点的度按不增顺序排成的序列称为图的度序列,
问以下数列能否为某简单图的各顶点的度序列？
（ 1） 1,1,2,3,2.
（ 2） 7,6,5,4,3,3,2.
（ 3） 10,6,3,2,2,1,1,1.
（ 4） 5,4,2,2,2,1,1.
解：都不能,▍
2009-7-26 17
运 筹 学 Operations Research
.3
16
的顶点度中至少有一个条边，则个顶点，有求证：若图例
GnnG
.12)(2)1(2
3)(
，矛盾
，则中所有顶点的度都假设反证法证：
nnnvdn
G
Vv

▍
子图（ subgraph）
.
.
),(),(
1
11
1111
GG
GGEE
VVEVGEVG

记作：
的子图为，则称
，，若，设
2009-7-26 18
运 筹 学 Operations Research
真子图（ proper subgraph）,GG?
1
支撑子图（ spanning subgraph）,,)(
11 的子图EEVV
.7 4 图的所有不同构的支撑子画出例 K
解：共有 11个，分别为
2009-7-26 19
运 筹 学 Operations Research
2009-7-26 20
运 筹 学 Operations Research
点导出子图（ vertex-induced subgraph）：
}){,(][ 111 的边中的两个端点均在 GVVVG?
规定,]\[
11 VVGVG

}]{\[ vVGvG
2009-7-26 21
运 筹 学 Operations Research
边导出子图（ edge-induced subgraph）：
)},({][ 111 EEEG 中的边的端点?
规定,]\[
11 EEGEG

}]{\[ eVGeG
2009-7-26 22
运 筹 学 Operations Research
链（ walk）,点边交错出现的序列,
迹 （ trail）,边不重的链,
路（ path）,点不重（当然边也不重）的链,
圈（回路） （ cycle）,闭的路,
2009-7-26 23
运 筹 学 Operations Research
.2)(8 中必含有圈，则图求证：若例 GG
证：
▍
连通图（ connected gragh）
.
.,
是连通图，则称的任两顶点都是连通的若图是连通的与称之间有一条路相连，则若顶点
GG
vuvu
2009-7-26 24
运 筹 学 Operations Research
连通分支（ connected component）,图的各连通部分,
显然，图的连通分支是其极大连通子图,
连通分支数,)(G?
.1)( GG?是连通图图证：分连通和不连通两种情况讨论,▍
.9 它们必连通中恰有两个奇顶点，则求证：若图例 G
2009-7-26 25
运 筹 学 Operations Research
.2
)2(
.)1(10
2
1
2
1

其中
，，使得的不连通的简单图找一个顶点数为必为连通图，则是简单图，且求证：若例
CG
GCG
则）（
，的两个连通分支为，不妨设反证法证
,2,1,1
,2)())(1(,21

iG
GGGG
ii
.
2
)2)(1(
2
)2)(1(
2
)1)(1(
2
)1)(1(
2
)1(
2
)1(
)()()(
2
1
2121
221122
21
21
，矛盾










C
CCGGG
2009-7-26 26
运 筹 学 Operations Research
11)2( KKG
▍
2009-7-26 27
运 筹 学 Operations Research
§ 6.1 over