第10章图论(GraphTheory) 第十章图论(GraphTheory) 10.1图的基本概念(Graph) 10.2路与图的连通性(Walks 特别地,(n,0)称为零图,(1,0)图称为平凡图。 (2)按G中关联于同一对结点的边数分为多重图和简 单图; 多重图:含有平行边的图（如图10.1.3） ； 线图:非多重图称为线图； 简单图:不含平行边和自环的图。 10.1图的基本概念第10章图论(GraphTheory) G1、G2是多重图 G3是线图 G4是简单图第10章图论(GraphTheory) (3)按G的边有序、无序分为有向图、无向图和混合图 ; 有向图：每条边都是有向边的图称为有向图 （图10.1.4 (b)； 无向图：每条边都是无向边的图称为无向图； 混合图：既有无向边,又有有向边的图称为混合图 。 (4)按G的边旁有无数量特征分为加权图、无权图(如图 10.1.4); 10.1图的基本概念第10章图论(GraphTheory) 图10.1.4 (5)按G的任意两个结点间是否有边分为完全图K n (如图10.1.5)和不完全图(如图10.1.6)。 10.1图的基本概
