图

在数学的分支图论中，图（Graph）用于表示物件与物件之间的关系，是图论的基本研究对象。一张图由一些小圆点（称为顶点或结点）和连结这些圆点的直线或曲线（称为边）组成。西尔维斯特在1878年首次提出“图”这一名词。图有多种变体，包括简单图、多重图、有向图、无向图等，但大体上有以下两种定义方式。一张图 G {displaystyle G} 是一个二元组 ( V , E ) {displaystyle (V,E)} ，其中 V {displaystyle V} 称为顶点集， E {displaystyle E} 称为边集。它们亦可写成 V ( G ) {displaystyle V(G)} 和 E ( G ) {displaystyle E(G)} 。 E {displaystyle E} 的元素是一个二元组数对，用 ( x , y ) {displaystyle (x,y)} 表示，其中 x , y ∈ V {displaystyle x,yin V} 。一张图 G {displaystyle G} 是一个三元组 ( V , E , I ) {displaystyle (V,E,I)} ，其中 V {displaystyle V} 称为顶集（Vertices set）， E {displaystyle E} 称为边集（Edges set）， E {displaystyle E} 与 V {displaystyle V} 不相交； I {displaystyle I} 称为关联函数， I {displaystyle I} 将 E {displaystyle E} 中的每一个元素映射到 V × V {displaystyle Vtimes V} 。如果 I ( e ) = ( u , v ) ( e ∈ E , u , v ∈ V ) {displaystyle I(e)=(u,v)(ein E,u,vin V)} 那么称边 e {displaystyle e} 连接顶点 u , v {displaystyle u,v} ，而 u , v {displaystyle u,v} 则称作 e {displaystyle e} 的端点， u , v {displaystyle u,v} 此时关于 e {displaystyle e} 相邻。同时，若两条边 i , j {displaystyle i,j} 有一个公共顶点 u {displaystyle u} ，则称 i , j {displaystyle i,j} 关于 u {displaystyle u} 相邻。如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。一个图如果若允许两结点间的边数多于一条，又允许顶点通过同一条边和自己关联，则为多重图的概念。它只能用“三元组的定义”。一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图（网），相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域（Adjvex），用以指示与vi邻接的点在图中的位置，链域（Nextarc）用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（Info）。每个顶点的单链表中结点的个数即为该顶点的出度（与该顶点连接的边的总数）。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。图的遍历方法有深度优先搜索法和广度（宽度）优先搜索法。深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：对于图 G ( V , E ) {displaystyle G(V,E)} 与图 G ′ ( V ′ , E ′ ) {displaystyle G'(V',E')} ，若存在从 V {displaystyle V} 到 V ′ {displaystyle V'} 的一一映射f，使任意 ( u , v ) ∈ E {displaystyle (u,v)in E} ,都有 ( f ( u ) , f ( v ) ) ∈ E ′ {displaystyle (f(u),f(v))in E'} ，则称 G {displaystyle G} 与 G ′ {displaystyle G'} 同构