图的基本概念精品文稿.ppt

《图的基本概念精品文稿.ppt》由会员分享，可在线阅读，更多相关《图的基本概念精品文稿.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的基本概念第1页，本讲稿共25页2023/2/11第一部分 图与网络 第一章 图论基本知识数学分支，可以解决线性规划等问题数学分支，可以解决线性规划等问题图图的的基基本本概概念念图图有向图有向图无向图无向图图的矩阵表示图的矩阵表示关联矩阵关联矩阵邻接矩阵邻接矩阵*子图子图顶点、边（弧）、链、路、圈（回顶点、边（弧）、链、路、圈（回路）、连通性、同构等路）、连通性、同构等*树树 生成树、最小生成树生成树、最小生成树生成子图生成子图图运算图运算第2页，本讲稿共25页2023/2/12第一节 图的定义图图论论是是近近数数十十年年来来得得到到蓬蓬勃勃发发展展的的一一个个数数学学分分支支，它它的的理理

2、论论与与方方法法在在许许多多领领域域中中得得到到广广泛泛的的应应用用并并取取得得了了丰丰硕硕的的成成果果成成为为运运筹筹学学一一个重要分支。个重要分支。线线性性规规划划、整整数数规规划划、运运输输问问题题等等等等，有有时时也也可可以以用用图图论论的的方方法法来来构构造造模模型型并并求求解解，而而且且由由于于图图的的结结构构的的直直观观性性，更更有有助助于于我我们们分分析析问问题题和和描描述述问问题题，何何况况有有些些研研究究对对象象，如如交交通网，它本身就是一个大网络，用图论的方法研究更方便。通网，它本身就是一个大网络，用图论的方法研究更方便。本节主要介绍关于无向图和有向图的定义等基本概念本节

3、主要介绍关于无向图和有向图的定义等基本概念第3页，本讲稿共25页2023/2/131.1 图引例引例1：哥尼斯堡七桥问题：哥尼斯堡七桥问题引例引例2：交通网络问题：交通网络问题北京北京郑州郑州西安西安成都成都第4页，本讲稿共25页2023/2/14引例引例:若出发点若出发点x1可运送货物到接收点可运送货物到接收点y1和和y2，发送点，发送点x2可运送货可运送货物到接收点物到接收点y1、y2、y3，用点和线表示，用点和线表示发送点、接收点以及它们发送点、接收点以及它们之间的关系之间的关系，得到下图：，得到下图：x1x2y3y2y1对象对象关系关系直观描述：直观描述：语言描述：语言描述：表示具体事

4、物的点（顶点）集合和表示具体事物的点（顶点）集合和表示事物之间关系的边集合组成图表示事物之间关系的边集合组成图对象对象（1）G=V,E，V=v1,v2,vn,E=e1,e2,en（2）G=(eij,(vi,vj)|i,j=1 n数学描述：数学描述：第5页，本讲稿共25页2023/2/151.1.1 无向图1 1无向图无向图设设V V是一个有是一个有n n个顶点的非空集合，个顶点的非空集合，V=vV=v1 1,v,v2 2,v,vn n,E,E是一个有是一个有m m条边的集合，条边的集合，E=E=e e1 1,e,e2 2,e,em m ，E E中任一条边中任一条边e e 是是V V的一个的一个

5、无序元素对无序元素对u,vu,v（或（或v vi i,v,vj j。i i j）（这里）（这里uvuv），则），则V V和和E E这两个集合组成了一个无向图，记这两个集合组成了一个无向图，记G=G=（V V，E E）。）。v vi i和和v vj j称为边称为边e eijij端点，端点，e eijij称为称为v vi i,v,vj j的关联边，的关联边，v vi i与与v vj j为为相邻顶点。相邻顶点。一、无向图无向图定义根据边有没有方向，将图分为无向图和有向图，下面分别讲解：v1v2v5v3v4第6页，本讲稿共25页2023/2/16示例：无向图G=(V,E)，其中V=v1,v2,v3,v

6、4,v5，E=e1,e2,e3,e4,e5,e6,e7G=(e12,(v1,v2),(e14,(v1,v4),(e15,(v1,v5),(e24,(v2,v4),(e34,(v3,v4),(e45,(v4,v5),(e51,(v5,v1)v4v1v2v5v31.1.1 无向图第7页，本讲稿共25页2023/2/171.1.1 无向图二、无向图术语平行边（多重边）：两边有一样的端点，如e15和e51简单图：图中无平行边完备图：图中任意两个端点之间有且仅有一条边链：两个端点之间的连接路径一个链的起始端点不为同一个称为开链，否则为闭链（圈）初等链：一个链中无重复的顶点。也称为路。回路（初等圈）一个圈

7、中除第一和最后顶点外各点均不相同。或者说闭合的路称为回路。v4v1v2v5v3简单链：一个链中无重复的边。第8页，本讲稿共25页2023/2/181.1.2 有向图设顶点的非空集合设顶点的非空集合V=vV=v1 1,v,v2 2,v,vn n,边的集合边的集合 E=E=e e1 1 ,e,e2 2,e,em m ，E E中任一条边中任一条边e e 是是V V的一个的一个有序元素对有序元素对u,vu,v（这里（这里uvuv），则），则V V和和E E这两个集合组成了一个有向这两个集合组成了一个有向图，记作有向图图，记作有向图G=G=（V V，E E）。）。u u称为起点，称为起点，v v称为终点

8、称为终点,有向图中，边有向图中，边e(u,v)e(u,v)称为连接顶点称为连接顶点u u和和v v的弧。的弧。一、有向图定义v1v2v5v4v3第9页，本讲稿共25页2023/2/19二、有向图术语完备图：图中任意两个端点之间恰好有两条边（u,v）和（v，u）。平行边：两边有一样的起终点简单图：图中无平行边基本图：去掉有向图方向就能得到一个无向图初等链：顶点都不相同的链（和基本图中的初等链相同）。1.1.2 有向图e2v4v1v2v5v4v3e1e3e5e7e8e6e4第10页，本讲稿共25页2023/2/1101.1.3 其它术语网络：如果图的边上带有数量指标（或称为权值），这样的图称为网络

9、.北京北京郑州郑州西安西安成都成都12008001400500600第11页，本讲稿共25页2023/2/111连通图：图（无向）中任意两点都连通称为图（无向）中任意两点都连通称为连通图连通图，否则称为否则称为分割图分割图。图的可达性（有向图）：若图：若图G中从顶点中从顶点u 到到v之间存之间存在单向路径，则称在单向路径，则称u可达可达v。强连通图：若图若图G内任两点之间相互可达，则称图内任两点之间相互可达，则称图G为为强连通图强连通图。1.1.3 其它术语v4v1v2v5v3v6v1v2v5v4v3e1e3e5e7e8e6e4第12页，本讲稿共25页2023/2/112欧拉链：连通无向图G中

10、，如果存在经过G中每条边一次且仅一次的链，称为欧拉链。欧拉图:起点和终点相同的欧拉链称为图G的欧拉环游。如果图G中存在一条欧拉环游，称图G为欧拉图。1.1.3 其它术语v4v1v2v3v5v4v1v2v3第13页，本讲稿共25页2023/2/113子图：设G1=(V1，E1)，G=(V，E)，若V1V，E1 E，则称G1为G的子图，即G1 G。生成子图：当V1=V，E1 E，则称G1为G的生成子图（支撑子图）。v1v2v5v4v3v1v2v5v4v1v2v5v4v31.1.3 其它术语第14页，本讲稿共25页2023/2/114树：无圈的无向连通图G称为树。记为T=（V，E）。树T的六个等价定

11、义：1 1、T T连通且无回路。连通且无回路。2 2、T T无回路且只有无回路且只有n-1n-1条边。条边。3 3、T T连通且有连通且有n-1n-1条边条边4 4、T T无回路，但不相邻的两个顶点之间联一条边，恰得到一个回无回路，但不相邻的两个顶点之间联一条边，恰得到一个回路。路。5 5、T T连通，但取掉任一条边后就不连通了。连通，但取掉任一条边后就不连通了。6 6、T T的任意两个顶点之间恰有一条初等链。的任意两个顶点之间恰有一条初等链。1.1.3 其它术语第15页，本讲稿共25页2023/2/115生成树：如果树满足 称T为G的生成树（T为G的生成子图又是一棵树）。亦即图G中能将各顶点

12、以最少边数连接起来的树。n一个无向图可有若干个生成树。一个无向图可有若干个生成树。1.1.3 其它术语v4v1v2v3v5v4v1v2v3v5第16页，本讲稿共25页2023/2/116图的同构：若图G=（V，E）与G=（V，E）的顶点集合V 和V以及边的集合E与E之间在保持关联关系的条件下一 一对应，则称图G和G为同构的。（简单说，若两个图顶点和边都能对应上称为同构图）1.1.3 其它术语vcvavbvdv4v1v2v3第17页，本讲稿共25页2023/2/117图图的的顶顶点点阶阶数数：无向图G=（V，E）中与顶点v关联的边数称为顶点的阶数，记作(v)。(v)为为偶偶数数，称称v为为偶偶阶

13、阶顶顶点点；(v)为为奇奇数数称称为为奇奇阶阶顶点。顶点。两个常用定理：两个常用定理：定理1 任一图中所有顶点的阶数之和为偶数。定理2 任一图中所有奇阶顶点的个数必为偶数。1.1.3 其它术语第18页，本讲稿共25页2023/2/1181.2 图的矩阵表示一、无向图的矩阵表示矩阵数值aij规则：aij=0，顶点vi与边eij不关联1，顶点vi与边eij关联1.无向图的关联矩阵无向图的关联矩阵形式：顶点边e1 e2 ei env1.vi .vnaij第19页，本讲稿共25页2023/2/119示例：特点：目的：关联矩阵无向图1、矩阵第i行中行中1的个数就是与顶点的个数就是与顶点vi相关相关的边的

14、数量的边的数量2、矩阵中j列中列中1的个数恒为的个数恒为2，因为每边只有2个端点v1v2v5v3v4e12 e14 e15 e24 e34 e45 e51v1 v2v3 v4 v511100011001000000010001011100010011关联矩阵第20页，本讲稿共25页2023/2/1202.无向图的邻接矩阵无向图的邻接矩阵形式：顶点顶点v1 v2 vi vnv1.vi .vnaij矩阵数值aij规则：aij表示顶点表示顶点vi和和vj之间边的数量之间边的数量示例：特点：1、邻接矩阵是对称矩阵对称矩阵2、邻接矩阵比关联矩阵小比关联矩阵小v1 v2 v3 v4 v5v1 v2v3 v

15、4 v50101210010000101110020000邻接矩阵第21页，本讲稿共25页2023/2/121二、有向图的矩阵表示aij=0，顶点vi与边eij不关联1，顶点vi为边eij起点1.有向图的关联矩阵与无向图的关联矩阵形式一样，但数值aij规则为：-1，顶点vi为边eij终点v1v2v5v4v3示例：特点：矩阵中矩阵中j列中的元素之和为列中的元素之和为0e12 e14 e15 e24 e34 e45 e51v1 v2v3 v4 v5111000-1-100100000001000-10-1-11000-100-11关联矩阵第22页，本讲稿共25页2023/2/1222.有向图的邻接

16、矩阵邻接矩阵形式以及矩阵数值aij规则与无向图一样v1 v2 v3 v4 v5v1 v2v3 v4 v50101100010000100000110000示例：特点：1、矩阵第第i行元素之和就是以顶点行元素之和就是以顶点vi为起点的为起点的有向边的数量有向边的数量2、矩阵第第j列元素之和就是以顶点列元素之和就是以顶点vj为终点为终点的有向边的数量的有向边的数量v1v2v5v4v3第23页，本讲稿共25页2023/2/123例例题题1：给给出出无无向向图图的的点点集集和和边边集集，及及关关联联关关系系，作作出出几几何图。何图。V=v1,v2,v3,v4,v5,E=e1,e2,e3,e4,e5,e6,e7 第一节 图的定义第24页，本讲稿共25页2023/2/124第一节 图的定义第25页，本讲稿共25页2023/2/125