01图论及网络基本知识.ppt

图论与网络基本内容 授课提纲 几个有意思的例子 图与网络的基本定义 图的连通性 图的矩阵表示 几种特殊的图 几个有意思的例子 哥德堡七桥问题 四色猜想 Hamilton周游世界游戏 Ramsey 问题 哥德堡七桥问题 四色猜想 Hamilton 环游世界问题 Ramsey 问题 任何六个人中，或有三个人互相认识，或有三个人互不认识，二者必居其一。 更一般性的问题：若一群人中或有m个人互相认识，或有n个人互不认识，则这群人最少得有多少人？记为Ramsey(m,n) [例] Ramsey(3,3)=6 图与网络的基本定义 无向图 有向图 图中的元素及关系 网络 顶点的度数 无向图 定义：无向图G=V,E, 其中V??称为顶点集, 其元素称为顶点或结点; E是V?V的多重子集, 称为边集, 其元素称为无向边，简称边. 有时用V(G)和E(G)分别表示V和E。 有向图 定义：有向图D=V,E, 其中V??称为顶点集, 其元素称为顶点或结点; E是V ? V的多重子集, 称为边集, 其元素称为无向边，简称边. 有时用V(D)和E(D)分别表示V和E。 图中的元素及关系 端点： ek=(vi, vj)?E, 称vi, vj为ek的端点； 关联： ek与vi ( vj)关联； 相邻：具有公共端点的两条边；或者与同一条边关联的两个点称为 相邻； 平行边：具有相同端点的两条边 环：两个端点为同一个点的边 简单图：无平行边无环的图 带权图（网络） 图G的每一条边e附加一个实数w(e), 称作边e的权. 图G连 同附加在边上的权称作带权图（网络）, 记作G=V,E,W. 无向图顶点的度数 设G=V,E为无向图, v?V, v的度数(度) d(v): v作为边的端点次数之和 悬挂顶点: 度数为1的顶点 悬挂边: 与悬挂顶点关联的边 G的最大度?(G)=max{d(v)| v?V} G的最小度?(G)=min{d(v)| v?V} 例如 d(v5)=3, d(v2)=4, d(v1)=4, ?(G)=4, ?(G)=1, v4是悬挂顶点, e7是悬挂边, e1是环 有向图顶点的度数 设D=V,E为有向图, v?V, v的出度d+(v): v作为边的始点次数之和 v的入度d?(v): v作为边的终点次数之和 v的度数(度) d(v): v作为边的端点次数之和 d(v)= d+(v)+ d-(v) ?+(D), ?+(D), ??(D), ??(D), ?(D), ?(D) 悬挂顶点, 悬挂边 例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, ?+=4, ?+=0, ??=3, ??=1, ?=5, ?=3 握手定理 定理 任何图(无向图和有向图)的所有顶点度数之和都 等于边数的2倍。 证 图中每条边(包括环)均有两个端点, 所以在计算各顶点 度数之和时, 每条边均提供2度, m条边共提供2m度。 推论 任何图(无向图和有向图)都有偶数个奇度顶点。 定理 有向图所有顶点的入度之和等于出度之和等于边数 证 每条边恰好提供1个入度和1个出度。 图的连通性 路与圈 无向图的连通性与连通分支 无向图中的最短路与距离 点割集与边割集 点连通度与边连通度 有向图的连通性及其分类 有向图中的最短路与距离 路与圈 定义：给定图G=V,E, G中顶点与边的交替序列?=v0e1v1e2…elvl.若?i(1?i?l), ei=(vi?1,vi), 则称?为v0到vl的通路, v0和vl分别为通路的起点和终点, l为路的长度. 又若v0=vl, 则称?为回路. 若通路(回路)中所有顶点(对于回路, 除v0=vl)各异, 则称为初级通路或路(初级回路或圈). 长度为奇数的圈称作奇圈,长度为偶数的圈称作偶圈。 表示方法 ① 按定义用顶点和边的交替序列, ?=v0e1v1e2…elvl ② 用边序列, ?=e1e2…el ③ 简单图中, 用顶点序列, ?=v0v1…vl 实例 无向图连通与连通分支 设无向图G=V,E, u,v?V u与v连通: 若u与v之间有通路. 规定u与自身总是连通的. 连通图: 任意两点都连通的图. 平凡图是连通图 连通关系 :R={u,v| u,v ?V且u与v连通}. 连通分支: 连通的子图. 连通分支数:p(G)=k G是连通图? p(G)=1 无向图中的最短路与距离 u与v间的最短路:u与v之间长度最短的通路(设u与v连通) u与v间的距离d(u,v):u与v之间短程线的长度 若u与v不连通, 规