2.无向图： 3.边：若<v,w心口VR必有 由顶点集和边 <w,v>IVR,即VR是对称的， 集构成的图称 则以无序对(v,w代替这两个 有序对，称顶点V和顶点w 作无向图。 之间存在一条边(V,w) 例如：G2(V2,VR2) V2=A,B,C,D,E,F) VR2={(A,B),(A,E), B,E),(C,D),(D,F) (B,F),(C,F)}
若<v, w> VR 必有 <w, v> VR, 即VR是对称的， 则以无序对(v,w)代替这两个 有序对，称顶点 v 和顶点 w 之间存在一条边(v,w) 。 B C A F E D 由顶点集和边 集构成的图称 作无向图。 例如: G2=(V2 ,VR2 ) V2={A, B, C, D, E, F} VR2={(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) } 2.无向图： 3.边：
5.有向网，无向网： 弧或边带权的图 分别称作有向网或 无向网。 4.子图： 设图G=(V,VR)和 A 图G口=(V口， VR▣)， 且V口▣V, VR▣▣VR
A B E C F A E F B B C 设图G=(V, VR) 和 图 G =(V , VR ), 且 V V, VR VR, 则称 G 为 G 的子图。 15 9 7 21 11 3 2 弧或边带权的图 分别称作有向网或 无向网。 4. 子图： 5. 有向网，无向网：
6.完全图、稀疏图、稠密图： 完全图 假设图中有n个顶点，e条边， 如果e=n(n-1)/2,则该无向图为完全图。 有向完全图 将含有e=n(n-1)条弧的有向图 称作有向完全图。 稀疏图：如果边或弧的个数满足e<n log n, 则称作稀疏图，否则称作稠密图
完全图 假设图中有 n 个顶点，e 条边， 如果e=n(n-1)/2 ，则该无向图为完全图。 有向完全图 将含有 e=n(n-1) 条弧的有向图 称作有向完全图。 稀疏图：如果边或弧的个数满足 e < n log n， 则称作稀疏图，否则称作稠密图。 6. 完全图、稀疏图、稠密图：
7.邻接点、度 对无向图来说， 邻接点：假若顶点ⅴ和顶点w之间存在一条边， 则称顶点ⅴ和w互为邻接点， 度：与顶点v关联的边的数目，记为TD(v)。 例如： TD(B)=3 A TDA)=2
邻接点：假若顶点v 和顶点w 之间存在一条边， 则称顶点 v 和 w 互为邻接点， 例如: TD(B) = 3 TD(A) = 2 度：与顶点v 关联的边的数目,记为TD(v)。 A C D F E B 7.邻接点、度 对无向图来说
8.入度、出度 对有向图来说， 由于弧有方向性， 顶点的出度：以顶点v 则有入度和出度之分 为弧尾的弧的数目， 记为OD(): 顶点的入度：以顶点V 为弧头的弧的数目， 记为ID(W)。 例如： OD(B)=1 有向图中项点的： ID(B)=2 度(TD)=出度(OD)+入度(D) TD(B)=3
顶点的出度: 以顶点v 为弧尾的弧的数目, A 记为OD(v); B E C F 对有向图来说， 顶点的入度: 以顶点v 为弧头的弧的数目, 记为ID(v)。 有向图中顶点的: 度(TD)=出度(OD)+入度(ID) 例如: I D(B) = 2 OD(B) = 1 TD(B) = 3 由于弧有方向性， 则有入度和出度之分 8.入度、出度