图论讲义完整版课件.ppt

图是最直观的模型图论简介图论是数学的一个分支,以图为研究对象.这种图由若干给定的点和连接两点的线构成,借以描述某些事物之间的关系.用点代表事物,用连接两点的线表示两个事物之间具有特定关系.图论起源于18世纪,追溯到1736年瑞士数学家L.Euler出版第一本图论著作,提出和解决著名Konigsberg七桥问题.从那时以来,图论不仅在许多领域,如计算机科学,运筹学,心理学等方面得到了广泛的应用,而且学科本身也获得长足发展,形成了拟阵理论,超图理论,代数图论,拓扑图论等新分支.图论GraphTheory哥尼斯堡七桥问题(K?nigsbergBridgeProblem)LeonhardEuler(1707-1783)在1736年发表第一篇图论方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联1图与网路的基本概念1.1图与网路节点(Vertex)物理实体、事物、概念一般用vi表示边(Edge)节点间的连线，表示有关系一般用eij表示图(Graph)节点和边的集合一般用G(V,E)表示点集V={v1,v2,…,vn}边集E={eij}同构图举例G?G’H?H’1?a,2?b,3?c,1?a,2?b,3?c,4?d4?d,5?e,6?f非同构图举例存在结点数及每个结点对应度都相等的两个图仍然不同构的情况.一个例子如下:(注意:两个4度点或邻接或不相邻接)1.2无向图与有向图边都没有方向的图称为无向图在无向图中eij=eji，或(vi,vj)=(vj,vi)当边都有方向时，称为有向图，用G(V,A)表示在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图1.3端点，关联边，相邻，次图中可以只有点，而没有边；而有边必有点若节点vi,vj之间有一条边eij，则称vi,vj是eij的端点(endvertex)，而eij是节点vi,vj的关联边(incidentedge)同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(paralleledges)既没有自环也没有平行边的图称为简单图(simplegraph)在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为d；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(evengraph)1.3端点，关联边，相邻，次有向图中，由节点指向外的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–次数为0的点称为孤立点(isolatedvertex)，次数为1的点称为悬挂点(pendantvertex)定理1：图中奇点的个数总是偶数个1.4链，圈，路径，回路，欧拉回路相邻节点的序列{v1?,v2?,…,vn?}构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directedpath)首尾相连的路径称为回路(circuit)；1.4链，圈，路径，回路，连通图走过图中所有边且每条边仅走一次的闭行走称为欧拉回路定理2：偶图一定存在欧拉回路(一笔画定理)1.5连通图，子图，成分设有两个图G1(V1,E1),G2(V2,E2),若V2?V1,E2?E1，则G2是G1的子图无向图中，若任意两点间至少存在一条路径，则称为连通图(connectedgraph)，否则为非连通图(discon-nectedgraph)；非连通图中的每个连通子图称为成分(component)链，圈，路径(简称路)，回路都是原图的子图平面图(planargraph)，若在平面上可以画出该图而没有任何边相交图的矩阵表示2树图与最小生成树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图2.1树的定义及其