图的基本概念.doc

第一章 图的基本概念 第一节 图和有向图 定义1.1 一个无向图图（graph）是指一个二元组，其中集合中的元素称为顶点（或点,或端点, 或结点）（or vertice, or node, or point), 集合中元素为中元素组成的无序对，称为边 (edge). 注意：1. 上述集合中的元素可以相同，有的文献称这样的集合为多重集。 2. 图称为空图，它有时在举反例的时候用到，且有时将一个结论推广到包含空图时会引起不必要的麻烦, 故本书中假设所讨论的图都不是空图。 3. 在一个图中，为了表示和分别是顶点集合边集，常将和分别记为和.