图的定义

2020-08-24  本文已影响0人  YOLO_2a2d

图的定义

线性表中数据元素叫结点;
树中数据元素叫结点;
图中数据元素叫顶点;

图中的定义

无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边,用无序偶(Vi,Vj)来表示;

有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也称为弧,用有序偶<Vi,Vj>来表示;

无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含n个顶点的无向完全图有n*(n-1)/2条边;

有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边;

稀疏图:边或弧数小于nlogn(n是顶点的个数);
稠密图:边或弧数大于n
logn;

权:图的边或弧带有与它相关的数字;
网:带权的图通常称为网;

图的顶点与边之间的关系

** 邻接点: **对于无向图G=(V,E),如果边(V1,V2)属于E,则称顶点V1和V2互为邻接点,即V1和V2相邻接。边(V1,V2)依附雨顶点V1和V2,或者说边(V1,V2)与顶点V1和V2相关联;

** 顶点V的度 ** 顶点V的度是和V相关联的边的数目,记为TD(V);

** 连通图 **在无向图G中,如果从顶点V1到顶点V2有路径则称V1和V2是连通的,如果对于图中任意两个顶点Vi和Vj都是连通的,则称G是连通图;

上一篇下一篇

猜你喜欢

热点阅读