7-1图的基本概 定义一个图是一个三元组<VG),E(G),中c>,简记为 G=<V,E>, 其中 1)V={v1,v2,v3,…,vn}是一个非空集合,v1(i= 2,3,,n)称为结点,简称点,V为结点集; 2)E={e1,e2,e3,…,en}是一个有限的集合,e;(i 1,2,3,,m)称为边,E为边集,E中的每个元素都有V 中的结点对(有序偶或无序偶)与之对应 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 一、图 定义一个图是一个三元组<V(G),E(G),φG>,简记为 G＝<V,E>， 7-1 图的基本概念 其中： 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与结点无序偶(u,v)相对应,则称边e为无向 边,记为e=(u,v),这时称u,v是边e的两个端点; 2)若边e与结点有偶u,v>相对应,则称边e为有向边 (或弧),记为e=<u,v>,这时称u是边e的始点(或 弧尾).v是边e的终点(或弧头),统称为e的端点 3)在一个图中,关联结点v1和v的边e,无论是有向的 还是无向的,均称边e与结点v和v;相关联,而v1和 ⅴ;称为邻接点,否则称为不邻接的; Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 图的术语 ▪ 若边e与结点无序偶(u，v)相对应，则称边e为无向 边,记为e＝(u，v)，这时称u，v是边e的两个端点； 2) 若边e与结点有偶<u，v>相对应，则称边e为有向边 (或弧)，记为e＝<u，v>，这时称u是边e的始点(或 弧尾).v是边e的终点(或弧头)，统称为e的端点； 3) 在一个图中，关联结点vi和vj的边e，无论是有向的 还是无向的，均称边e与结点vI和vj相关联，而vi和 vj称为邻接点，否则称为不邻接的；
续: 4)关联于同一个结点的两条边称为邻接边; 5)图中关联同一个结点的边称为自回路(或环); 6)图中不与任何结点相邻接的结点称为孤立结点 7)仅由孤立结点组成的图称为零图; 8)仅含一个结点的零图称为平凡图 9)含有n个结点、m条边的图称为(n,m)图; Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 续： 续： 4) 关联于同一个结点的两条边称为邻接边； 5) 图中关联同一个结点的边称为自回路(或环)； 6) 图中不与任何结点相邻接的结点称为孤立结点； 7) 仅由孤立结点组成的图称为零图； 8) 仅含一个结点的零图称为平凡图； 9) 含有n个结点、m条边的图称为(n，m)图；
续: 续: 每条边都是无向边的图称为无向图; 每条边都是有向边的图称为有向图; 有些边是无向边,而另一些是有向边的图称为混合图。 在有向图中,两个结点间(包括结点自身间)若有同始点和 同终点的几条边,则这几条边称为平行边,在无向图中, 两个结点间(包括结点自身间)若有几条边,则这几条边称 为平行边,两结点v,v间相互平行的边的条数称为边(v v;)或<v;,ⅴ;>的重数; Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 续： 续： ▪ 每条边都是无向边的图称为无向图； ▪ 每条边都是有向边的图称为有向图； ▪ 有些边是无向边，而另一些是有向边的图称为混合图。 ▪ 在有向图中，两个结点间(包括结点自身间)若有同始点和 同终点的几条边，则这几条边称为平行边，在无向图中， 两个结点间(包括结点自身间)若有几条边，则这几条边称 为平行边，两结点vi，vj间相互平行的边的条数称为边(vi， vj)或<vi，vj>的重数；
续: 14)含有平行边的图称为多重图。非多重图称为线 图;无环和平行边的图称为简单图。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 续： 14)含有平行边的图称为多重图。非多重图称为线 图；无环和平行边的图称为简单图