【例6-1】设有两个二元组G1=(V1R1)与G2=(V2R2),其中, V1={1,2,3,4,5} R1={VR1} VR1={<1,2>,<1,5>,<2,1>,<2,4>,<3,5>,<4,1> R2=iVRy VR2={(ab),(a,d)2(b,d),(d,c)} (a)有向图 (a)无向图 【图-】图示例
6 【例 6-1】设有两个二元组G1=(V1 ,R1 )与G2=(V2 , R2 )，其中， V1={1, 2, 3, 4, 5} R1={VR1 } VR1={<1,2>, <1,5>, <2,1>, <2,4>, <3,5>, <4,1>} V2={a, b, c, d} R2={VR2 } VR2={(a,b), (a, d), (b, d), (d, c)} 1 2 5 4 3 a b c d (a) 有向图 (a) 无向图 【图 -】图示例
§6.1.1图的概念 4.邻接、关联 ·对图中任意结点x与y,若它们之间存在边的关 系(即有<x,y>,或y,x〉),则称x与y邻接, 们互为邻接点。同时称x或y与边<x,y〉(或 <y,x>或(x,y))关联
7 §6.1.1 图的概念 4．邻接、关联 • 对图中任意结点x与y，若它们之间存在边的关 系（即有<x,y>，或<y,x>），则称x与y邻接， 它们互为邻接点。同时称x或y与边<x,y>（或 <y,x>或(x,y)）关联。 1 2 5 4 3 a b c d
§6.1.1图的概念 5.度 对任一结点x,称以它为头的弧的个数为它的入度 称以它为尾的弧的个数为它的出度 称它的入度与出度之和为它的度 对无向图,无出度入度之分,直接称与它关联的边的 个数为它的度
8 §6.1.1 图的概念 5．度 • 对任一结点x，称以它为头的弧的个数为它的入度 • 称以它为尾的弧的个数为它的出度 • 称它的入度与出度之和为它的度。 • 对无向图，无出度入度之分，直接称与它关联的边的 个数为它的度。 1 2 5 4 3 a b c d
§6.1.1图的概念 6.权 权是一个数值量,是某些信息的数字化抽象。 权分边权与结点权,分别是边与结点的问题世界所关 心的信息的数值化表示 例如,若结点代表城市,则边权可代表城市之间的交 通费用。 200 70 60
9 §6.1.1 图的概念 6．权 • 权是一个数值量，是某些信息的数字化抽象。 • 权分边权与结点权，分别是边与结点的问题世界所关 心的信息的数值化表示。 • 例如，若结点代表城市，则边权可代表城市之间的交 通费用。 1 2 5 4 3 60 70 200 170 70 90
§6.1.1图的概念 7.路径(通路) 对有向图,若存在弧序列 X1,X2> 且n≥l,则称从x到x有通路(路径)。上列序列称为 x到x的路径。该路径也可表示为 2
10 §6.1.1 图的概念 7．路径（通路） • 对有向图，若存在弧序列 <x0 ,x1>，<x1 ,x2>，…，<xn-1 ,xn > 且n≥1，则称从x0到xn有通路（路径）。上列序列称为 x0到xn的路径。该路径也可表示为 (x0 , x1 , … ,xn ) 1 2 5 4 3