图论基本概念.ppt

《图论基本概念.ppt》由会员分享，可在线阅读，更多相关《图论基本概念.ppt（34页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、图论基本概念（续）近代数学选讲之一本课程主要内容欧拉图及其判定树（tree)二部图、匹配、独立集、覆盖图论中的一些基本概念图论的一点历史（起源于Euler于1736年解决Konisberg七桥问题）简单无向图一个无向图(undirectedgraph)是由一个非空有限集合V和V中某些元素的无序对集合E构成的二元组，记为G=（V，E）。其中 称为图G的顶点集（vertexset）或节点集（nodeset），V中的每一个元素 称为该图的一个顶点（vertex）或节点（node）；称为图的边集（edgeset），E中的每一个元素 (即中某两个元素的无序对)记为 ，称为该图的一条从 到 的边（edge

2、）。当边 时，称 和 为边 的端点，并称 与 相邻（adjacent）；边 称为与顶点 ，关联（incident）。如果某两条边至少有一个公共端点，则称这两条边在图 G中相邻。子图，诱导子图图H叫做图G的子图（subgraph），记作 ，如果 且 。若H是G的子图，则G称为H的母图。G的支撑子图H（spanningsubgraph，又称生成子图）是指满足V（H）=V（G）的子图。诱导子图，令 为V的子集，G的由W诱导的子图（induced subgraph），记为GS，是以S为顶点集，以 为边集的G的子图。子图子图子图子图诱导子图诱导子图诱导子图诱导子图轨道Path，圈 Cycle,路walk

3、，迹trail 称为图G中的一条路以 为起点，以 为终点的 路（walk），如果 ，并且 与 关联。若 ，称W为闭路。若W的所有边不相同，则称为一条迹（trail）。若W的所有顶点互不相同，称其为轨道（path），有n个顶点的轨道记为一条有n个顶点的轨道若首尾相连，则得到一个圈 （cycle）.图的连通性若图G的两个顶点u,v间存在道路，则称u和v连通(connected)。u,v间的最短轨的长叫做u,v间的距离。记作d（u，v）。若图G的任二顶点均连通，则称G是连通图。C为图 的连通分支，如果C是G的最大连通子图.每个图都看作由一些连通分支组成.割点（cutvertex):G-v连通分支比G

4、多；割边(cutedge):G-e连通分支数比G 多。Euler图Euler图：如果G有一条包含所有边的闭迹（closed trail），则称G为Euler图（俗称可一笔画）。Euler定理：G是Euler图当且仅当G连通且每个顶点度为偶数证明：Fleury算法：例：找出欧拉环游Hamiltonian圈Hamiltonian图：图G的一个子图H称为G的Hamiltonian圈，如果H是一个经过G的所有顶点的圈。一个图若含有Hamiltonian圈，则称为Hamiltonian图；否则为非Hamiltonian图。判定一个图是否是Hamiltonian图是很困难的问题；相反判定其是否为Euler

5、图则很容易。定理（Dirac,1952).G是n阶简单图，若每个顶点的度d(v)n/2,则G是Hamilton-图。例：20个人开圆桌会，其中每人都认识一半以上的人，问能否安排座位使每个人傍边都是认识人？例*：10个男孩与10个女孩一起去郊游，每个人认识一半的异性，问开篝火晚会时能否让每个人傍边都是认识的异性？完全图，多部图一个图称为完全图，记为Kn，如果其任意两个顶点之间有边相连。一个图称为多部图（multi-partite graph），如果其顶点可划分成k部分 ，使得对于任意 ，其诱导子图 中任两点不相邻。若k=2，则G成为二部图（bipartite graph）G为一完全二部图，如果

6、，且 中任意顶点与 中任一顶点相邻，记为G为二部图当且仅当可用两种颜色对G来着色。定理：一个图为二部图当且仅当其不含奇圈（顶点数为奇数的圈）。树(Tree)连通的无圈图叫做树，记之为T。若图G满足 且 ，则称T是G的生成树（spanning tree）。图G连通的充分必要条件为G有生成树。一个连通图的生成树的个数很多，用 表示的生成树的个数，则有Cayley公式 .五个顶点的树一个图是树的充要条件 定理（i）G是树当且仅当G中任两顶点之间有且仅有一条轨道。（ii）G是树当且仅当G无圈，且|E|=|V|-1。（iii）G是树当且仅当G连通，且|E|=|V|-1。（iv）G是树当且仅当G连通，且

7、，不连通。（v）G是树当且仅当G无圈，恰有一个圈。独立集(IS)集合 称为图G的一个独立集（Independent Set），如果M中任两点不相邻；称为最大独立集（Maximum Independent Set）;如果M是所有独立集中势最大的；称为极大独立集（MaximalIndependent Set）,如果M本身是独立集，但任添加一个顶点到M中，则M不再是独立集。匹配（matching)、覆盖 图G的边的集合 称为一个匹配，如果M中任两边不相邻（无公共端点)。M称为G的一个最大匹配，如果M是G的所有匹配中所含边数最多。同样可定义极大匹配。C称为G的点覆盖(covering)，如果G的每条边

8、至少一个端点属于C.最大独立集、最小顶点覆盖定理（Gallai，1959）：设MIS为图G的一个最大独立集，VC为G的最小顶点覆盖，则|MIS|+|VC|=|V|证明：首先，V-MIS一定是G的顶点覆盖。这是因为对任一（，）V，或者V-MIS，或者V-MIS；否则有，MIS，矛盾！因为最大独立集，MISMIS为最小覆盖。证明：最大匹配，最小顶点覆盖定理（Konig）令G为二部图，M为G的最大匹配，VC为G的最小顶点覆盖。则|M|=|VC|。推论：令为二部图，则MIS。推论：令为二部图，则最大匹配有多项式时间算法，则最大独立集也有。（事实上，两者都属于）注：注：KonigKonig定理对一般图不成立定理对一般图不成立一道智力思考题一个8x8的棋盘，去掉两个对角的正方形后，能否被1x2的长方形所完全覆盖？01010101010101001010101101010100101010110101010010101010101010Thanks,End