连通图针对无向图,强连通图针对有向图。
稀疏图(边数较少),稠密图(边数较多)。
稠密图:邻接矩阵、Prim算法...
稀疏图:邻接表、Kruskal算法...
如果一个连通图的所有结点的度都是偶数,那么它就是Eulerian,如果除了两个结点的度是奇数其他都是偶数,那么它就是Semi-Eulerian,否则就是Non-Eulerian。
给定一组节点的度序列来判断一个图是否为简单图?(符合以下两点即可)
a、每个节点度数要小于节点个数。
b、该图具有偶数个奇数度的节点。
判定哈密顿回路条件:
a、路径节点个数等于 n+1
b、相邻点之间存在连通的边
c、各点只出现过1次(除了首尾)
d、第一个节点等于最后一个节点(构成回路)
待更新...