文档介绍：第六章图与网路分析
图是最直观的模型
1
B
A
C
D
图论 Graph Theory
哥尼斯堡七桥问题(Königsberg Bridge Problem)
Leonhard Euler (1707-1783) 在1736年发表第一篇图论方面的论文,奠基了图论中的一些基本定理
很多问题都可以用点和线来表示,一般点表示实体,线表示实体间的关联
2
图与网路的基本概念
节点(Vertex)
物理实体、事物、概念
一般用 vi 表示
边(Edge)
节点间的连线,表示有关系
一般用 eij 表示
图(Graph)
节点和边的集合
一般用 G(V,E) 表示
点集 V={v1,v2,…, vn}
边集E={eij }
网路(Network)
边上具有表示连接强度的权值,如 wij
又称加权图(Weighted graph)
3
无向图与有向图
边都没有方向的图称为无向图,
在无向图中 eij=eji,或(vi, vj)=(vj, vi)
当边都有方向时,称为有向图,用G(V,A)表示
在有向图中,有向边又称为弧,用 aij表示,i, j 的顺序是不能颠倒的,图中弧的方向用箭头标识
图中既有边又有弧,称为混合图
4
端点,关联边,相邻,次
图中可以只有点,而没有边;而有边必有点
若节点vi, vj 之间有一条边 eij,则称 vi, vj 是 eij 的端点(end vertex),而 eij 是节点 vi, vj 的关联边(incident edge)
同一条边的两个端点称为相邻(adjacent)节点,具有共同端点的边称为相邻边
一条边的两个端点相同,称为自环(self-loop);具有两个共同端点的两条边称为平行边(parallel edges)
既没有自环也没有平行边的图称为简单图(simple graph)
在无向图中,与节点相关联边的数目,称为该节点的“次”(degree),记为 d ;次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even);图中都是偶点的图称为偶图(even graph)
5
端点,关联边,相邻,次
有向图中,由节点指向外的弧的数目称为正次数,记为 d+,指向该节点的弧的数目称为负次数,记为 d–
次数为 0 的点称为孤立点(isolated vertex) ,次数为 1 的点称为悬挂点(pendant vertex)
定理 1:图中奇点的个数总是偶数个
链,圈,路径,回路,欧拉回路
相邻节点的序列{v1,v2,…, vn} 构成一条链(link),又称为行走(walk);首尾相连的链称为圈(loop),或闭行走
在无向图中,节点不重复出现的链称为路径(path);在有向图中,节点不重复出现且链中所有弧的方向一致,则称为有向路径(directed path)
首尾相连的路径称为回路(circuit);
6
链,圈,路径,回路,连通图
走过图中所有边且每条边仅走一次的闭行走称为欧拉回路
定理 2:偶图一定存在欧拉回路(一笔画定理)
连通图,子图,成分
设有两个图 G1(V1, E1), G2(V2, E2), 若V2 V1, E2 E1, 则 G2 是 G1 的子图
无向图中,若任意两点间至少存在一条路径,则称为连通图(connected graph),否则为非连通图( discon-nected graph);非连通图中的每个连通子图称为成分(component)
链,圈,路径(简称路),回路都是原图的子图
平面图(planar graph),若在平面上可以画出该图而没有任何边相交
7
树图与最小生成树
一般研究无向图
树图:倒置的树,根(root)在上,树叶(leaf)在下
多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图
8
树的定义及其性质
任两点之间有且只有一条路径的图称为树(tree),记为T
树的性质:
最少边的连通子图,树中必不存在回路
任何树必存在次数为 1 的点
具有 n 个节点的树 T 的边恰好为 n1 条,反之,任何有n 个节点, n1 条边的连通图必是一棵树
图的生成树
树 T 是连通图 G 的生成树(spanning tree),若 T 是 G的子图且包含图 G 的所有的节点;包含图 G 中部分指定节点的树称为 steiner tree
每个节点有唯一标号的图称为标记图,标记图的生成树称为标记树(labeled tree)
Caylay 定理:n (2)个节点,有nn2个不同的标记树
9
图的生成