资源描述：
《图结构和基本问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图结构和基本问题-----------------------页面1-----------------------图结构和基本问题刘汝佳-----------------------页面2-----------------------目录一、预备知识二、图的遍历及其应用三、有向图：强连通分量和传递闭包四、无向图：割顶、桥和双连通分量五、强连通化和支配点六、特殊图类介绍七、经典问题列表-----------------------页面3-----------------------1预备知识1.1图的基本概念1.2路径、圈
2、和连通性1.3生成树、完全图和补图1.4特殊图类1.5有向图和带权图1.6图的ADT1.7邻接矩阵1.8邻接表和前向星-----------------------页面4-----------------------图的基本概念*图G=(V,E),即顶点集和边集组成的二元组,它描述了顶点集的相互关系*本文只考虑简单图–边的两端不是同一个顶点(没有自环self-loops)–一对结点最多被一条边连接(没有重边paralleledges)*注意:自环和重边在有些情况(见后)很有用*图的数学表示–点:用整数0,1,2,…,V-
3、1表示–边:用无序数对(u,v)表示,或者表示成u-v*边数E不超过V(V-1)/2-----------------------页面5-----------------------图形表示*此二图是同一个图的不同表示.图中并不定义各个结点的位置以及边的形态(直线?曲线?),关键是有哪些点，哪些点相连*所有边如下表-----------------------页面6-----------------------其他术语*其他名称–结点=顶点:vertex,node–边=弧:edge,arc,link*对于边e=(u,v)
4、–u和v邻接(adjacent)–e和u、v关联(incident)–点的度数(degree)是与它关联的边的数目*子图–子图(subgraph):边的子集和相关联的点集–导出子图(inducedgraph):点的子集和相关联的边集-----------------------页面7-----------------------图绘制*图绘制(GraphDrawing):顶点赋予几何坐标,边绘制成直线或者曲线*平面图(planargraph):可以绘制成边不相交的形式*欧几里得图(euclideangraph)的绘制中,
5、顶点的位置和边是有意义的,例如地图或者电路图*本文的多数算法不使用几何信息-----------------------页面8-----------------------同构*上面两个图同构,但不和下面的图同构-----------------------页面9-----------------------路径和圈*一条路径(path)是一个结点序列,路上的相邻结点在图上是邻接的.*如果结点和边都不重复出现,则称为简单路径(simplepath).如果除了起点和终点相同外没有重复顶点和边,称为圈(cycle).*不相交
6、路(disjointpath)表示没有除了起点和终点没有公共点的路.更严格地–任意点都不相同的叫严格不相交路(vertex-disjointpath)–同理定义边不相交(edge-disjointpath)路*注意:汉语中圈和环经常混用(包括一些固定术语).由于一般不讨论自环(self-loop),所以以后假设二者等价而不会引起混淆-----------------------页面10-----------------------连通性*如果任意两点都有路径,则称图是连通(connected)的,否则称图是非连通的.*非
7、连通图有多个连通分量(connectedcomponent,cc),每个连通分量是一个极大连通子图(maximalconnectedsubgraph),因为任意加一个结点以后将成为非连通图-----------------------页面11-----------------------生成树*连通去圈图成为树(tree)*树的集合称为森林(forest)*生成树:包含某图G所有点的树*生成森林:包含某图G所有点的森林*一个图G是树当且仅当以下任意一个条件成立–G有V-1条边,无圈–G有V-1条边,连通–任意两点只有唯一
8、的简单路径–G连通,但任意删除一条边后不连通*还有其他条件,可类似定义-----------------------页面12-----------------------完全图和补图*如果V个点的图有V(V-1)/2图,称为完全图*对于(u,v),若邻接则改为非邻接,若非邻接则改为邻接,得到的图为原图的补图*原图和补
