离散数学-图论课件

第8章图论(GraphTheory第八章图论(GraphTheory)81图的基本概念(Graph)82路与图的连通性(waks&ConnectivityofGraphs83图的矩阵表示(MatrixNotationofGraph)84最短链与关键路(Minimalpath)85欧拉图与哈密尔顿图(ulerianGraph&Hamilton-ianGraph8.6平面图(PlanarGraph87树与生成树(TreesandSpanningTrees)8.8二部图(bipartitegraph)第8章图论(GraphTheory8.1图的基本概念图81.1哥尼斯堡七桥问题第8章图论(GraphTheory81图的基本概念8.1.1图1图的定义现实世界中许多现象能用某种图形表示这种图形是由一些点和一些连接两点间的连线所组成。【例811】a,b,c,d4个篮球队进行友谊比赛。为了表示4个队之间比赛的情况,我们作出图8,11的图形在图中4个小圆圈分别表示这4个篮球队,称之为结点如果两队进行过比赛,则在表示该队的两个结点之间用条线连接起来,称之为边。这样利用一个图形使各队之间的比赛情况一目了然。第8章图论(GraphTheory81图的基本概念如果图811中的4个结点a,b,c,d分别表示4个人,当某两个人互相认识时,则将其对应点之间用边连接起来。这时的图b又反映了这4个人之e间的认识关系。图811第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章图论(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章图论(GraphTheory8.1图的基本概念ae?(a)图812第8章图论(GraphTheory81图的基本概念2.图G的结点与边之间的关系邻接点:同一条边的两个端点。孤立点:没有边与之关联的结点邻接边:关联同一个结点的两条边。孤立边:不与任何边相邻接的边自回路(环):关联同一个结点的一条边((ν,ν)或(ν,p))平行边(多重边:关联同一对结点的多条边。第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章图论(GraphTheory8.1图的基本概念【例813】设图G=〈V,E〉如图10.1.3所示。这里V={v1,v2,v3},E={1e其中e1=(