第七章图论

图论Р第七章Р第七章图论Р第七章图论Р第七章图论Р第七章图论Р1/1/2018Р1Р7.2 路与回路Р哥尼斯堡七桥问题Р能否从河岸或小岛出发,通过每一座桥,且仅通过一次回到原地?Р问题Р1/1/2018Р2Р第七章图论Р本章主要内容Р图的基本概念?路与回路?图的矩阵表示?欧拉图与汉密尔顿图?平面图?对偶图与着色?树与生成树?根树及其应用Р1/1/2018Р3Р第七章图论Р7.1 图的基本概念Р图可直观地表示离散对象之间的相互关系,研究它们的共性和特性,以便解决具体问题。?一个图是由一些结点和连接两结点间的连线组成,至于连线的长短及结点的位置是无关紧要的.Р1/1/2018Р4Р7.1 图的基本概念Р下面表示的是同一个图Р1/1/2018Р5Р7.1 图的基本概念Р本节的主要内容Р图的术语? 完全图与偶图? 子图与补图? 图的同构Р1/1/2018Р6Р7.1 图的基本概念Р图的术语Р图?无向图、有向图?邻接和关联?结点的度数?简单图、多重图Р1/1/2018Р7Р7.1 图的基本概念Р定义1 图Р一个图是一个三元组<V(G),E(G), G>其中?V(G) 是一个非空的结点集合?E(G) 是边集合?G 是从边集合 E 到结点无序偶(有序偶)集合上的函数Р1/1/2018Р8Р7.1 图的基本概念Р例Р1/1/2018Р9Р7.1 图的基本概念Р图(续)Р若把图中的边 ei 看作总是与两个结点关联,则一个图可简记为 G =< V, E > , 其中?V —非空点集?E —连接结点的边集Р1/1/2018Р10Р7.1 图的基本概念