图的基本定义

Scroll Down

1.图按照有无方向分为有向图和无向图,无向图由顶点和边构成,有向图由定点和唬构成,弧有弧尾和弧头之分,A->B记为<A,B> 2.图按照边或者弧的多少分为稀疏图和稠密图.如果任意两个顶点之间都存在边则叫完全图,有向的话则称为有向完全图,若无重复的边或者顶点到自身的边则叫简单图 3.图中顶点之间有邻接点和依附的概念.无向图顶点的边数叫做度,有向图顶点分为入度和出度 4.图上的边或弧上带权重则称为网 5.途中顶点间存在路径,两顶点存在路径说明是连通的,如果路径最终回到起始点则称为环,当中不重复的叫简单路径,若任意两顶点都是连通的,则图就是连通图,有向则称为强连通图.图中有子图,若子图极大连通则就是连通分量,有向的则称为强连通分量. 6.无向图中连通且n个顶点n - 1条边叫生成树,有向图中一顶点入度为0其余顶点入度为1的叫有向树.一个有向图由若干棵有向树构成生成森林.