图论1—图论基础.ppt

图论1—图论基础 孙睿 什么是图? A B C D 哥尼斯堡七桥示意图 问题1(哥尼斯堡七桥问题): 能否从任一陆地出发通过每座桥恰好一次而回到出发点？ A B D C 七桥问题模拟图 欧拉指出： 如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地. 图论中的“图”并不是通常意义下的几何图形或物体的形状图, 而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统. 定义1 一个有序二元组(V, E ) 称为一个图, 记为G = (V, E ), 其中 ① V称为G的顶点集, V≠?, 其元素称为顶点或结点, 简称点; ② E称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边. 如果V = {v1, v2, … , vn}是有限非空点集, 则称G为有限图或n阶图. 如果E的每一条边都是无向边, 则称G为无向图(如图1); 如果E的每一条边都是有向边, 则称G为有向图(如图2); 否则, 称G为混合图. 图 1 图 2 并且常记 V = {v1, v2, … , vn}, |V | = n ; E = {e1, e2, … , em}(ek=vivj ) , |E | = m. 称点vi , vj为边vivj的端点. 在有向图中, 称点vi , vj分别为边vivj的始点和终点. 我们大部分情况只讨论有限简单图： (1) 顶点个数是有限的; (2) 任意一条边有且只有两个不同的点与它相互关联; (3) 若是无向图, 则任意两个顶点最多只有一条边与之相联结; (4) 若是有向图, 则任意两个顶点最多只有两条边与之相联结. 当两个顶点有两条边与之相联结时，这两条边的方向相反. 如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足. 定义2 若将图G的每一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络), 记为G = (V, E , F ). 定义3 设G = (V, E)是一个图, v0, v1, …, vk∈V, 且?1≤i≤k, vi-1vi∈E, 则称v0 v1 … vk是G的一条通路. 如果通路中没有相同的边, 则称此通路为道路. 始点和终点相同的道路称为圈或回路. 如果通路中既没有相同的边, 又没有相同的顶点, 则称此通路为路径, 简称路. 定义4 任意两点均有通路的图称为连通图. 几种特殊的图 完全图：图G的任何两个不同的顶点是邻接的，则图G是完全的 补图：G’的顶点集合为V(G)，且对于图G的每对顶点u，v，uv是G’的边当且仅当uv不是G中的边 空图：G的边集为空集。 二分(部)图：V(G)的顶点能够被划分为两个子集U,W，使得G的每条边必然连接U和W的一个顶点 在图G中，与顶点v相关联的边的总数称为是v的度，记为deg v 图论第一定理 证明：在计算G中所有顶点度的和时，每一条边e被计数了两次。 例题：给出一个非负整数组成的有限序列s，s是否是某个图（无自环）的度序列？ 2 4 2 Yes 3 1 No 首先利用图论第一定理。 然后把所有顶点排序，用最大点的度减去最小点的度，将最小点的度设为0。 如果最后得到全0序列，则输出yes，否则输出no 2 2 3 1 2 0 2 0 0 0 0 例题：给出一个非负整数组成的有限序列s，s是否是某个简单图的度序列？ 3 3 2 2 1 1 Yes 3 3 3 1 No 首先利用图论第一定理。 然后把所有顶点排序，将最大点的值设为0，然后将其后部最大点的值的个数个点的数均减1. 如果最后得到全0序列，则输出yes，否则输出no 3 3 2 2 1 1 3 3 3 1 0 2 1 1 1 1 0 2 2 0 0 0 0 0 1 1 0 0 1 -1 0 0 0 0 0 0 0 0 0 -2 树：无圈的连通图就称为树 因此，图G是树当且仅当G的任何两个端点都被唯一的路连通。 定理：具有n个顶点的不同树的个数是 n^(n-2)