图论ch1图的基本概念

1、图的基本概念(gcheng)图，就在我们身边23networking.jpg4content/uploads/2012/01/SaharaDesertFoodChain1.jpg56Semantic_Net.svg.png一切都源于柯尼斯堡的七座桥7本节课的主要内容1.1 图的基本概念1.5 图的中心与中位点1.6 图的矩阵表示8集合、无序对集合 (set) 一组不重复的对象 例：S=v1, v2, v3=v3, v2, v1=v1, v1, v2, v3无序对 (unordered pair)含有2个或1个元素的集合例：v1, v2，v2常记作：(v1, v2)，(v2, v2)9如无特殊说

2、明，本课程中用()表示无序对用<>表示有序对10图、顶点、边图：G=<V,E>顶点集 (vertex set)：V或V(G)(edge set)：E或E(G) E(G)要满足什么条件？ "e Î E(G), (e Î1,2)"e Î E(G), (e Í V (G)图的规模 阶(order)：(G)=|V(G)| /读音“纽”v1e1(size)：(G)=|E(G)|e5e4v2e7e2v5边的几种记法：e=(u, v)=uvv3e3v411图、顶点、边(续)一些术语v1、v2是e1的端点(endpoint)v

3、1、v2和e1关联(incident) v1和v2相邻(adjacent)e1和e2相邻(adjacent) e7是环边(loop)v1e1e5e4v2e7e2v5v3e3v412如果我们用刚才的集合表示法来表示这个图，你觉得会不会有什么？v1e1e6e5e4v2e7e2v5v3e3v413多重集合、重边多重集合 (multiset) 一组可重复的对象 例：S=v1, v2, v3=v3, v2, v1v1, v1, v2, v3重边 (multiple edges)例：e5和e6E(G)=(v1, v2), (v2, v3), (v3, v4), (v3, v5), (v1, v5), (v

4、1, v5), (v5, v5)v1e1e6e5e4v2e7e2v5v3e3v414度顶点的度 (degree) 顶点关联的边的数量，环边计2次 例：d(v1)=3，d(v5)=5图的度 最大度：D(G) = max d (v)vÎV (G )最小度：d (G) = min d (v)vÎV (G )v1e1e6e5e4v2e7e2v5v3e3v415推论1.1.1任何图中，奇度顶点的个数总是偶数（0）。证明：1. 顶点度数之和为偶数。2. 奇度顶点的个数不能是奇数。16一些重要类型的图零图(null graph) V(G)=空图 (empty graph) 平凡图(tri

5、vial graph) 简单图 (simple graph)完全图 (complete graph) k正则图 (kregular graph) 二部图 (bipartite graph)完全二部图 (complete bipartite graph)17一些重要类型的图零图 (null graph)空图(empty graph) E(G)=平凡图(trivial graph)简单图 (simple graph)完全图 (complete graph) k正则图 (kregular graph) 二部图 (bipartite graph)完全二部图 (complete bipartite gr

6、aph)18一些重要类型的图零图 (null graph)空图 (empty graph)平凡图(trivial graph) (G)=1的空图简单图 (simple graph)完全图 (complete graph) k正则图 (kregular graph) 二部图 (bipartite graph)完全二部图 (complete bipartite graph)19一些重要类型的图零图 (null graph)空图 (empty graph) 平凡图(trivial graph) 简单图(simple graph) 没有环边和重边完全图 (complete graph) k正则图 (k

7、regular graph) 二部图 (bipartite graph)v1e1e6e5e4v2e7e2v5v3e3v4完全二部图 (complete bipartite graph)20一些重要类型的图零图 (null graph)空图 (empty graph) 平凡图(trivial graph) 简单图 (simple graph)完全图(complete graph) 每对顶点都相邻的简单图，记作K(G)k正则图 (kregular graph)二部图 (bipartite graph)完全二部图 (complete bipartite graph)21一些重要类型的图零图 (nul

8、l graph)空图 (empty graph) 平凡图(trivial graph) 简单图 (simple graph)完全图 (complete graph)k正则图(kregular graph)"v ÎV (G), (d (v) = k )二部图 (bipartite graph)完全二部图 (complete bipartite graph)22一些重要类型的图零图 (null graph)空图 (empty graph) 平凡图(trivial graph) 简单图 (simple graph)完全图 (complete graph) k正则图 (kregul

9、ar graph) 二部图(bipartite graph) V (G) = X È Y , X ¹ Æ,Y ¹ Æ, X Ç Y = Æ"e Î E(G), (e Ç X ¹ Æ)Ù (e Ç Y ¹ Æ)完全二部图 (complete bipartite graph)23一些重要类型的图零图 (null graph)空图 (empty graph) 平凡图(trivial graph) 简单图 (simple graph)完全图 (

10、complete graph) k正则图 (kregular graph) 二部图 (bipartite graph)完全二部图(complete bipartite graph) 每对XY顶点都相邻的简单图，记作K|X|,|Y|24如无特殊说明，本课程讨论的是简单图25图的1：父子H是G的子图(subgraph) V(H)V(G) E(H)E(G)H是G的生成子图 (spanning subgraph)H是G的V点导出子图 (induced subgraph)H是G的E边导出子图 (edgeinduced subgraph)e1v1e5e4v2v2e4e2e2v5v5v3v3e3v4v426

11、图的1：父子H是G的子图 (subgraph)H是G的生成子图(spanning subgraph) V(H)=V(G)H是G的V点导出子图 (induced subgraph)H是G的E边导出子图 (edgeinduced subgraph)v1e1v1e5e4v2v2e2e2v5v5v3v3e3v4v427图的1：父子H是G的子图 (subgraph)H是G的生成子图 (spanning subgraph)H是G的V点导出子图(induced subgraph) "v , v ÎV ' = V (H ), ( v , v )Î E(G) ®

12、(v , v )Î E(H ) ，记作H=GVijijijH是G的E边导出子图 (edgeinduced subgraph)v1e1e5e4v2v2e4e2e2v5v5v3v3e3e3v4v428图的1：父子H是G的子图 (subgraph)H是G的生成子图 (spanning subgraph)H是G的V点导出子图 (induced subgraph)H是G的E边导出子图 (edgeinduced subgraph) V (H ) =Ue，记作H=GEeÎE '= E (H )v1v1e1e5e4e5e4v2e2v5v5v3v3e3v429图的1：父子(续)一些记

13、法GV：GV(G)VGv：Gv GE：<V(G), E(G)E>Ge：Gev1e1e5e4v2v2e4e2e2v5v5v3v3e3e3v4v430图的2：同构G和H同构 (isomorphism): V(G)V(H) (u, v)E(G) iff. (u), (v)E(H)记作 G H图的同构是等价（自称、传递）v2v1ee41e3v4ee5e42v2ve51ve5e21v5v3v3e3v431图的2：同构(续)你是如何判定图是否同构的？属于NP，但属于P还是NPC？还不知道！32图片来自图的运算G的补图(complement) G = V (G),(x, y)Ï E(G

14、)G和H的并 (union)G和H的不交并/和 (addition) G和H的联/连接(join)G和H的对称差 (symmetric difference)bbxaxacc33图的运算G的补图 (complement)G和H的并(union)V (G)ÈV (H ), E(G)È E(H ) G È H =G和H的不交并/和 (addition)G和H的联/连接(join)G和H的对称差 (symmetric difference)bbbÈxaayxayccc34图的运算G的补图 (complement)G和H的并 (union)G和H的不交并/和(a

15、ddition) 仅当V (G)ÇV (H ) = ÆG + H = V (G)ÈV (H ), E(G)È E(H )G和H的联/连接(join)G和H的对称差 (symmetric difference)bebe+xadyxadyccff35图的运算G的补图 (complement)G和H的并 (union)G和H的不交并/和 (addition)仅当V (G)ÇV (H ) = ÆG和H的联/连接(join)V (G)ÈV (H ), E(G)È E(H )È (x, y)| x ÎV (

16、G)Ù y ÎV (H ) G Ú H =G和H的对称差 (symmetric difference)babaxxÚyycdcd36图的运算G的补图 (complement)G和H的并 (union)G和H的不交并/和 (addition) G和H的联/连接(join)G和H的对称差(symmetric difference)仅当V (G) = V (H ) = VV , (E(G)È E(H ) (E(G)Ç E(H ) G Å H =bbbÅ a aacdcdcd37途经、迹、路、圈v1e1e5e4v2e2v5

17、v3e3v438途径 (walk) 顶点和边交替出现的序列v0, e1, v1, , ek, vk ei=(vi1, vi) v0和vk分别称作起点和终点途经、迹、路、圈边不重复出现v1e1e5e4v2e2v5v3e3v439迹 (trail)途径 (walk) 顶点和边交替出现的序列v0, e1, v1, , ek, vk ei=(vi1, vi) v0和vk分别称作起点和终点途经、迹、路、圈边不重复出现顶点不重复出现v1e1e5e4v2简单图中，路的记法中可以省略边e2v5v3e3v440路(path)迹 (trail)途径 (walk) 顶点和边交替出现的序列v0, e1, v1, ,

18、ek, vk ei=(vi1, vi) v0和vk分别称作起点和终点途经、迹、路、圈起点和终点相同边不重复出现顶点不重复出现v1e1e5e4v2e2v5v3e3v441路(path)迹 (trail)闭途径 (closed walk)途径 (walk) 顶点和边交替出现的序列v0, e1, v1, , ek, vk ei=(vi1, vi) v0和vk分别称作起点和终点途经、迹、路、圈起点和终点相同边不重复出现顶点不重复出现v1e1e5e4v2e2v5v3e3v442路(path)(closed trail)迹 (trail)闭途径 (closed walk)途径 (walk) 顶点和边交替出

19、现的序列v0, e1, v1, , ek, vk ei=(vi1, vi) v0和vk分别称作起点和终点途经、迹、路、圈起点和终点相同边不重复出现顶点不重复出现（起点和终点除外）v1e1e5e4v2e2v5v3e3v443圈 (cycle)路(path)(closed trail)迹 (trail)闭途径 (closed walk)途径 (walk) 顶点和边交替出现的序列v0, e1, v1, , ek, vk ei=(vi1, vi) v0和vk分别称作起点和终点长度途径的长度 (length) 边的数量路的长度 u到v的最短路 (shortest path)：u到v的长度最小的路 距离(

20、distance)：最短路的长度，记作d(u, v)圈的长度v1奇圈(odd cycle)：长度为奇数的圈偶圈 (even cycle)：长度为偶数的圈围长(girth)：最短圈的长度e1e5e4v周长(circumference)：最长圈的长度2e2v5v3e3v444例1.1.3 设G是简单图，若d (G) ³ 3，则G必有偶圈。证明：1. G有最长路，记作P=v0, , vk2. v0在P上有两个不同于v1的相邻顶点vi和vji或j是奇数，i和j是偶数，偶圈偶圈v0v1vivjvk45定理1.1.2一个非平凡图是二部图当且仅当它不含奇圈。证明：1.必要性：每次走回起点，都要经过

21、偶数条边2.充分性：提示：将所有顶点分为X和Y两部分，证明X和Y的内部不可能有边任取顶点u，定义：X=与u距离为奇数的顶点，Y=与u距离为偶数的顶点v1反证法：有边就有奇圈思考：u 恰是v 或v 怎么办？12思考：u无路可达的顶点怎么办？1同奇偶uu'v246连通连通 (connected) 两顶点间有路连通图 (connected graph) 每对顶点都连通连通分支 (connected component) 极大连通子图v3v1v4v2G的连通分支数记作w(G)v547定理1.1.2 (续)一个非平凡图是二部图当且仅当它不含奇圈。证明：1.必要性：每次走回起点，都要经过偶数条边2.充分性：提示：将所有顶点分为X和Y两部分，证明X和Y的内部不可能有边任取顶点u，定义：X=与u距离为奇数的顶点，Y=与u距离为偶数的顶点v1反证法：有边就有奇圈思考：u 恰是v 或v 怎么办？12思考：u无路可达的顶点怎么办？每个连通分支都是二部图1同奇偶uu'v248连通图的性质若图G连通，则(G)(G)1。证明：1.从空图开始，每添加一条边，w最多减少1v1e1e5e4v2e2v5v3e3v449连通图的中心和中位点离心率 (eccentricity)e(v) = max d (v, u )uÎV (G )中心 (center)vvvvvarg min e(v)1