图的基本概念 无向图及有向图ppt课件

离散数学，CH7图的基本概念1无向图和有向图，1图论的起源，图论是组合数学的一个分支，它起源于1736年欧拉关于图论的第一篇论文，这篇论文解决了著名的“柯尼斯堡七桥问题”，从而使欧拉成为图论的创始人。哥尼斯堡的7座桥位于前苏联的加里宁格勒，历史上曾是德国东普鲁士省的首府。弗里茨普雷格尔河穿过城堡。河里有两个小岛，共有7座桥连接两岸和小岛。问：在所有的桥只能走一次的前提下，这个地方的所有桥怎么能都通过呢？3、柯尼斯堡7号桥问题的解决，莱昂哈德欧拉(LeonhardEuler)在1735年成功地解决了这个问题，证明这个方法不存在，也顺便解决了一个中风的问题。他在圣彼得堡科学院发表了图论史上的第一份重要文件。欧拉将实际的抽象问题简化为平面上的点和线的组合，每座桥被视为一条线，桥所连接的区域被视为一个点。这样，如果你从某一点开始，最后回到这一点，这一点的行数必须是偶数。，4。图论的起源。欧拉最后给出了一个判断任何一个河桥图是否可以走一次的规则。如果有两个以上的地方连接奇数桥，则没有符合要求的路线。如果只有两个地方有奇怪的桥，所需的路线可以从任何一个地方找到。如果没有奇数桥的地方，所需的路线可以从任何地方实现。他还解释了如何快速找到所需路线。许多数学家试图分析这个案例。这些分析最终发展成数学中的图论。5，欧拉图，定义一个图，如果你能从一个点开始，穿过每一边一次，只回到起点一次，那么它就叫做欧拉图。欧拉给出并证明了判断欧拉图的充要条件定理，并证明了七桥图不是欧拉图。从这个问题中我们可以看出：图：图用点代表每一个事物，用边代表每一个事物之间的二元关系。因此，图是研究集合上二元关系的工具，也是建立数学模型的重要手段。100多年后，在“七桥”问题之后，图论的研究停滞了100多年。直到1847年，基尔霍夫用“树”图解决了电路理论中联立方程的求解问题。十年后，凯利用“树”图来计算有机化学中的问题。在此期间，两个著名的图论问题盛行：汉密尔顿电路问题和“四色猜想”问题。1856年，英国数学家汉密尔顿设计了一个环游世界的游戏。他在一个正十二面体的20个顶点上标出了20个著名城市的名字，并要求玩家从一个城市开始，经过每个城市一次，并且只经过一次，然后回到起点。9、哈密尔顿电路图、和、和、和、和、和、和、和、和、和、和、和、和、和、和、和、和、和、以及问题1976年，当人们长时间使用至少四种颜色绘制地图时，经过1200多个小时的计算机计算，四色猜想的问题被证明了。 11、5和半个世纪后，在四色猜想问题出现后，图论的研究又停滞了半个世纪，直到科尼利厄斯在1920年写了许多关于图论的论文，并在1936年出版了第一本关于图论的书。此后，图论在理论和应用上取得了很大的进步。特别是，计算机的出现使图论发展迅速。学好图论非常重要。图论是组合数学的一个分支，与群论、矩阵论、集合论、概率论、拓扑学和数值分析等其他数学分支密切相关。图论为包含二元关系的系统提供了一个数学模型，因此它在许多领域变得越来越重要，并在物理、化学、信息学、运筹学等领域取得了丰硕的成果。自20世纪50年代以来，计算机的迅速发展极大地推动了图论的发展，使得图论成为数学领域中发展最快的分支之一。本章研究：1 .无向图和有向图2。路径、环和图的连通性。图4的矩阵表示。最短路径和关键路径14。今天的内容，无向图的一些相关概念和有向图图握手定理子图相关概念图同构15。初步知识，有序产品3336 ab= | xayb 有序对：无序产品：A。是无序产品。e是笛卡儿积的一个子集，它的元素叫做有向边，也叫做边。20，有向图示例，给定有向图D=，其中v=a，b，c，d，e=，。图的一些概念和规则，g表示无向图，但有时g用来指图(无向图或有向图)。d只能代表一个有向图。V(G)和E(G)分别表示G的顶点集和边集。如果| v (g) |=n，则G称为n阶图。如果|V(G)|和|E(G)|都是有限数，那么G被称为有限图。如果边集e (g)=，g被称为零图。此时，如果g是n阶图，g被称为n阶零图，表示为n n。特别是，N1被称为平凡图。在图的定义中，顶点集合v被定义为非空集合，但是在图的操作中，可以产生顶点集合是空集合的操作结果。因此，顶点集为空集的图被定义为空图，空图表示为。22、校准图、非校准图和基础图。图的集合定义转换成图形表示后，通常用ek表示无向边(vi，vj)(或有向边)，顶点或边用字母标注的图称为校准图，否则称为非校准图。有向边变为无向边的无向图称为原图的基图。很容易知道校准图和非校准图可以相互转换。任何无向图G都可以通过在每条边上添加箭头来获得。23，关联和关联时间，环，孤立点，设g=是无向图，ek=(vi，vj) e，调用vi，vj ek的端点，ek和vi或ek和VJ相互关联。如果vivj，则ek和vi或ek和vj的相关数称为1。如果vi=vj，ek和vi之间的相关数称为2，ek称为环。如果vlvi和vlvj，则任何vlV被认为具有0的ek和vl的相关性。24，关联和关联时间，环，孤立点，设d=有向图，ek= e，vi，vj为ek的端点。如果vi=vj，则ek称为d中的环。无论在无向图还是有向图中，无穷关联的顶点都称为孤立点。如果et e使得et=(vi，vj)，则vi和vj彼此相邻。如果ek和el具有至少一个公共端点，则ek和el彼此相邻。有方向图d=，vi，vjV，ek，el e。如果et e使et=，则vi称为et的起点，vj是et的终点，vi称为与vj相邻，vj与vi相邻。如果ek的终点是el的起点，则称ek与el相邻。例如，点和边之间的连接数，点和边之间的邻接数，顶点的度数，定义集G=无向图，V V，次数V的和称为边的端点的度数，简称度数，记为dG(v)。当混乱没有发生时，它被简单地记为d(v)。设d=是一个有向图，v v，假设v是边的起点的次数之和是v的度数，表示为d D(v)，简单表示为D(v)。V被用作一条边的端点的次数之和称为V的进入度，它被记录为d-D(v)和简单的d-(v)。称d (v)d-(v)v的度数，并记为d(v)。，29，D(v1)=4d(v2)=4d(v3)=3d(v4)=1d(V5)=0，30，D(v1)=2d(v2)=1d(v3)=3d(v4)=1d(V5)=1，D-(v1)=1d-(v2)=3d-(v3)=0d-(v4)=3d-(V5)=1，D(v1)=3d(v2)=4d(v3)=3d(v4)=4d(V5)=2，31，最大(出/入)度在无向图g中，最大度数3336(g)=最大DG (v) | v v (g)最小度数3336(g)=最小DG (v) | v v (g)在有向图D中，最大输出： (d)=最大DD (v) | v v (d)最小输出：(D)=最小dD (v)|vV(D)最大输入握手定理(图论的基本定理)，定理7.1让图G=是无向图或有向图，v=v1，v2，VN，| e |=m，则任何无向图中每个顶点的度数之和等于边数的两倍。证明了G中的每条边(包括环)都有两个端点，所以在计算G中每个顶点的度数之和时，每条边提供2度。当然，M边总共提供2度。推论：在任何图中，奇数度的顶点数都是偶数。在一个部门的25个人中，有没有可能每个人都同意另外5个人的观点，仅仅因为他们有不同的观点？回答：不可能。考虑一个顶点代表人的图。如果两个人同意，他们可以通过边连接，所以每个顶点都是奇数度。奇数度的图有奇数个，这是不可能的。注：(1)许多离散问题可以用图形模型来解决。(2)为了建立一个图形模型，需要决定顶点和边分别代表什么。(3)在图模型中，边通常代表两个顶点之间的关系。34，握手定理，定理7.2有向图D=，v=v1，v2，VN，| e |=m，然后，35度序列，设g=n阶无向图，v=v1，v2，VN，称为d(v1)，d(v2)，对于顶点标定的无向图，它的度序列是唯一的。相反，对于给定的非负整数列d=D1，D2，如果存在v=v1，v2，VN作为顶点集，使得d (vi)=di，那么d是可图解的。特别是，如果得到的图是一个简单的图，那么D就是简单的图。类似地，让d=n阶有向图，v=v1，v2，vn，称为d (v1)，d (v2)，, d(vn)作为d的度序列，也称为d(v1)，d(v2)，, d (vn)和d-(v1)，d-(v2)，, d-(vn)分别作为d的度列和度列。例如，根据顶点的校准顺序，度数序列是4，4，2，1，3。例如，按字母顺序，度序列：5，3，3，3度列外：4，0，2，1度列内：1，3，1，2，38，(4，4，3，1，0)(3，4，3，4，2)，练习：39，图解的一个必要和充分条件，该定理设置非负整数列d=(D1，d2，如果并且仅当它被证明是必要的，那么d是可图表化的。握手定理清楚地证明了这一点。充足。根据已知条件，d中存在偶数奇数度点。奇数度点连接到两个点之间的一侧，其余点通过环实现。(3，3，2，3)，(5，2，3，1，4)可以是图的度序列吗？为什么？已知图g中有10条边和4个3度顶点，其他顶点的度数小于或等于2。g中有多少个顶点？为什么？解决方案：1 .由于这两个序列中奇数度顶点的个数是奇数，从握手定理的推导中可以看出，它们都不能成为图的度序列。2.显然，当图G中剩余顶点的度数为2时，图G的顶点数最少。让G图至少有x个顶点。根据握手定理，34 2(x-4)=210解：x=8，所以G至少有8个顶点。41，简单图和多重图，在无向图中定义，如果有一个以上的无向边与一对顶点相关联，这些边称为平行边，平行边的数量称为多重性。在有向图中，如果有多个有向边与一对顶点相关联，并且这些边的起点和终点相同(即它们的方向相同)，则这些边称为平行边。有平行边的图称为多重图。既不包含平行边也不包含环的图称为简单图。42，简单图和多重图例子，43，完全图，定义7.7让G是一个n阶无向简单图。如果G中的每个顶点与其他n-1个顶点相邻，则G被称为n阶无向完全图，缩写为n阶完全图，并表示为Kn(n1)。假设D是一个N阶有向简单图。如果D中的每个顶点都与剩余的n-1个顶点和剩余的n-1个顶点相邻，那么D被称为N阶有向完全图。假设D是一个n阶有向简单图。如果D的基图是n阶无向完全图Kn，那么D被称为n阶竞赛图。44，完全图例子，n阶无向完全图有n(n-1)/2n阶无向完全图有n (n-1) n阶锦标赛有n(n-1)/2，K5，3阶无向完全图，4阶锦标赛图，45，正则图，定义G为n阶无向简单图，如果vV(G)，都有d (v)=k，则G称为k-正则图。例如，n阶零图是0-正则图，n阶无向完全图是(n-1)-正则图Petersen图是3-正则图，这表明在n阶k-正则图中，边数m=kn/2。当k是奇数时，n必须是偶数。46，子图，定义并设置g=，g=为两个图(两者都是无向图或两者都是有向图)。如果VV和EE，那么g是g的子图，g是g的母图，如果VV或EE，那么g被表示为GG.那么g被称为g的真子图。如果v=v，那么g被称为g的生成子图。让E1E和E1 被称为g的E1导出子图，其将E1作为边集，将与E1中的边相关联的顶点集V1作为顶点集，并被表示为GE1。47，在上图中，(2)和(3)都是(1)的子图；(3)生成子图；(5)和(6)是(4)的子图；(5)生成子图；例如，在上图中，设G为(1)中的数字，V1=a，b，c，则V1的派生子图GV1为(2)中的数字。以E1=E1，E3为例，E1的派生子图GE1显示在(3)的图中。49，补图，定义7.9设G=是一个N阶的无向简单图，取V为顶点集，取所有为边集，使G成为一个完全图的加边集Kn，称为G的补图，表示为G。(1)是自补图(2)和(3)是补图，并且(50)在下图中，(1)是(2)的补图，当然(2)也是(1)的补图，即，(1)和(2)是补图。同样，(3)和(4)是互补图。图的同构。在图论的研究中，我们更关心的是图的结构，它与顶点和边的具体元素或图的绘制无关。为此，我们引入同构的概念。52，图同构，定义7.10:来设置两个无向(有向)图G1=，G2=，如果有双射f:V1V2，它满足U V 1，如果v v1，e=(u，v) e1e=(f (u)，f (v) E2 (e= e1e= E2)且e和e 的重数相同，则G1和G2同构如果把G1G2看作一个说明：同构的图，它的图论性质完全相同，53，图的同构，54，55，(2) (3) (4) (5)和(6)是不同的结构。因为在(6)中有三个不相邻的顶点，