图的基本术语

1、端点和邻接点

在一个无向图中，如果存在一条 边（i,j），则成为i,j为此边的两个端点，并称他们互为邻接点，在一个有向图中，如果存在一条 边（i,j），则称此边为i的一个出边，j的一个入边，i,j分别称为起始端点，终止端点

2、完全图

如果无向图中每两个顶点之间都有一条边，有向图中两个顶点间存在方向相反的两条边，则成为完全图。

3、回路或环

如果一条路径上的起始顶点和终止顶点是同一个顶点，则称此路径为回路或环。

4、连通，连通图，连通分量

无向图G中，从顶点vi到vj有路径，则称vi，vj连通，如果任意两点连通，则为连通图，否则为非连通图，无向图中的极大连通子图为连通分量。

5、强连通图，强连通分量

有向图G中，从顶点vi到vj有路径，则称vi，vj连通，如果任意两点vi和vj连通，则为强连通图，有向图中的极大强连通子图为强连通分量。

6、关节点和重连通图

假如删除图G中顶点V及相关联的各边后，将图的一个连同分量分为两个或多个连通分量，则称顶点V为图G的关节点。一个没有关节点的连通图为重连通图。

7、稠密图和稀疏图

当一个图接近完全图时称为稠密图，一个图含较少的边时为稀疏图。

8、权和网

图中每一条边都可以附有一个对应的数，这种与边有关的数称为权，权可以表示一个顶点到另一个顶点的距离或花费的代价，边上带有权的图称为带权图或叫网。