《离散数学》1-2图的基本研讨.ppt

一个人要把他带的一条狗，一只羊和一袋菜用一条小船摆渡到河的对岸。由于这个船非常小，每次摆渡这个人只能将狗、羊和菜之一带过去。但是，不能把狗和羊，也不能把羊和菜单独的留在河的同一岸。 为了回答这个问题，我们首先建立一个集合，这个集合以被允许出现的局面为元素。例如，人、狗、羊和菜在河的开始一岸我们记为元素（人狗羊菜，0），元素（0，人狗羊菜）表示到了河的另一岸。而（人狗羊，菜），（狗羊，人菜），…表示允许出现的各种局面。对于任意的两种局面，若这个人进行一次摆渡能从一个局面变为另一个局面，这两个局面之间就有关系R，我们得到了集合上的一个二元关系。 用一个图表示这件事。在这个图中每一个局面对应一个图的顶点，若两个局面之间有关系，则用一条线段把这两个局面对应的顶点相连接。 一个集合就是一些不同对象的总体。 然而有许多时候，我们遇到的不是不同对象的总体。例如，我们谈及一个班级学生名字的总体，可是，可能有两个或多个学生同名。 生成=？ 补图是相当于完全图来说的。 此定理的结论比较明显，可以作如下说明： 任何一个图，在其中增加一条边，则总度数增加2度，从没有边开始，由于没有一条边，故总度数为0，然后把|E|条边分别加进图中，总度数增加为2|E|，所以，结论成立。 此定理的结论比较明显，可以作如下说明： 任何一个图，在其中增加一条边，则总度数增加2度，从没有边开始，由于没有一条边，故总度数为0，然后把|E|条边分别加进图中，总度数增加为2|E|，所以，结论成立。 设G=（V，E） 是一个无向图，可以认为每一个顶点对应一个城市，二个城市之间除有边相邻接以外，还有一个通路的问题。 （1）我们往往用一个顶点的序列来表示一条通路。 （2）一条通路也可以用边的序列来表示。 设G=（V，E） 是一个无向图，可以认为每一个顶点对应一个城市，二个城市之间除有边相邻接以外，还有一个通路的问题。 （1）我们往往用一个顶点的序列来表示一条通路。 （2）一条通路也可以用边的序列来表示。 一条回路的长度，就是这条回路经过的边的条数。 一条回路的长度，就是这条回路经过的边的条数。 无向图中,顶点之间的连通关系是等价关系。 事实上，由定理1的推论知，存在一条长度最多为n-1的通路，也即存在k?N，1≤k≤n-1，有aij(k)=1。 故结论成立。 狄杰斯特拉算法 狄杰斯特拉算法 理解:全局最优=局部最优中的最优 也许有人说还有一种，就是一条从 v0到t1，再回到 T中某一顶点t’，由t’到t中间不经P中其余点。实际上，从v0到t1再到 t’的这条通路一定不短于从v0到t’的最短通路，而由作法可知从v0 到t’的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从 v0到t’的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。 也许有人说还有一种，就是一条从 v0到t1，再回到 T中某一顶点t’，由t’到t中间不经P中其余点。实际上，从v0到t1再到 t’的这条通路一定不短于从v0到t’的最短通路，而由作法可知从v0 到t’的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从 v0到t’的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。 */81 无向图的关联矩阵 设 G=(V,E)是一个无向图，|V|=n，|E|=m， V={v1,v2, ?,vn}，E={e1,e2, ?,em}， 则有n×m 阶矩阵 ， M(G)=(mij)n×m 其中: 称 M(G)=(mij)n×m为图G的关联矩阵。 mij= 1 如顶点vi与边ei关联 0 如顶点vi与边ei关联 */81 例 e1 e2 e3 e4 e5 e6 e7 e8 v1 1 1 1 0 1 0 0 0 v2 1 0 0 1 0 0 0 0 v3 0 0 1 1 0 0 1 1 v4 0 0 0 0 1 1 0 1 v5 0 1 0 0 0 1 1 0 M(G)= 特点： 1、行和为度数 2、列和为2 3、所有元素的和为总 度数 4、平行边列相同 有向图的关联矩阵 * 定义 设无环有向图D=V,E, V={v1, v2, …, vn}, E={e1, e2,