(图论)图的基本概念--第一章.ppt

有向图的可达矩阵 定义1.27 设D＝V,E为有向图。V＝{v1,v2,…,vn}，令 pij＝ 1 vi 可达 vj 0 否则 称(pij)n×n为D的可达矩阵，记作P(D)，简记为P。 1.5 图的运算 定义1.28 设G1＝V1,E1，G2＝V2,E2为两个图。 若V1∩V2＝?，则称G1与G2是不交的。 若E1∩E2＝?，则称G1与G2是边不交的或边不重的。 说明：不交的图，必然是边不交的，但反之不真。 图的运算 定义1.29 设G1＝V1,E1，G2＝V2,E2为不含孤立点的两个图（它们同为无向图或同为有向图）。 (1)称以E1∪E2为边集，以E1∪E2中边关联的顶点组成的集合为顶点集的图为G1与G2的并图，记作G1∪G2。 (2)称以E1-E2为边集，以E1-E2中边关联的顶点组成的集合为顶点集的图为G1与G2的差图，记作G1-G2。 (3)称以E1∩E2为边集，以E1∩E2中边关联的顶点组成的集合为顶点集的图为G1与G2的交图，记作G1∩G2。 (4)称以E1⊕E2为边集（为集合之间的对称差运算），以E1⊕E2中边关联的顶点组成的集合为顶点集的图为G1与G2的环和，记作G1⊕G2。 定义1.29的说明 (1)若G1＝G2，则 G1∪G2＝G1∩G2＝G1(G2) G1-G2＝G2-G1＝G1⊕G2＝? 这就是在图的定义中给出空图概念的原因。 (2)当G1与G2边不重时， G1∩G2＝? G1-G2＝G1 G2-G1＝G2 G1?G2＝G1∪G2 (3)图之间环和的定义也可以用并、交、差给出，即 G1⊕G2＝(G1∪G2)-(G1∩G2) 最短路算法 问题：若干个城市被铁路网连通， 任何制定其中的两座城市， 试求这两座城市之间的最近的铁路 图论模型： 城市作为顶点， 仅当两城市有一段铁路， 中途没有其他火车站的将这两个城市连边， 边上赋权。 求任意2个点的最短路 Dijkstra算法 Dijkstra算法能求一个顶点到另一顶点最短路径。它是由Dijkstra于1959年提出的。实际它能出始点到其它所有顶点的最短路径。 Dijkstra算法是一种标号法：给赋权图的每一个顶点记一个数，称为顶点的标号（临时标号，称T标号，或者固定标号，称为P标号）。T标号表示从始顶点到该标点的最短路长的上界；P标号则是从始顶点到该顶点的最短路长。 Dijkstra算法步骤如下： Dijkstra算法 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1 5 1 2 9 3 4 1 3 6 9 2 7 2 1 4 9 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1 5 1 2 9 3 4 1 3 6 9 2 7 2 1 4 9 0 2 8 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1 5 1 2 9 3 4 1 3 6 9 2 7 2 1 4 9 0 2 8 ∞ ∞ 10 ∞ ∞ ∞ ∞ 1 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1 5 1 2 9 3 4 1 3 6 9 2 7 2 1 4 9 0 8 3 ∞ 10 ∞ ∞ ∞ ∞ 1 2 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1 5 1 2 9 3 4 1 3 6 9 2 7 2 1 4 9 0 8 6 10 12 5 ∞ ∞ 1 2 3 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1 5 1 2 9 3 4 1 3 6 9 2 7 2 1 4 9 0 8 6 10 12 14 ∞ 1 2 3 5 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1 5 1 2 9 3 4 1 3 6 9 2 7 2 1 4 9 0 7 10 12 14 ∞ 1 2 3 5 6 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1 5 1 2 9 3 4 1 3 6 9 2 7 2 1 4 9 0 9 12 14 ∞ 1 2 3 5 6 7 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1 5 1 2 9 3 4 1 3 6 9 2 7 2 1 4 9 0 12 14 10 1 2 3 5 6 7 9 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2 8 1 7 6 1