图的定义与术语2
让编程改变世界
Change the world by program
图的顶点与边之间的关系
对于无向图G=(V,E)，如果边(V1,V2)∈E，则称顶点V1和V2互为邻接点(Adjacent)，即V1和V2相邻接。 边(V1,V2)依附(incident)于顶点V1和V2，或者说边(V1,V2)与顶点V1和V2相关联。 顶点V的度(Degree)是和V相关联的边的数目，记为TD(V)，如下图，顶点A与B互为邻接点，边(A,B)依附于顶点A与B上，顶点A的度为3。 对于有向图G=(V,E)，如果有<V1,V2>∈E，则称顶点V1邻接到顶点V2，顶点V2邻接自顶点V1。 以顶点V为头的弧的数目称为V的入度(InDegree)，记为ID(V)，以V为尾的弧的数目称为V的出度(OutDegree)，记为OD(V)，因此顶点V的度为TD(V)=ID(V)+OD(V)。 下图顶点A的入度是2，出度是1，所以顶点A的度是3。 无向图G=(V,E)中从顶点V1到顶点V2的路径(Path)。 下图用红线列举了从顶点B到顶点D的四种不同路径： 如果G是有向图，则路径也是有向的。 下图用红线列举顶点B到顶点D的两种路径，而顶点A到顶点B就不存在路径啦： 路径的长度是路径上的边或弧的数目。 第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。 序列中顶点不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。 下图左侧是简单环，右侧不是简单环：连通图
在无向图G中，如果从顶点V1到顶点V2有路径，则称V1和V2是连通的，如果对于图中任意两个顶点Vi和Vj都是连通的，则称G是连通图(ConnectedGraph) 下图左侧不是连通图，右侧是连通图： 无向图中的极大连通子图称为连通分量。 注意以下概念：- 首先要是子图，并且子图是要连通的；
- 连通子图含有极大顶点数；
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边。