第六章图论 定义一个图是一个序偶<V,E>,记为 G=<V,E>,其中： 1)V={1,2,3,V}是一个有限的非空集合， V:（i=1,2,3,n)称为结点，简称点，V为结 点集； 2）)E={e1,e2,e3,em}是一个有限的集合， e:(i=1,2,3,m)称为边，E为边集，E中的 每个元素都有V中的结点对与之对应。即对任 意e∈E,都有e与<u,v>或者(u,v)相对应。 2025/5/13 计算机与信息工程学院
2025/5/13 计算机与信息工程学院 1 定义一个图是一个序偶<V,E>，记为 第六章 图论 G＝<V,E>，其中： 1) V＝{v1,v2,v3,.,vn}是一个有限的非空集合， vi(i＝1,2,3,.,n)称为结点,简称点，V为结 点集； 2) E＝{e1,e2,e3,.,em}是一个有限的集合， ei(i＝1,2,3,.,m)称为边，E为边集，E中的 每个元素都有V中的结点对与之对应。即对任 意e∈E，都有e与<u,v>或者(u,v)相对应
图的分类（按边的方向） 若边e与无序结点对(u,v)相对应，则称边e为无向边，记 为e=(u,v),这时称u,v是边e的两个端点； 若边e与有序结点对<u,v>相对应，则称边e为有向边（或 弧)，记为e=<u,v>,这时称u是边e的始点（或弧 尾).v是边e的终点（或弧头），统称为e的端点； 每条边都是无向边的图称为无向图； 每条边都是有向边的图称为有向图； 有些边是无向边，而另一些是有向边的图称为混合图。 用小圆圈表示V中的结点，用由u指向v的有向线段表示 <uv>,无向线段表示(u,V)。 2025/5/13 计算机与信息工程学院 2
2025/5/13 计算机与信息工程学院 2 若边e与无序结点对(u，v)相对应，则称边e为无向边,记 为e＝(u，v)，这时称u，v是边e的两个端点； 若边e与有序结点对<u，v>相对应，则称边e为有向边(或 弧)，记为e＝<u，v>，这时称u是边e的始点(或弧 尾).v是边e的终点(或弧头)，统称为e的端点； 每条边都是无向边的图称为无向图； 每条边都是有向边的图称为有向图； 有些边是无向边，而另一些是有向边的图称为混合图。 图的分类(按边的方向) 用小圆圈表示V中的结点，用由u指向v的有向线段表示 <u,v>，无向线段表示(u,v)
例 设图G=<V,E>如右图所 e6 示。这里 es es V={V1,V2,3,V4s}, E={e1,e2,eg,e4e5,e6}, 基粤w2,=g>,9g=, e4=(V2,3),e5=<3,v2>,e6=(V3,3)。 图中的e1、e3e4是无向边，e2e5是有向边。 2025/5/13 计算机与信息工程学院 3
2025/5/13 计算机与信息工程学院 3 例 设图G＝<V,E>如右图所 示。这里 V＝{v1 ,v2 ,v3 ,v4 ,v5 }， E＝{e1 ,e2 ,e3 ,e4 ,e5 ,e6 }， 其中 e1 ＝(v1 ,v2 )，e2 ＝<v1 ,v3 >，e3 ＝(v1 ,v4 )， e4 ＝(v2 ,v3 )，e5 ＝<v3 ,v2 >，e6 ＝(v3 ,v3 )。 图中的e1、e3、e4是无向边，e2、e5是有向边
例 G G 上图所示的三个图分别表示为： G,=<V1,E>=<v1,V2Vgv4,【(v2,(2,vg), (,3),(V2V4,(VV4,(V3,V4}> G2=<W2,E2>=<{a,b,c,d,e},{Ka,b>,<c,b>, <c,a>,<d,e>}> G3=V3,E3>=<{1,2,3,4,5},{K1,2>,(1,4),<4,3>, <3,5>,<4,5>}> 2025/5/13 计算机与信息工程学院 4
2025/5/13 计算机与信息工程学院 4 例 上图所示的三个图分别表示为： G1 ＝<V1 ,E1 >＝<{v1 ,v2 ,v3 ,v4 }，{(v1 ,v2 ),(v2 ,v3 ), (v1 ,v3 ),(v2 ,v4 ),(v1 ,v4 ),(v3 ,v4 )}> G2 ＝<V2 ,E2 >＝<{a,b,c,d,e},{<a,b>,<c,b>, <c,a>,<d,e>}> G3 ＝<V3 ,E3 >＝<{1,2,3,4,5},{<1,2>,(1,4),<4,3>, <3,5>,<4,5>}>
几个概念 在一个图中，关联结点v和v的边e, 无论是有向的还是 无向的，均称边e与结点v,和v相关联，而v和v称为 邻接点，否则称为不邻接的； 2)关联于同一个结点的两条边称为邻接边： 3》)图中关联同一个结点的边称为环（或自回路）； 4)图中不与任何结点相邻接的结点称为孤立结点； 5)仅由孤立结点组成的图称为零图； 6)仅含一个结点的零图称为平凡图； e6 )含有n个结点、m条边的图 称为(n,m)图； e2 e 2025/5/13 计算机与信息工程学院 5
2025/5/13 计算机与信息工程学院 5 在一个图中，关联结点vi和vj的边e，无论是有向的还是 无向的，均称边e与结点vI和vj相关联，而vi和vj称为 邻接点，否则称为不邻接的； 几个概念 2) 关联于同一个结点的两条边称为邻接边； 3) 图中关联同一个结点的边称为环(或自回路)； 4) 图中不与任何结点相邻接的结点称为孤立结点； 5) 仅由孤立结点组成的图称为零图； 6) 仅含一个结点的零图称为平凡图； 7) 含有n个结点、m条边的图 称为(n，m)图；