离散数学-图论基础.ppt

文档介绍：第七章图论基础Graphs*第一节图的基本概念一个图G定义为一个三元组:G=<V,E,Φ>V——非空有限集合,V中的元素称为结点(node)或顶点(vertex)E——有限集合(可以为空),E中的元素称为边(edge)Φ——从E到V的有序对或无序对的关联映射(associativemapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)*图的基本概念图G=<V,E,Φ>中的每条边都与图中的无序对或有序对联系若边eE与无序对结点[va,vb]相联系,即Φ(e)=[va,vb](va,vbV)则称e是无向边(或边、棱)若边eE与有序对结点<va,vb>相联系,即Φ(e)=<va,vb>(va,vbV)则称e是有向边(或弧)va是e的起始结点,vb是e的终结点v1v2v3(a)v1v2v3(b)v1v2v3(c)*图的基本概念若va和vb与边(弧)e相联结,则称va和vb是e的端结点va和vb是邻接结点,记作:vaadjvb(adjoin)也称e关联va和vb,或称va和vb关联e若va和vb不与任何边(弧)相联结,则称va和vb是非邻接结点,记作:vanadjvb关联同一个结点的两条边(弧),称为邻接边(弧)关联同一个结点及其自身的边,称为环(cycle),环的方向没有意义v1v2v3(a)v1v2v3(b)v1v2v3(c)*图的基本概念若将图G中的每条边(弧)都看作联结两个结点则G简记为:<V,E>每条边都是弧的图,称为有向图(directedgraph)(如图b)每条边都是无向边的图,称为无向图(undirectedgraph)(如图a)有些边是弧,有些边是无向边的图,称为混合图(如图c)v1v2v3(a)v1v2v3(b)v1v2v3(c)*图的基本概念若图G中的任意两个结点之间不多于一条无向边(或不多于一条同向弧),且任何结点无环,则称G为简单图(如图c)若图G中某两个结点之间多于一条无向边(或多于一条同向弧),则称G为多重图(如图a,b)两个结点间的多条边(同向弧)称为平行边(弧),平行边(弧)的条数,称为重数v1v2v3(a)v1v2v3(b)v1v2v3(c)*图的基本概念在多重图的表示中,可在边(弧)上标注正整数,以表示平行边(弧)的重数把重数作为分配给边(弧)上的数,称为权(weight)将权的概念一般化,使其不一定是正整数,则得到加权图的概念:给每条边(弧)都赋予权的图,叫做加权图(weightedgraph)记作G=<V,E,W>,W是各边权之和v1v2v3(a)v1v2v3(b)v1v2v3(c)1111112211*图的基本概念在无向图G=<V,E>中,V中的每个结点都与其余的所有结点邻接,即 (va)(vb)(va,vbV[va,vb]E),如图(a)pletegraph),记作K|V|若|V|=n,则|E|=C=n(n-1)/2v1v2v3(a)v1v2v3(b)2n*图的基本概念在有向图G=<V,E>中,V中的任意两个结点间都有方向相反的两条弧,即(va)(vb)(va,vbV<va,vb>E∧<vb,va>E),如图(a)则称该图为有向完全图,记作K|V|若|V|=n,则|E|=P=n(n-1)v1v2v3(a)v1v2v3(b)2n*图的基本概念在图G=<V,E>中,若有一个结点不与其他任何结点邻接则该结点称为孤立结点,如图(a)中的v4仅有孤立结点的图,称为零图,零图的E=,如图(b)仅有一个孤立结点的图,称为平凡图(trivialgraph),如图(c)v1v2v3(a)v1v2v3(b)v1(c)v4