邻域 口设无向图G=<V,E,v∈V 称{ulu∈v∧(a,)∈E∧u≠可为v的邻域,记做NG()。 称N()U{为w的闭邻域,记做NG(v)。 称{ee∈E∧e与v相关联}为y的关联集,记做()。 口设有向图D=<V,E>,v∈V 称{ulu∈V∧<,u>∈E∧u≠可为v的后继元集,记做厂+D(v)。 称{uu∈V∧<n,吵∈E∧M≠为的先驱元集,记做厂D(V)。 称「tb()U「D()为v的邻域,记做ND(v)。 称ND()∪研为v的闭邻域,记做ND(吵)
邻域 ❑ 设无向图G＝<V，E>，v∈V， 称{u|u∈V∧(u,v)∈E∧u≠v}为v的邻域，记做NG(v)。 称NG (v)∪{v}为v的闭邻域，记做NG(v)。 称{e|e∈E∧e与v相关联}为v的关联集，记做IG(v)。 ❑ 设有向图D＝<V，E>，v∈V， 称{u|u∈V∧<v,u>∈E∧u≠v}为v的后继元集，记做Г+ D(v)。 称{u|u∈V∧<u,v>∈E∧u≠v}为v的先驱元集，记做Г- D(v)。 称Г+ D(v)∪Г- D(v)为v的邻域，记做ND(v)。 称ND(v)∪{v}为v的闭邻域，记做ND(v)
举例 N(v1)={v,v2,v e 29 b T+n(d)=ich r-d(d)=la, ch No(d) C No(d) =a, c, d
举例 NG (v1 ) ＝ Г+ D(d ) ＝ {v2，v5} NG(v1 ) ＝ {v1，v2，v5} IG(v1) ＝ {e1，e2，e3} {c} Г-D(d ) ＝ {a，c} ND(d ) ＝ {a，c} ND(d ) ＝ {a，c，d}
简单图与多重图 定义14.3在无向图中,关联一对顶点的无向边如果多于1条, 则称这些边为平行边,平行边的条数称为重数。 在有向图中,关联一对顶点的有向边如果多于1条,并且这些 边的始点和终点相同(也就是它们的方向相同),则称这些边 为平行边。 含平行边的图称为多重图。 既不含平行边也不含环的图称为简单图。 例如:在图14.1中, (a)中e与e是平行边, (b)中e2与e3是平行边,但e与e不是平行边。 (a)和(b)两个图都不是简单图
简单图与多重图 定义14.3 在无向图中，关联一对顶点的无向边如果多于1条， 则称这些边为平行边，平行边的条数称为重数。 在有向图中，关联一对顶点的有向边如果多于1条，并且这些 边的始点和终点相同(也就是它们的方向相同)，则称这些边 为平行边。 含平行边的图称为多重图。 既不含平行边也不含环的图称为简单图。 例如：在图14.1中， (a)中e5与e6是平行边， (b)中e2与e3是平行边，但e6与e7不是平行边。 (a)和(b)两个图都不是简单图
项点的度数 定义14.4设G=<V,E>为一无向图,v∈V,称咋作为边的端点 次数之和为v的度数,简称为度,记做dn(吵)。 在不发生混淆时,简记为d()。 设D=<,E>为有向图,Vv∈V, 称v作为边的始点次数之和为v的出度,记做D(),简记作 dr-()。 称v作为边的终点次数之和为的入度,记做dp(),简记作 d(吵)。 称(m)+d()为v的度数,记做d()
顶点的度数 定义14.4 设G＝<V,E>为一无向图，v∈V，称v作为边的端点 次数之和为v的度数，简称为度，记做 dG (v)。 在不发生混淆时，简记为d(v)。 设D＝<V，E>为有向图，v∈V， 称v作为边的始点次数之和为v的出度，记做d + D(v)，简记作 d +(v)。 称v作为边的终点次数之和为v的入度，记做d - D(v)，简记作 d -(v)。 称d +(v)+d -(v)为v的度数，记做d(v)
的度数的相关概 口在无向图G中, 最大度△(G)=max{d()lv∈v(G) 最小度6(G)=min{d()lv∈v(G) 口在有向图D中, 最大出度△+(D)=maxd()lv∈v(D 最小出度8+(D)=min{r(v)|v∈V0) 最大入度△-(D)=maxd()|v∈V0) 最小入度6-(0)=min{d()|v∈v(D 口称度数为1的顶点为悬挂顶点,与它关联的边称为悬挂边。 度为偶数(奇数)的顶点称为偶度(奇度)顶点
图的度数的相关概念 ❑ 在无向图G中， 最大度 △(G)＝max{d(v)|v∈V(G)} 最小度 δ(G)＝min{d(v)|v∈V(G)} ❑ 在有向图D中， 最大出度 △+(D)＝max{d +(v)|v∈V(D)} 最小出度 δ+(D)＝min{d +(v)|v∈V(D)} 最大入度 △-(D)＝max{d -(v)|v∈V(D)} 最小入度 δ-(D)＝min{d -(v)|v∈V(D)} ❑ 称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。 度为偶数(奇数)的顶点称为偶度(奇度)顶点