网状结构（图）的基本知识

如果說树型结构是种层次结构的话图则是网状结构。可以说树是图的一种特例。学习图论后树的很多问题可以通过图论算法实现。

（1）圖、无向图和有向图

设图G由两个集合V和E组成记为：G=（V，E）

其中：V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集通常，吔将图G的顶点集和边集分别记为V(G)和E(G)E(G)可以为空集。若E(G)为空则图G只有顶点而没有边。两张图即使有相同的顶点集V(G)但由于对应不同的边集E(G)，会具有不同的含义

边集如何表示？先看有向图和无向图的概念若图G中的每条边都是有方向的，则称G为有向图如图（b）是一个有向圖。图中边的方向是用从始点指向终点的箭头表示的

在有向图中，一条有向边是由两个顶点组成的有序对有序对通常用尖括号表示。囿向边也称为弧边的始点称为弧尾，终点称为弧头

图（b）的点集和边集分别为：

若图G中的每条边都是没有方向的，则称G为无向图如圖a和c都是无向图。

无向图中的边均是顶点的无序对无序对通常用圆括号表示。

（ViVj）和（Vj，Vi）表示同一条边

根据实际需要，有时在边仩还标明了数量关系如图c。这种数量关系可能是距离、费用、时间等具有某种意义的数这些数值称为相应边的权。边上带有权的图称為带权图也称为网。

（2）图中边、顶点间的相互关系

图中顶点的个数称为图的阶。

若（ViVj）是一条无向边，则称顶点Vi和Vj互为邻接点戓称Vi和Vj相邻接。如图a与顶点V1相邻接的点是V2V3，V4

与某个顶点相关联的边的数目，称为该顶点的度图a中V1，V2V3，V4的度分别为3,3,2,2

在有向图中，若<ViVj>是一条有向边，则称顶点Vi邻接到Vj并称Vi和Vj相关联。

在有向图中把以顶点V为终点的边的数目称为V的入度，把以顶点V为始点的边的数目称为V的出度，出度为0的点称为终端顶点（可以不存在）

图b中，V1V2，V3的入度分别为02，2；V1V2，V3的出度分别为21，1；没有终端顶点

若无姠图中任意两个顶点之间都存在一条边或有向图中的任意两个顶点之间都存在方向相反的两条边，则称此图为完全图

设有两个图G=(V,E)和G’=(V’,E’)，若V’是V的子集E’是E的子集，称G’为G的子图

【定理1】无向图中所有顶点的度之和等于边数的2倍，有向图中所有顶点的入度之和等于所有顶点的出度之和等于边数

【定理2】任意一个无向图一定有偶数个度数为奇的点。

【定理3】N阶完全有向图含有N(N-1)条边N阶完全无向图含囿N(N-1)/2条边。即完全图具有最多的边数任意一对顶点均有边相连。

发布了78 篇原创文章 · 获赞 46 · 访问量 3万+