def2:一个有向图G是一个有序的二元组,记为 G=(V,A),其中V=(V1V2…Vn)称为G的点集合, A={an称为G的弧(有向边)集合,a;是以V 指向V的一条弧。 ●V=n表示G中节点个数为n,此节点个数n也称 为图G的阶 ●|A=m表示有向图G中弧的个数为m ●任一顶点相关联(连接)的边的数目称为该顶 点的次数
7 def 2：一个有向图G是一个有序的二元组，记为 G=(V, A)，其中V=(V1V2…Vn )称为G的点集合， A={aij}称为G的弧（有向边）集合，aij是以Vi 指向Vj的一条弧。 ⚫ |V|=n表示G中节点个数为n，此节点个数n也称 为图G的阶 ⚫ |A|=m表示有向图G中弧的个数为m ⚫ 任一顶点相关联（连接）的边的数目称为该顶 点的次数
2连通图 def3:在有向图G中,一个点和边的交替序列 V ev称为G中从点V到V的一条 路,记为A,其中V为此路A的起点,V为路A 的终点;若路A的起点与终点重合,则称A为回 路;又若G中点V与V间存在一条路,则称点 V;与V是连通的;若G中任何二点都是连通的, 则称G为连通图,或图G为连通的。在无向图 中有对应的概念。 有向图 无向图 路链 回路 圈
8 2 连通图 def 3：在有向图G中,一个点和边的交替序列 {Vi eij Vj…Vk ekl Vl } 称为G中从点Vi到Vl的一条 路，记为A，其中Vi为此路A的起点，Vj为路A 的终点；若路A的起点与终点重合,则称A为回 路；又若G中点Vi与Vj间存在一条路，则称点 Vi与Vj是连通的；若G中任何二点都是连通的， 则称G为连通图，或图G为连通的。在无向图 中有对应的概念。 有向图 路 回路 无向图 链 圈
3子图 def4:设有两个图:G1=(V1,E),G2=(V2 E2)若有 VICVEICE,则称G1为G2的子图, 记作G∈G2;若有Ⅴ=V2而E∈E2,则称图 G1=(V1,E1)是图G2=(V2,E2)的生成子图(支撑 子图)
9 3 子图 def 4：设有两个图：G1= (V1 , E1 ) ，G2= (V2 , E2 )若有 ，则称G1为G2的子图， 记作 ；若有 V1=V2而 ,则称图 G1= (V1 , E1 ) 是图G2= (V2 , E2 )的生成子图（支撑 子图）。 V1 V2 E1 E2 G1 G2 E1 E2
●例:下示图G1是图G的子图,图G2.是图G的生 成子图。 (a)图G (b)图G1 (c)图G2
10 ⚫ 例：下示图G1是图G的子图，图G2是图G的生 成子图。 V1 V3 V2 V4 V1 V2 V4 V1 V3 V2 V4 （a）图G （b）图G1 （c）图G2
4赋权图(加权图)与网路 def5:设G是一个图(或有向图),若对G的每 条边(或弧)e;都赋予一实数oi,称其为该 边(弧)的权,则G连同其他弧上的权集合称 为一个赋权图,记作G=(V,E,W)或G=(V,A W),此中W={o,O1为对应边(弧)的权 若G=(V,E,W)(或(V,A,W)为赋权图,且 在G的V中指定一个发点(常记为)和一个 收点(记为v1),其余点称为中间点,则称这 样指定了发点与收点的赋权图G为网络
11 4 赋权图（加权图）与网路 def 5：设G是一个图（或有向图），若对G的每 一条边（或弧）eij都赋予一实数ωij，称其为该 边（弧）的权，则G连同其他弧上的权集合称 为一个赋权图，记作G= (V, E, W) 或G= (V, A, W)，此中W={ωij}，ωij为对应边（弧）eij的权。 若G= (V, E, W) （或(V, A, W)）为赋权图，且 在G的V中指定一个发点（常记为Vs）和一个 收点（记为Vt），其余点称为中间点，则称这 样指定了发点与收点的赋权图G为网络