图的基本概念

22:061第一部分图与网络第一章图论基本知识数学分支，可以解决线性规划等问题图的基本概念图有向图无向图图的矩阵表示关联矩阵邻接矩阵*子图顶点、边（弧）、链、路、圈（回路）、连通性、同构等*树生成树、最小生成树生成子图图运算22:062第一节图的定义图论是近数十年来得到蓬勃发展的一个数学分支，它的理论与方法在许多领域中得到广泛的应用并取得了丰硕的成果成为运筹学一个重要分支。线性规划、整数规划、运输问题等等，有时也可以用图论的方法来构造模型并求解，而且由于图的结构的直观性，更有助于我们分析问题和描述问题，何况有些研究对象，如交通网，它本身就是一个大网络，用图论的方法研究更方便。本节主要介绍关于无向图和有向图的定义等基本概念22:0631.1图引例1：哥尼斯堡七桥问题引例2：交通网络问题北京郑州西安成都22:064引例:若出发点x1可运送货物到接收点y1和y2，发送点x2可运送货物到接收点y1、y2、y3，用点和线表示发送点、接收点以及它们之间的关系，得到下图：x1x2y3y2y1对象关系直观描述：语言描述：表示具体事物的点（顶点）集合和表示事物之间关系的边集合组成图对象（1）G={V,E}，V={v1,v2,···vn},E={e1,e2,···en}（2）G={(eij,(vi,vj))|i,j=1···n}数学描述：22:0651.1.1无向图1．无向图设V是一个有n个顶点的非空集合，V={v1,v2,…,vn},E是一个有m条边的集合，E={e1,e2,…,em}，E中任一条边e是V的一个无序元素对[u,v]（或vi,vj。i≠j）（这里u≠v），则V和E这两个集合组成了一个无向图，记G=（V，E）。vi和vj称为边eij端点，eij称为vi,vj的关联边，vi与vj为相邻顶点。一、无向图定义根据边有没有方向，将图分为无向图和有向图，下面分别讲解：v1v2v5v3v422:066示例：无向图G=(V,E)，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6,e7}G={(e12,(v1,v2)),(e14,(v1,v4)),(e15,(v1,v5)),(e24,(v2,v4)),(e34,(v3,v4)),(e45,(v4,v5)),(e51,(v5,v1))}v4v1v2v5v31.1.1无向图22:0671.1.1无向图二、无向图术语平行边（多重边）：两边有一样的端点，如e15和e51简单图：图中无平行边完备图：图中任意两个端点之间有且仅有一条边链：两个端点之间的连接路径一个链的起始端点不为同一个称为开链，否则为闭链（圈）初等链：一个链中无重复的顶点。也称为路。回路（初等圈）一个圈中除第一和最后顶点外各点均不相同。或者说闭合的路称为回路。v4v1v2v5v3简单链：一个链中无重复的边。22:0681.1.2有向图设顶点的非空集合V={v1,v2,…,vn},边的集合E={e1,e2,…,em}，E中任一条边e是V的一个有序元素对[u,v]（这里u≠v），则V和E这两个集合组成了一个有向图，记作有向图G=（V，E）。u称为起点，v称为终点,有向图中，边e(u,v)称为连接顶点u和v的弧。一、有向图定义v1v2v5v4v322:069二、有向图术语完备图：图中任意两个端点之间恰好有两条边（（u,v）和（v，u））。平行边：两边有一样的起终点简单图：图中无平行边基本图：去掉有向图方向就能得到一个无向图初等链：顶点都不相同的链（和基本图中的初等链相同）。1.1.2有向图e2v4v1v2v5v4v3e1e3e5e7e8e6e422:06101.1.3其它术语网络：如果图的边上带有数量指标（或称为权值），这样的图称为网络.北京郑州西安成都1200800140050060022:0611连通图：图（无向）中任意两点都连通称为连通图，否则称为分割图。图的可达性（有向图）：若图G中从顶点u到v之间存在单向路径，则称u可达v。强连通图：若图G内任两点之间相互可达，则称图G为强连通图。1.1.3其它术语v4v1v2v5v3v6v1v2v5v4v3e1e3e5e7e8e6e422:0612欧拉链：连通无向图G中，如果存在经过G中每条边一次且仅一次的链，称为欧拉链。欧拉图:起点和终点相同的欧拉链称为图G的欧拉环游。如果图G中存在一条欧拉环游，称图G为欧拉图。1.1.3其它术语v4v1v2v3v5v4v1v2v322:0613子图：设G1=(V1，E1)，G=(V，E)，若V1V，E1E，则称G1为G的子图，即G1G。生成子图：当V1=V，E1E，则称G1为G的生成子图（支撑子图）。v1v2v5v4v3v1v2v5v4v1v2v5v4v31.1.3其它术语22:0614树：无圈的无向连通图G称为树。记为T=（V，E）。树T的六个等价定义：1、T连通且无回路。2、T无回路且只有n-1条边。3、T连通且有n-1条边4、T无回路，但不相邻的两个顶点之间联一条边，恰得到一个回路。5、T连通，但取掉任一条边后就不连通了。6、T的任意两个顶点之间恰有一条初等链。1.1.3其它术语22:0615生成树：如果树满足称T为G的生成树（T为G的生成子图又是一棵树）。亦即图G中能将各顶点以最少边数连接起来的树。一个无向图可有若干个生成树。)()(),()(GETEGVTV1.1.3其它术语v4v1v2v3v5v4v1v2v3v522:0616图的同构：若图G=（V，E）与G’=（V’，E’）的顶点集合V和V’以及边的集合E与E’之间在保持关联关系的条件下一一对应，则称图G和G’为同构的。（简单说，若两个图顶点和边都能对应上称为同构图）1.1.3其它术语vcvavbvdv4v1v2v322:0617图的顶点阶数：无向图G=（V，E）中与顶点v关联的边数称为顶点的阶数，记作δ(v)。Δ(v)为偶数，称v为偶阶顶点；δ(v)为奇数称为奇阶顶点。两个常用定理：定理1任一图中所有顶点的阶数之和为偶数。定理2任一图中所有奇阶顶点的个数必为偶数。1.1.3其它术语22:06181.2图的矩阵表示一、无向图的矩阵表示矩阵数值aij规则：aij=0，顶点vi与边eij不关联1，顶点vi与边eij关联1.无向图的关联矩阵无向图的关联矩阵形式：顶点边e1e2···ei···env1.vi.vnaij22:0619示例：特点：目的：关联矩阵无向图1、矩阵第i行中1的个数就是与顶点vi相关的边的数量2、矩阵中j列中1的个数恒为2，因为每边只有2个端点v1v2v5v3v4e12e14e15e24e34e45e51v1v2v3v4v511100011001000000010001011100010011关联矩阵22:06202.无向图的邻接矩阵无向图的邻接矩阵形式：顶点顶点v1v2···vi···vnv1.vi.vnaij矩阵数值aij规则：aij表示顶点vi和vj之间边的数量示例：特点：1、邻接矩阵是对称矩阵2、邻接矩阵比关联矩阵小v1v2v3v4v5v1v2v3v4v50101210010000101110020000邻接矩阵22:0621二、有向图的矩阵表示aij=0，顶点vi与边eij不关联1，顶点vi为边eij起点1.有向图的关联矩阵与无向图的关联矩阵形式一样，但数值aij规则为：-1，顶点vi为边eij终点v1v2v5v4v3示例：特点：矩阵中j列中的元素之和为0e12e14e15e24e34e45e51v1v2v3v4v5111000-1-100100000001000-10-1-11000-100-11关联矩阵22:06222.有向图的邻接矩阵邻接矩阵形式以及矩阵数值aij规则与无向图一样v1v2v3v4v5v1v2v3v4v50101100010000100000110000示例：特点：1、矩阵第i行元素之和就是以顶点vi为起点的有向边的数量2、矩阵第j列元素之和就是以顶点vj为终点的有向边的数量v1v2v5v4v322:0623例题1：给出无向图的点集和边集，及关联关系，作出几何图。V={v1,v2,v3,v4,v5},E={e1,e2,e3,e4,e5,e6,e7}第一节图的定义22:0624第一节图的定义给出图G=（V，E），就可以作出它的几何图。例题1.给出无向图的点集和边集，及关联关系，作出几何图。V={v1,v2,v3,v4,v5},EmE={e1,e2,e3,e4,e5,e6,e7}关联关系如下表所示：Ee1e2e3e4e5e6e7e=[u,v][v1,v2][v1,v5][v2,v4][v1,v4][v4,v3][v5,v4][v1,v5]v1e1v2e2e7v5e4e3e6v4e5v3