1、第六讲 (第七章 ) 图的概念与表示1 图的基本概念2 链 (或路 )与圈 (或回路 )3 图的矩阵表示退出退出7.1 图的基本概念什么是图 ?可用一句话概括，即：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。因为它显得太抽象，不便于理解，所以有必要给出另外的回答。下面便是把图作为代数结构的一个定义。定义 7.1.1 一个图 G定义为一个三元组 ， 记作 G=。 其中 V是个非空有限集合，它的元素称为结点； E也是个有限集合，其元素称为边，而 是从 E到 V中的有序对或无序对的映射。由定义可知，图 G中的每条边都与图中的无序或有序结点对相联系的。若边 e E与无序结点
2、对 vi， vj 相联系，则 (e)= vi， vj ， 这时边 e称为无向边，有时简称为边；若边 e E与有序结点对 相联系，则 (e)=， 此时边 e称为有向边或弧， vi称为弧 e的始结点， vj称为弧 e的终结点。若结点 vi与 vj由一条边 (或弧 )e所联结，则称结点 vi和 vj是边 (或弧 )e的端结点；同时也称结点 vi与 vj是邻接结点，记作 vi adj vj； 否则为非邻接结点，记作 vi nadj vj； 也说边 (或弧 )e关联 vi与 vj或说结点 vi与 vj关联边 (或弧 )e。 关联同一个结点的两条边或弧称为邻接边或弧。而联结一结点与它自身的一条边，称为环。
3、环的方向是无意义的。如果把图 G中的弧或边总看作联结两个结点，则图G可简记为 G=， 其中 V是非空结点集， E是联结结点的边集或弧集。定义 7.1.2 在图 G=中，如果每条边都是弧，该图称为有向图；若每条边都是无向边，该图 G称为无向图；如果有些边是有向边，另一些边是无向边，图 G称为混合图。定义 7.1.3 在图 G=中，如果任何两结点间不多于一条边 (对于有向图中，任何两结点间不多于一条同向弧 )，并且任何结点无环，则图 G称为简单图；若两结点间多于一条边 (对于有向图中，两结点间多于一条同向弧 )图 G称为多重图，并把联结两结点之间的多条边或弧，称为平行边或弧，平行边或弧的条数称为重
4、数。定义 7.1.4 给每条边或弧都赋予权的图 G=，称为加权图，记为 G=， 其中 W表示各边之权的集合。加权图在实际中有许多应用，如在输油管系统图中权表示单位时间流经管中的石油数量；在城市街道中，权表示表示通行车辆密度；在航空交通图中，权表示两城市的距离等等。定义 7.1.5 在无向图 G=中，如果 V中的每个结点都与其余的所有结点邻接，即 (vi)(vj)(vi， vj V vi， vj E)则该图称为无向完全图，记作 K|V|。 若 |V|=n， 该图记作 Kn。在一个图中，如果一个结点不与任何其他结点邻接，则该结点称为孤立结点。仅有孤立结点的图称为零图。显然，在零图中边集为空集。若一个图中只含一个孤立结点，该图称为平凡图。
