图与网络分析
第一页，共34页。
§1.图的基本知识一、图
1、图：由一些点及一些点的连线所组成的图形。若V={V1,V2,…, Vn}是空间n个点的集合  E= { e1,e2,…, em}是空间m个点的集合满足1)V非空    2)E中每一条线ei是以V中两个点Vs,Vt为端点     3)E中任意两条线之间除端点之外无公共点.则由V、E构成的二元组合G=(V， E)就是图。2、子图：已知图G1（V1，E1）若V1   V， E1     E   则称图G1（V1，E1）是图G=(V， E)的子图3、若在图G中，某个边的两个端点相同，则称e是环。4、多重边：图中某两点之间有多余一条的边，称之为多重边。   多重图：含有多重边的图。5、简单图：无环、无多重边的图。
第二页，共34页。
   
二、连通图
1、链：给定一个图G=(V,E)，一个点边的交错序列(vi1, ei1, vi2, ei2,…,vik-1,eik-1,vik)，如果满足eit=[vit,vit+1] (t=1,2,…,k-1)，则称为一条联结vi1和vik的链，称点vi2, vi3,…,vik-1为链的中间点 ...