图原理与心得

图原理与心得

一、图的性质

　　•图的路径的定义是边序列，也可是点边序列（正规定义）：以下默认路径是简单路径（点边序列中边不重合的路径）。
　　•一个图有n个结点，若边数大于n-1条，则一定有环（首尾结点相同的路径）（记住即可）。
　　•生成子图是一个包含原图所有结点的子图。
　　•无向图的连通：
　　　两结点连通，即两结点之间有路径。
　　　一个图是连通图，即任意两个结点有路径。
　　　连通分量 = 极大连通子图 = 包含尽可能多的结点与边的连通子图。
　　　无向图成为连通图所需边最少：构成一条线或一个生成树——n-1条。
　　　无向图成为连通图所需边最多：成为完全图——n(n-1)/2条。
　　•有向图的强连通：
　　　两结点强连通，即两结点可相互到达。
　　　一个图是强连通图，即任意两个结点可以相互到达。
　　　强连通分量 = 极大强连通子图 = 包含尽可能多的顶点与边的强连通子图。
　　　有向图成为强连通图所需边最少：构成一个环——n条。
　　　有向图成为强连通图所需边最多：成为完全图——n(n-1)条。
　　•对于连通图，有生成树，该生成树是包含其所有结点的极小连通子图（极小是边极少但仍保持连通）。非连通图有生成森林。
　　•连通分量只能少结点，生成树只能少边。而“极大”、“极小”是描述边的，因此极大连通子图指连通分量，包含全部顶点的极小连通子图指生成树。