图与网络分析的基本概念

是否存在欧拉回路的判定规则： 

（1）如果连接奇数边的顶点多于两个，则不存在欧拉回路；

（2）如果只有两个点连接奇数边，可以从这两个地方之一出发，找到欧拉回路；

（3）如果没有一个点连奇数边，则无论从哪里出发，都能找到欧拉回路。

图及其分类

这里研究的图与平面几何中的图不同，我们只关心图中有多少个点，点与点之间有无线连接，至于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。下面介绍有关图的一些基本概念。

    1.无向图  图是点和线所组成的图形，即图是一个有序二元组(V,E)，记为G=(V,E)，其中V={v1,v2,…vp}是p个点的集合，E={e1,e2,…eq}是q条边的集合。V中的元素vi称为顶点，E中的元素ek称为边。

①平行边——

②简单图——

③完备图——

④子图——

⑤生成子图——

⑥连通图——

   2.有向图 

①弧——在一个网络图中带方向的边称为弧。弧必须有一个起点和一个终点。若弧的起点为u、终点为v，则记为 e=(u,v)

②有向图——

③入度——

④出度——

⑤同构图——若有向图D1=(V1,E1)和D2=(V2,E2)的顶点集V1和V2以及边集E1和E2之间在保持关联性质的条件下一一对应，则称D1和D2为同构图。

图的矩阵表示

1.权矩阵。

2.邻接矩阵。

一、图与网络的基本概念

9.6 主要解题方法和典型例题分析.docx(下载附件 1.18 MB)