图的基本概念 无序积:设A,B为任意的两个集合,称{ab}|a∈A且 b∈B为A与B的无序积,记做A&B 定义141:一个无向图G是个二重组<WGE(G)>,其中V(G为有限 非空结点(或叫顶点)集合E(G是边的集合它是无序积N&N的多 重子集,其元素为无向边 定义142:一个有间MGEG其中VG 为有限非空结点(或叫顶点)集合E)是边的集合,它 是笛卡儿乘积VV的多重子集,具元素为有向边,简称边。 东南大学计算机科学与工程学院 同的出学 图论
定义14.2：一个有向图G是一个二重组<V(G),E(G)>, 其中V(G) 为有限非空结点（或叫顶点）集合, E(G)是边的集合，它 是笛卡儿乘积V×V的多重子集，其元素为有向边，简称边。 无序积：设A，B为任意的两个集合，称{{a,b} | a∈A且 b∈B}为A与B的无序积，记做A&B. 定义14.1：一个无向图G是一个二重组<V(G),E(G)>, 其中V(G)为有限 非空结点（或叫顶点）集合, E(G)是边的集合，它是无序积V&V的多 重子集，其元素为无向边，简称边
图的基本术语 通常用G表示无向图,D表示有向图,但G也可以泛指图。VG,EG 分别表示G的顶点集和边集。GE(G)分别表示G的顶点数和边数, 若V(G=n,则称G为n阶图。 若VGEG均为有限数,则称G为有限图 若图G中,边集为空,则称之为零图,若G为n阶图,则称之为n阶零 图记为Nn,N称为平凡图。顶点集为空的图记为空图。 4称页点或边用字母标定的图为标定图,否则称为非标定图。另外,将 有向边改为无向边后的图称为原图的基图。 5设G=<VE>为无向图,e=WM)∈E则称Wv为e的端点,e与v或ek 与v是彼此关联的。若≠v,则称e与V或e与V的关联次数为1,若 v=v,则称ek与v的关联次数为2,并称为环任意的v∈V,若≠v且 vV则称e与的关联次数为0
通常用G表示无向图，D表示有向图，但G也可以泛指图。V(G)，E(G) 分别表示G的顶点集和边集。|V(G)|,|E(G)|分别表示G的顶点数和边数， 若|V(G)|＝n，则称G为n阶图。 若|V(G)|,|E(G)|均为有限数，则称G为有限图。 若图G中，边集为空，则称之为零图，若G为n阶图，则称之为n阶零 图记为Nn，N1称为平凡图。顶点集为空的图记为空图。 称顶点或边用字母标定的图为标定图，否则称为非标定图。另外，将 有向边改为无向边后的图称为原图的基图。 设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，并称为环。任意的vl∈V，若vl≠vi且 vl≠vj ，则称ek与vl的关联次数为0
图的基本术语 6设无向图G=<VE>,wv∈V,ee∈E。若有e=v),则称M与∨是 相邻的。若e与e至少有一个公共端点,则称e与e是相邻的。 有向图D=<VE>,Mv∈V,ee∈E。若有ekvy>,则e与M关 联,称为的始点,为的终点,并称邻接到,V等接于M,若e 的终点为e的始点,则称e与e相邻。 东南大学计算机科学与工程学院 同的出学 图论
设无向图G=<V,E>，vi ,vj∈V， ek ,el∈E。若有ek=(vi ,vj )，则称vi与vj是 相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。 有向图D=<V,E>，vi ,vj∈V，ek ,el∈E 。若有ek=<vi ,vj>，则ek与vi ,vj关 联，称vi为ek的始点，vj为ek的终点，并称vi邻接到vj，vj邻接于vi，若ek 的终点为el的始点，则称ek与el相邻。 Vi Vj Vl Vi
图的基本术语 设无向图G=<VE>,对所有的v∈V称 {uu∈∧(v)∈E入≠v} 为v的邻域,记为Ne(),并称N)∪记为v的闭邻域,记为N(V) 称{e|e∈E∧e与相关联}为v的关联集,记为l)。 设有向图D=<VE>,对所有的v∈V,称I(v)={u∈VA<v,>∈E入l≠v} 为的后继元素。称I(v)={∈V入<l,v>∈E≠v为的先驱元素 称两者之并为v的邻域,记为Nv)称N()∪{},为v的闭邻域。 东南大学计算机科学与工程学院 同的出学 图论
设无向图G=<V,E>，对所有的v∈V 称 { | ( , ) } u u V u v E u v 为v的邻域，记为NG(v)，并称NG(v) ∪{v}记为v的闭邻域，记为 N (v) G 称 { | } e e E e v 与 相关联 为v的关联集，记为IG(v) 。 设有向图D=<V,E>，对所有的v∈V ，称 为v的后继元素。称 为v的先驱元素。 称两者之并为v的邻域，记为ND (v) 。称ND (v) ∪{v}，为v的闭邻域。 (v) {u | u V v,u E u v} D = + (v) {u | u V u,v E u v} D = −
平行边与多重图 定义143在无向图中,关联一对顶点的无向边如果多于一条, 则称这些边为平行边,平行边的条数称为重数。在 有向图中,关联一对顶点的有向边如果多于一条, 并且这些边的始点和终点相同,则称这些边为平行 边。含平行边的图称为多重图,即不含平行边也不 含环的图称为简单图。非多重图称为线图 东南大学计算机科学与工程学院 同的出学 图论
定义14.3 在无向图中，关联一对顶点的无向边如果多于一条， 则称这些边为平行边，平行边的条数称为重数。在 有向图中，关联一对顶点的有向边如果多于一条， 并且这些边的始点和终点相同，则称这些边为平行 边。含平行边的图称为多重图，即不含平行边也不 含环的图称为简单图。非多重图称为线图