例14,1 例14.1(1)给定无向图G=<V,E>,其中V={v1,v2v3,Vv4,vs}, (2)给定有向图D=<M,E>,其中V={a,b,c,d}, E={<a,a>,<a,b>,<a,b>,<a,d,<c,d>,<d,c>,<c,b为}。 画出G与D的图形。 b
例14.1 例14.1 (1) 给定无向图G＝<V,E>，其中 V＝{v1 ,v2 ,v3 ,v4 ,v5 }， E={(v1 ,v1 ),(v1 ,v2 ),(v2 ,v3 ),(v2 ,v3 ),(v2 ,v5 ),(v1 ,v5 ),(v4 ,v5 )}. (2) 给定有向图D=<V,E>，其中 V＝{a,b,c,d}， E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。 画出G与D的图形
的一些概念和规定 口G表示无向图,但有时用G泛指图(无向的或有向的)。 口D只能表示有向图。 口V(G),E(G)分别表示G的顶点集和边集。 口若|V(G)|=n,则称G为n阶图。 口若|V(G)与|E(G)|均为有限数,则称G为有限图。 口若边集E(G)=,则称G为零图,此时,又若G为n阶图,则称G 为n阶零图,记作N,特别地,称N1为平凡图 口在图的定义中规定顶点集V为非空集,但在图的运算中可能产 生顶点集为空集的运算结果,为此规定顶点集为空集的图为 空图,并将空图记为
图的一些概念和规定 ❑ G表示无向图，但有时用G泛指图(无向的或有向的)。 ❑ D只能表示有向图。 ❑ V(G)，E(G)分别表示G的顶点集和边集。 ❑ 若|V(G)|＝n，则称G为n阶图。 ❑ 若|V(G)|与|E(G)|均为有限数，则称G为有限图。 ❑ 若边集E(G)＝，则称G为零图，此时，又若G为n阶图，则称G 为n阶零图，记作Nn，特别地，称N1为平凡图。 ❑ 在图的定义中规定顶点集V为非空集，但在图的运算中可能产 生顶点集为空集的运算结果，为此规定顶点集为空集的图为 空图，并将空图记为
标定图与非标定图、基图 口将图的集合定义转化成图形表示之后,常用e表示无向边 (v;,v1)(或有向边<v;,v>),并称顶点或边用字母标定 的图为标定图,否则称为非标定图。 口将有向图各有向边均改成无向边后的无向图称为原来图 的基图。 口易知标定图与非标定图是可以相互转化的,任何无向图G 的各边均加上箭头就可以得到以G为基图的有向图
标定图与非标定图、基图 ❑ 将图的集合定义转化成图形表示之后，常用ek表示无向边 (vi ,vj )（或有向边<vi ,vj >），并称顶点或边用字母标定 的图为标定图，否则称为非标定图。 ❑ 将有向图各有向边均改成无向边后的无向图称为原来图 的基图。 ❑ 易知标定图与非标定图是可以相互转化的，任何无向图G 的各边均加上箭头就可以得到以G为基图的有向图
关联与头联次数、环、孤立点 口设G=<,E>为无向图,e=(vy∈E, 称v;v为e的端点,ek与或ek与v是彼此相关联的。 若v≠v;,则称ek与v或e与v的关联次数为1。 若v=v,则称e与v的关联次数为2,并称e为环。 任意的v∈V,若vv且v≠v,则称ek与v的关联次数为0。 口设D=《,E>为有向图,=<v吵∈E, 称vv为的端点。 若v=v,则称e为D中的环。 口无论在无向图中还是在有向图中,无边关联的顶点均称为孤 立点
关联与关联次数、环、孤立点 ❑ 设G＝<V,E>为无向图，ek＝(vi,vj)∈E， 称vi,vj为ek的端点，ek与vi或ek与vj是彼此相关联的。 若vi≠vj，则称ek与vi或ek与vj的关联次数为1。 若vi＝vj，则称ek与vi的关联次数为2，并称ek为环。 任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联次数为0。 ❑ 设D＝<V,E>为有向图，ek＝<vi,vj>∈E， 称vi,vj为ek的端点。 若vi＝vj，则称ek为D中的环。 ❑ 无论在无向图中还是在有向图中，无边关联的顶点均称为孤 立点
相邻与邻 口设无向图G=,E>,v,v∈V,"k,e∈E 若e∈E,使得e=(,),则称与是相邻的。 若e与e至少有一个公共端点,则称e与e是相邻的。 口设有向图D=<,E>,v,v∈V,ek,e∈E。 点,并称邻华。则称为的始点,为e的终 若彐e∈E,使得e=<v, 接于 若ek的终点为e的始点,则称与e相邻
相邻与邻接 ❑ 设无向图G＝<V，E>，vi，vj∈V，ek，el∈E。 若et∈E，使得et ＝(vi，vj )，则称vi与vj是相邻的。 若ek与el至少有一个公共端点，则称ek与el是相邻的。 ❑ 设有向图D＝<V，E>，vi，vj∈V，ek，el∈E。 若et∈E，使得et ＝<vi，vj >，则称vi为et的始点，vj为et的终 点，并称vi邻接到vj，vj邻接于vi。 若ek的终点为el的始点，则称ek与el相邻