离散数学-图论121张课件

第8章图论(GraphTheory第八章图论(GraphTheory)81图的基本概念(Graph)82路与图的连通性(waks&ConnectivityofGraphs83图的矩阵表示(MatrixNotationofGraph)84最短链与关键路(Minimalpath)85欧拉图与哈密尔顿图(ulerianGraph&Hamilton-ianGraph8.6平面图(PlanarGraph87树与生成树(TreesandSpanningTrees)8.8二部图(bipartitegraph)第8章图论(GraphTheory1第8章图论(GraphTheory8.1图的基本概念图81.1哥尼斯堡七桥问题第8章图论(GraphTheory2第8章图论(GraphTheory81图的基本概念8.1.1图1图的定义现实世界中许多现象能用某种图形表示这种图形是由一些点和一些连接两点间的连线所组成。【例811】a,b,c,d4个篮球队进行友谊比赛。为了表示4个队之间比赛的情况,我们作出图8,11的图形在图中4个小圆圈分别表示这4个篮球队,称之为结点如果两队进行过比赛,则在表示该队的两个结点之间用条线连接起来,称之为边。这样利用一个图形使各队之间的比赛情况一目了然。第8章图论(GraphTheory3第8章图论(GraphTheory81图的基本概念如果图811中的4个结点a,b,c,d分别表示4个人,当某两个人互相认识时,则将其对应点之间用边连接起来。这时的图b又反映了这4个人之e间的认识关系。图811第8章图论(GraphTheory4第8章图论(GraphTheory81图的基本概念定义811一个图G是一个序偶〈VG),E(G)〉,记为G=〈V(G),E(G)。其中VG是非空结点集合,E(G)是边集合,对E(G中的每条边,有VG)中的结点的有序偶或无序偶与之对应。若边e所对应的结点对是有序偶(a,b〉,则称e是有向边。a叫边e的始点b叫边e的终点统称为e的端点。若边e所对应的结点对是无序偶ab),则称e是无向边。这时统称e与两个结点a和b互相关联。第8章图论(GraphTheory5第8章图论(GraphTheory81图的基本概念我们将结点a、b的无序结点对记为a,b),有序结点对记为(a,b)。一个图G可用一个图形来表示且表示是不唯一的【例81.2】设G=〈VG,E(G),其中V(G)={a,b升,EG)={e1y234P5627},e1=(a,b),e2=(anc),e3=(b,d,e4=(b,c),es=(d4),e6=(a,d)ey=(b,b)。则图G可用图8.12a)或(b表示。第8章图论(GraphTheory6第8章图论(GraphTheory8.1图的基本概念ae?(a)图812第8章图论(GraphTheory7第8章图论(GraphTheory81图的基本概念2.图G的结点与边之间的关系邻接点:同一条边的两个端点。孤立点:没有边与之关联的结点邻接边:关联同一个结点的两条边。孤立边:不与任何边相邻接的边自回路(环):关联同一个结点的一条边((ν,ν)或(ν,p))平行边(多重边:关联同一对结点的多条边。第8章图论(GraphTheory8第8章图论(GraphTheory8.1图的基本概念如例8.1.1中的图,结点集V={a,b,c,d},边集Ee1,e2,e3,e4,es},其中(a,b)(a,d)),es=(c,d)。d与a、d与c是邻接的,但d与b不邻接,边e3与es是邻接的。a第8章图论(GraphTheory9第8章图论(GraphTheory8.1图的基本概念【例813】设图G=〈V,E〉如图10.1.3所示。这里V={v1,v2,v3},E={1e其中e1=(v1,p2),e2=(v1,v3De313图8.1在这个图中,e3是关联同一个结点的一条边即自回路;边e4和e都与结点v2、v3关联,即它们是平行边第8章图论(GraphTheory10离散数学-图论121张课件11离散数学-图论121张课件12离散数学-图论121张课件13离散数学-图论121张课件14离散数学-图论121张课件15离散数学-图论121张课件16离散数学-图论121张课件17离散数学-图论121张课件18离散数学-图论121张课件19离散数学-图论121张课件20离散数学-图论121张课件21离散数学-图论121张课件22离散数学-图论121张课件23离散数学-图论121张课件24离散数学-图论121张课件25离散数学-图论121张课件26离散数学-图论121张课件27离散数学-图论121张课件28离散数学-图论121张课件29离散数学-图论121张课件30离散数学-图论121张课件31离散数学-图论121张课件32离散数学-图论121张课件33离散数学-图论121张课件34离散数学-图论121张课件35离散数学-图论121张课件36离散数学-图论121张课件37离散数学-图论121张课件38离散数学-图论121张课件39离散数学-图论121张课件40离散数学-图论121张课件41离散数学-图论121张课件42离散数学-图论121张课件43离散数学-图论121张课件44离散数学-图论121张课件45离散数学-图论121张课件46离散数学-图论121张课件47离散数学-图论121张课件48离散数学-图论121张课件49离散数学-图论121张课件50离散数学-图论121张课件51离散数学-图论121张课件52离散数学-图论121张课件53离散数学-图论121张课件54离散数学-图论121张课件55离散数学-图论121张课件56离散数学-图论121张课件57离散数学-图论121张课件58离散数学-图论121张课件59离散数学-图论121张课件60离散数学-图论121张课件61离散数学-图论121张课件62离散数学-图论121张课件63离散数学-图论121张课件64离散数学-图论121张课件65离散数学-图论121张课件66离散数学-图论121张课件67离散数学-图论121张课件68离散数学-图论121张课件69离散数学-图论121张课件70离散数学-图论121张课件71离散数学-图论121张课件72离散数学-图论121张课件73离散数学-图论121张课件74离散数学-图论121张课件75离散数学-图论121张课件76离散数学-图论121张课件77离散数学-图论121张课件78离散数学-图论121张课件79离散数学-图论121张课件80离散数学-图论121张课件81离散数学-图论121张课件82离散数学-图论121张课件83离散数学-图论121张课件84离散数学-图论121张课件85离散数学-图论121张课件86离散数学-图论121张课件87离散数学-图论121张课件88离散数学-图论121张课件89离散数学-图论121张课件90离散数学-图论121张课件91离散数学-图论121张课件92离散数学-图论121张课件93离散数学-图论121张课件94离散数学-图论121张课件95离散数学-图论121张课件96离散数学-图论121张课件97离散数学-图论121张课件98离散数学-图论121张课件99离散数学-图论121张课件100离散数学-图论121张课件101离散数学-图论121张课件102离散数学-图论121张课件103离散数学-图论121张课件104离散数学-图论121张课件105离散数学-图论121张课件106离散数学-图论121张课件107离散数学-图论121张课件108离散数学-图论121张课件109离散数学-图论121张课件110离散数学-图论121张