2009-7-29
第一节 图的基本概念
1,图与子图

为边集。
为顶点集，，其中图
eeE
vvVEVG
,,
,,),(
1
1

。其中子图 EEVVEVG,),,(
e1
e2
e3e5 e6
e4e7 v3
v2v1
v4
e2
e3e5 e6
e4 v3
v2v1
v4
G1：如 G：
简单图：无环、无多重边的图。
2009-7-29
2,关联与相邻关联。与或称记二点间的边，是若关联（边与点关系）：
evvvve
vve
)(],,[
,
2121
21
相邻。与有公共点，称与边相邻；与称有公共边，与）：点相邻（边与边、点与点
212121
21
eeeevv
vv
3,链与圈

],,[ 1
12211
中的一条链。则称此边点序列为若满足
，成的序列中的某些点与边相间构链：由
Gvve
veevevG
圈：封闭的链。
条链。中任二点间至少存在一连通图：图 G
2009-7-29
4,有向图与无向图

在图上用箭线表示。的边为弧，记（
，称有向图为有向图。为区别起见为无向图；否则称称无序，若点对也可记图
),,vv
GG
vvvvvGEVG ],[).],[,(),,(

），路有向图：弧（
，链无向图：边
ji
ji
vv
vv
,
],[
，圈
，回路比较：
2009-7-29
5,树例 1 已知有 5个城市，要在它们之间架设电话线网，要求任 2城市都可通话（允许通过其它城市），并且电话线的根数最少。
v1
v2
v3
v5
v4
特点：连通、无圈。
树 —— 无圈的连通图，记为 T。
2009-7-29
v1
v2
v3
v5
v4
树的性质：（ 1）树的任 2点间有且仅有 1链；
（ 2）在树中任去掉 1边，则不连通；
（ 3）在树中不相邻 2点间添 1边，恰成 1圈；
（ 4）若树 T有 m个顶点，则 T有 m-1条边。
2009-7-29
6.图的部分（支撑）树若图 G=（ V,E） 的子图 T=（ V,E’） 是树，
则称 T为 G的部分树或支撑树。
特点 —— 边少、点不少。
性质,G连通，则 G必有部分树。
证：破圈、保连通。