第1章 图和子图.ppt

图论及其应用
1 图的基本概念
2 树
3 连通度
4 遍历问题
5 匹配
6 着色问题
7 平面图
8 有向图
9 网络
10 NP-完全问题
第一章图的基本概念
图的概念
同构
图的矩阵和顶点的度
子图
路和连通性
圈
最短路问题
图的概念
Königsberg七桥问题
电网络
四色猜想
图 G = (V(G), E(G)), 其中
V(G) = { } V ---顶点集, ---顶点数
E(G) = { } E ---边集,ε---边数
例如,下图中,
V={a, b,…,f},
E={k,p, q , ae, af, …,ce, cf }
d
e
f
G = (V, E)
p
q
a
b
c
k
注意, 右图仅仅是图G的一个几何实现(geometric realization,代表representation), 它们有无穷多个,随顶点位置及边的形状而不同。真正的图G是上面所给出式子,它与顶点的位置、边的形状等无关。不过今后对图G及其几何实现将经常不加以区别。
d
e
f
G = (V, E)
p
q
a
b
c
k
称边 ad 与顶点a (及d) 相关联(incident)。也称顶点 b(及 f) 与边 bf 相关联。
称顶点a与e 相邻(adjacent)。也称有公共端点的一些边,例如
p与af彼此相邻。
称一条边的两个顶点为它的两个端点
环(loop,selfloop):如边 k ,它的两个端点相同。
棱(link):如边ae,它的两个端点不相同。
重边:如边p及边q。
简单图:(simple graph)无环,无重边
平凡图:仅有一个顶点的图。
注意:任何一图都有 V 。
记号: (,)
d
e
f
G = (V, E)
p
q
a
b
c
k
例题
若G为简单图,则。
若一群人中,凡相识的两人都无公共朋友,凡不相识的两人都恰有两个公共朋友,则每人的朋友数相等。
同构