理学图论简介.ppt

文档介绍：该【理学图论简介 】是由【1557281760】上传分享，文档一共【54】页，该文档可以免费在线阅读，需要了解更多关于【理学图论简介 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。理学图论简介
一、图论的开展
图与网络最优化理论
(1736年)
普雷格尔河流经哥尼斯堡小城,河中有两个小岛,在四块陆地之间修建了七座小桥.
§1图论的根本概念
Euler研究了这一游戏问题,他将四块陆地视为四个结点,——Euler图问题.
问题一:一个居民从家中出来散步,经过每座小桥一次且仅一次,然后回到家中.
问题二:一个居民从家中出来散步,经过每座小桥一次且仅一次即可.
Königsberg桥对应的图
Euler证明了:哥尼斯堡七桥问题的两个提法都不成立.
此类问题也称为Euler(回)路问题.
(1856年)
有人用一个十二面体代表地球,它上面的二十个顶点代表世界上的二十个大城市,三十条棱,表示连接二十个大城市的路径.
(四色猜测)问题(19世纪中)
任何一个国家或地区的地图仅需要四种不同的颜色着色,就可以将相邻区域用不同颜色区分.
问题:一个人从任一点出发,经过每个顶点一次且仅一次后,回到出发地.
Hamilton最早对这类问题进展了研究,此类问题也称为Hamilton环游问题.
二、图论的根本概念
图是一个三元有序组G=(G(V),G(E),G).其中G(V)是一个非空的顶点集合,简称为点集,(E)是一个与V不交的边集合,简称为边集,简记为E.G称为关联函数,G:EVV.
一个图简记为G=(V,E)
VV是一种集合运算,称为笛卡儿乘积,当VV中的元素为有序时,图G称为有向图,否那么称G为无向图.
假设eE,u,vV,当G(e)=uv时,称边e与顶点u,v相关联,即边e连接顶点u,,v为e的端点.
,,因人而异.
与同一条边相关联两个顶点称为相邻的;
相关联与同一个顶点的两条边称为相邻的.
两个顶点重合为一点的边称为环;
一条边与其端点称为相关联的;
以一样两顶点为端点的边(有向边的方向一样)称为重边.
在大多数情况下,图论研究无环无重边的有限简单图.
三、图论的矩阵表示
设图G=(V,E),|V|=n,|E|=m.
图G的关联矩阵是一个nm矩阵R=(rij)nm,其中rij是顶点vi与边ej相关联的次数,只能取0,1,2(边ej为环时取2).
图G的邻接矩阵是一个nn矩阵A=(aij)nn,其中aij是连接顶点vi与vj的边的数目.
,关联矩阵R和邻接矩阵A的元素只有0和1.
关联矩阵R中列元素的和等于2,因为一条边只关联两个顶点.
在(边)加权图中,邻接矩阵A=(aij)nn中的aij表示顶点vi,,vj不相邻时赋何值,视情况而定.
次为奇数的顶点称为奇点,否那么称为偶点.
定理:设图G=(V,E),假设|E|=m,那么
推论:在任何图中,奇点个数为偶数.
四、顶点的次(度)
图G的顶点v的次(或称度)dG(v)是指图G中与v关联边的数目,每个环记两个次.
一、路,回路,连通
图G的一条路是指一个顶点与边交织出现的非空有限序列
W=v0e1v1e2···vk-1ekvk
使得对1ik,边ei以vi-1,vi为端点,也称W为从v0到vk的一条路,v0,vk称为路W的起,终点,k称为路W的长.
§2图的连通性与最短路问题
边不一样的路称为简单路,顶点不同的路称为根本路.
一条起,.
在简单图中,路W可以表示为顶点序列
W=v0v1···vk-1vk
二部图(偶图):图G=(V,E),如果顶点集合V可以被划分为两个不相交的非空子集S,T,即S∩T=,S∪T=V,且对任意的边uvE,那么uS,vT.
定理2:一个图是偶图当且仅当图中不含奇回路.
图G的两顶点u,v称为连通的,如果存在连接u,,,那么可以把该图分割成假设干个连同的子图,称为连通分支.