大学计算机基础-图的基本概念

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

注意：线性表中可以没有元素，称为空表。树中可以没有节点，叫做空树。但是在图中不允许没有顶点，可以没有边。

基本术语：

·无向边：若顶点Vi和Vj之间的边没有方向，称这条边为无向边（Edge），用（Vi，Vj）来表示。

·无向图（Undirected graphs）：图中任意两个顶点的边都是无向边。

·有向边：若从顶点Vi到Vj的边有方向，称这条边为有向边，也称为弧（Arc），用＜Vi，Vj＞来表示，其中Vi称为弧尾（Tail），Vj称为弧头（Head）。

·有向图（Directed graphs）：图中任意两个顶点的边都是有向边。

·简单图：不存在自环（顶点到其自身的边）和重边（完全相同的边），如图9-32所示。

图9-32　无向图和有向图

·无向完全图：无向图中，任意两个顶点之间都存在边。

·有向完全图：有向图中，任意两个顶点之间都存在方向相反的两条弧。

·稀疏图；有很少条边或弧的图称为稀疏图，反之称为稠密图。

·权（Weight）：表示从图中一个顶点到另一个顶点的距离或耗费。(www.xing528.com)

·网：带有权重的图

·度：与特定顶点相连接的边数；

·出度、入度：有向图中的概念，出度表示以此顶点为起点的边的数目，入度表示以此顶点为终点的边的数目；

·环：第一个顶点和最后一个顶点相同的路径；

·简单环：除去第一个顶点和最后一个顶点后没有重复顶点的环；

·连通图：任意两个顶点都相互连通的图；

·极大连通子图：包含竟可能多的顶点（必须是连通的），即找不到另外一个顶点，使得此顶点能够连接到此极大连通子图的任意一个顶点；

·连通分量：极大连通子图的数量；

·强连通图：此为有向图的概念，表示任意两个顶点a，b，使得a能够连接到b，b也能连接到a的图；

·生成树：n个顶点，n-1条边，并且保证n个顶点相互连通（不存在环）；

·最小生成树：此生成树的边的权重之和是所有生成树中最小的；