第一节图的基本概念 本章讨论的图都是连通图 若有图G=(V,E),取其全部或部分顶点V, 再取其全部或部分边E,则图G=(V1,E)称 为图G的子图。这里非空，E中的边连接的顶 点都在V中 二、 有向图 前面所讨论的图中边是没有方向的，e,=(Ws, V)=(V,Vs),这种图也称为无向图。但许多实际 问题用无向图来描述是不够的 23
23 第一节 图的基本概念 本章讨论的图都是连通图。 若有图G＝(V，E)，取其全部或部分顶点V1， 再取其全部或部分边E1，则图G＝(V1，E1 )称 为图G的子图。这里Vl非空，El中的边连接的顶 点都在V1中。 二、有向图 前面所讨论的图中边是没有方向的，ej = (vs， vt )＝(vt，vs )，这种图也称为无向图。但许多实际 问题用无向图来描述是不够的
第一节图的基本慨念 例如交通网络中的单行道，一项工程各工序 间的先后次序关系等。于是设想用带箭头的线来 反映这种有次序的相互关系，这就是有向图。 定义2设V={y1,V2,vn}是n个元素的非 空集合，A={a1,a2,am}是m个元素的集合 若对任一a,∈A,均有有序对 (Vs,V)∈V与之 对应，则称VUA为有向图，记为G=(V,A)。称 v为G的顶点，a为G的孤，并记a=(y。,v)。弧 也称为有向边，在不至于混淆的情况下，简称边
24 第一节 图的基本概念 例如交通网络中的单行道，一项工程各工序 间的先后次序关系等。于是设想用带箭头的线来 反映这种有次序的相互关系，这就是有向图。 定义2 设V={v1，v2，.，vn }是n个元素的非 空集合，A={a1，a2，.，am}是m个元素的集合。 若对任一aj ∈A，均有有序对（vs，vt）∈V与之 对应，则称V∪A为有向图，记为G＝(V，A)。称 vi为G的顶点，aj为G的弧，并记aj = (vs，vt )。弧 也称为有向边，在不至于混淆的情况下，简称边
第一节图的基本概念 图8-8表示一个有向图G=V,A),其中V= {V1,V2,V3,V4,vsh,A=,az,a3,a4,a5' a6 27) 21 V2),a2=(1 3 V3), a7=(V4'V5),ag=( V2 a4 V4 al a7 a3 a5 a8 a2 V3 a6 5 图8-8一个有向图 25
25 第一节 图的基本概念 图8-8表示一个有向图G＝(V，A)，其中V＝ {v1，v2，v3，v4，v5 }，A＝{a1，a2，a3，a4，a5， a6，a7，a8 }，a1=(v1，v2 )，a2=(v1，v3 )，a3=(v2， v3 )， a4=(v2 ， v4 )，a5=(v2 ， v5 )，a6=(v3 ， v5 )， a7=(v4，v5 )，a8=(v5，v4 )。 图8-8 一个有向图
第一节图的基本概念 在有向图G中，从一个顶点出发，顺着弧的 方向，经过弧、点、弧、点， 到达某一点， 称它为G中的一条单向链或通路，简称路。也可 用经过这条单向链的顶点（或弧）表示单向链。如 图8-8中的(W1,a1,V2 a5’V5’a8 V)是一条单 向链，也可表示为W1,V2,Vsv4)或(a1,as,ag) 在有向图中，顶点的次数分为入次，和出次。 入次是以该顶点为终点的边的个数，出次是以该 顶点为起点的边的个数。 26
26 第一节 图的基本概念 在有向图G中，从一个顶点出发，顺着弧的 方向，经过弧、点、弧、.、点，到达某一点， 称它为G中的一条单向链或通路，简称路。也可 用经过这条单向链的顶点(或弧)表示单向链。如 图8-8中的(v1，a1，v2，a5，v5，a8，v4 )是一条单 向链，也可表示为(v1，v2，v5，v4 )或(a1，a5，a8 )。 在有向图中，顶点的次数分为入次，和出次。 入次是以该顶点为终点的边的个数，出次是以该 顶点为起点的边的个数
第一节图的基本念 例如在图8-8中，d(2)=3,d(V2)=1, d(v4)=1,d(v4)=2,d(s)=1,d(s)=3。 三、赋权图 如果对于给定的图G=(V,E)的任一边e∈E, 有一实数W(e)与之对应，则称G为赋权图，称 W(e)为边e的权。 例如，图8-9表示一个赋权图，其中W(y1, V2)=1,W(W1,V3)=4,W(y2,V3)=2等。通常表 示赋权图时， 往往是将边的权数显示在该边上。 27
27 第一节 图的基本概念 例如在图8-8中，d + (v2 ) ＝3， d - (v2 ) ＝1， d + (v4 ) ＝1， d - (v4 ) ＝2， d + (v5 ) ＝1， d - (v5 ) ＝3。 三、赋权图 如果对于给定的图G＝(V，E)的任一边e∈E， 有一实数W(e)与之对应，则称G为赋权图，称 W(e)为边e的权。 例如，图8-9表示一个赋权图，其中W(v1， v2 )＝1，W(v1，v3 )＝4，W(v2，v3 )＝2等。通常表 示赋权图时，往往是将边的权数显示在该边上