图论 PPT G1基本概念.pptVIP

图的画法 图可以画出来:顶点画成点,边画成连接顶点的曲线. 例如下图G可画成右边两种样子: V(G) ? {A,B,C} ? E(G) ? {eAB, eBC, eAC} ? ? 有关度的若干术语 孤立点:度为0的顶点 悬点:度为1的顶点 悬边:与悬点关联的边 奇点:度为奇数的顶点 偶点:度为偶数的顶点 正则图:各顶点度相同 若度为k,称为k-正则图. 例如:Kn是(n?1)-正则图 二部图 定义:设G ? (V,E)是简单图.若V可划分为不相交的非空集合V1和V2,且E中所有边都连接V1中的一个顶点和V2中的一个顶点,则称G为二部图(bipartite graph)或偶图. 若V1中任一顶点都与V2中每个顶点相邻,则称为完全二部图. 若|V1| ? m, |V2| ? n, 则完全二部图记为Km,n Lu Chaojun, SJTU Lu Chaojun, SJTU 图的基本概念 * Lu Chaojun, SJTU 图论的研究对象 世界由事物组成,事物之间有联系. 图可以直观地描述事物及其间联系. 用结点表示事物 用边表示事物间联系 可见,图模型几乎可用于任何领域. 图论(graph theory)就是以这种结点和边构成的图为研究对象. * Lu Chaojun, SJTU 图的例子 七桥问题 红楼家谱 乙烷 Lu Chaojun, SJTU * 图的定义 定义:图G是二元组(V,E),其中 V是非空顶点集合 E是边集合,每条边与V中两个顶点(可相同)相关联. 若边e与顶点u,v关联,称u和v 相邻, 亦称e连接u,v. 对任意图G,约定用V(G)和E(G)表示该图的顶点集和边集. Lu Chaojun, SJTU * graph vertex edge adjacent 有限图vs无限图 有限图:V和E是有限集合 无限图:V或E是无限集合 我们只讨论有限图: V ? {v1, v2,…, vn} E ? {e1, e2,…, em} 以后不加说明时,都假定图有n个结点,m条边. 若|V(G)| ? n,称G是n阶图. Lu Chaojun, SJTU * 无向图vs有向图 无向边:边无方向,可视为顶点的无序对. 记作e ?{u,v} ? uv ? vu, u和v称为e的端点. 有向边:边有方向,可视为顶点的有序对. 记作e ? (u,v), u称始点, v称终点. 无向图:E中都是无向边. 以后不加说明的都是无向图. 有向图: E中都是有向边. Lu Chaojun, SJTU * undirected edge directed edge endpoint initial vertex terminal vertex undirected graph directed graph 简单图vs多重图 环:所关联的两个顶点重合的边. 重边:关联两个顶点的多条边. 多重图:有重边的图. 简单图:无重边无环的无向图. 完全图:任意两个不同顶点都相邻的简单图. n个结点的完全图记作Kn . 空图/零图:无边的简单图,记作Nn . Lu Chaojun, SJTU * loop multiple edge multigraph simple graph null / empty graph complete graph 顶点的度 顶点的度(degree):与顶点v关联的边数. 记作dG(v)或d(v). 环对d(v)的贡献为2. 对有向图:d(v) ? d+(v) + d?(v) 出度(out-degree) d+(v) ? 以v为始点的边数 入度(in-degree) d?(v) ? 以v为终点的边数 环对出度,入度各贡献1. 例如: Kn中各顶点的度都为n ? 1. Lu Chaojun, SJTU * 握手定理及其推论 定理[握手定理]:图G ? (V,E),若|E| ? m.则 推论:G中奇点数目必为偶数. 推论:Kn的边数为n(n?1)?2. Lu Chaojun, SJTU * 子图 定义:给定G ? (V,E), 如果G? ? (V?,E?)满足V??V, E?? E,则称G?是G的子图(subgraph),记作G?? G. 如果G? ? G,则称G?是G的真子图,记作G??G; 平凡子图: G和Nn 如果V??V,则称G?是G的支撑(spanning)子图或生成子图; 如果E?包含了G在V?中的所有边,则称G?是G的导出(induced)子图. * Lu Chaojun, SJTU 例:子图 下图中 G?和G?都是G的子图 G?是G的