图论模型

基本概念

1. 图的概念

   定义 一个图G是指一个二元组（V（G），E（G）），其中：

   1. V（G）={v1,v2,…,v_v}是非空有限集，称为顶点集，其中元素称为图G的顶点。
   2. E(G) 是顶点集V(G) 中的无序或有序的元素偶对(v_i,v_j)组成的集合，即称为边集，其中元素称为边。

   定义 图G的阶是指图的顶点数|V(G)|，用v来表示；图的边的数目|E(G)|用ε来表示。

   用G=（V（G），E（G））表示图，简记G=（V,E）。也用v_iv_j来表示边(v_i,v_j)。

   定义 若一个图的顶点集和边集都是有限集，则称其为有限图。只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图。

   定义 若图G中的边均为有序偶对(v_i,v_j)，称G为有向图。称边e=(v_i,v_j)为有向边或弧，称e=(v_i,v_j)是从vi连接vj，称vi为e的尾，称vj为e的头。

   若图G中的边均为无序偶对v_iv_j，称G为无向图。称边e=v_iv_j为无向边，称e连接v_i和v_j，顶点vi和vj称为e的端点。既有无向边又有有向边的图称为混合图。

   常用术语

   1. 边和它的两端点称为互相关联。
   2. 与同一条关联的两个端点称为相邻的顶点，与同一个顶点关联的两条边称为相邻的边。
   3. 端点重合为一点的边称为环，端点不相同的边称为连杆。
   4. 若一对顶点之间有两条以上的边联结，则这些边称为重边。
   5. 既没有环也没有重边的图，称为简单图。
   6. 任意两顶点都相邻的简单图，称为完全图。记为K_v。
   7. 若V（G）=X∪Y，X∩Y=Φ，且X中任意两顶点不相邻，Y中任意两顶点不相邻，则称为二部图或偶图；若X中每一顶点皆与Y中一切顶点相邻，称为完全二部图或完全偶图，记为K_m,n(m=|X|,n=|Y|).

2. 赋权图与子图

   定义 若图G=(V(G),E(G))的每一条边e都赋以一个实数w(e)，称w(e)为边e的权，G连同边上的权称为赋权图。

   定义 设G=(V,E)和G’=(V’,E’)是两个图

   1. 若V’⊆V，E‘⊆E，称G’是G的一个子图，记G‘⊆G。
   2. 若V’=V，E‘⊆E，则称G’是G的生成子图。
   3. 若V‘⊆V，且V’≠Φ，以V‘为顶点集，以两端点均在V’中的边的全体为边集的图G的子图，称为G的由V‘导出的子图，记为G[V’]。
   4. 若E‘⊆E，且E’≠Φ，以E‘为边集，以E’的端点集为顶点集的图G的子图，称为G的由E‘导出的子图，记为G[E’]。

3. 图的矩阵表示

   邻接矩阵：（以下均假设图为简单图）。

   1. 对无向图G，其邻接矩阵A=(a_ij)_v×v，其中：
      aij={1,若vi与vj相邻，0,若vi与vj不相邻a_{ij}= \begin{cases} 1,若v_i与v_j相邻，\\ 0,若v_i与v_j不相邻 \end{cases} aij​={1,若vi​与vj​相邻，0,若vi​与vj​不相邻​

   2. 对有向图G=(V,E)，其邻接矩阵A=(a_ij)_v×v，其中：
      aij={1,若(vi,vj)∈E，0,若(vi,vj)∉Ea_{ij}= \begin{cases} 1,若(v_i,v_j)∈E，\\ 0,若(v_i,v_j)∉E \end{cases} aij​={1,若(vi​,vj​)∈E，0,若(vi​,vj​)∈/E​

   3. 对有向赋权图G=(V,E)，其邻接矩阵A=(a_ij)_v×v，其中：
      aij={wij,若(vi,vj)∈E，且wij为其权0，i=j,∞，若(vi,vj)∉Ea_{ij}= \begin{cases} w_{ij},若(v_i,v_j)∈E，且w_{ij}为其权\\ 0，i=j,\\ ∞，若(v_i,v_j)∉E \end{cases} aij​=⎩⎨⎧​wij​,若(vi​,vj​)∈E，且wij​为其权0，i=j,∞，若(vi​,vj​)∈/E​

   关联矩阵

   1. 对无向图G=(V,E)，其关联矩阵M=(m_ij)_v×ε，其中：
      mij={1,若vi与ej相关联，0,若vi与ej不关联m_{ij}= \begin{cases} 1,若v_i与e_j相关联，\\ 0,若v_i与e_j不关联 \end{cases} mij​={1,若vi​与ej​相关联，0,若vi​与ej​不关联​

   2. 对有向图G=(V,E)，其关联矩阵M=(m_ij)_v×ε，其中：
      mij={1,若vi是ej的尾，−1,若vi是ej的头，0,若vi不是ej的头与尾m_{ij}= \begin{cases} 1,若v_i是e_j的尾，\\ -1,若v_i是e_j的头， \\ 0,若v_i不是e_j的头与尾 \end{cases} mij​=⎩⎨⎧​1,若vi​是ej​的尾，−1,若vi​是ej​的头，0,若vi​不是ej​的头与尾​

4. 图的顶点度

   定义

   1. 在无向图G中，与顶点v关联的边的数目（环算两次），称为顶点v的度或次数，记为d(v)或d_G(v)。称度为奇数的顶点为奇点，度为偶数的顶点为偶点。
   2. 在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d-(v)。称d(v)=d+(v)+d-(v)为顶点v的度或次数。

5. 路和连通

   定义

   1. 无向图G的一条途径（或通道或链）是指一个有限非空序列W=v0e1v1e2…ekvk，它的项交替地顶点和边，使得对1≤i≤k，ei的端点是v_i-1和v_i，称W是从v0到vk的一条途径，或一条（v0，vk）途径。整数k称为W的长。顶点v0和vk分别称为起点和终点，而v1,v2,…,v_k-1称为W的内部结点。

   2. 若途径W的边互不相同但顶点可重复，则称W为迹或简单链。

   3. 若途径W的顶点和边均互不相同，则称W为路或路径。一条起点为v0，终点为vk的路称为(v0,vk)路记为P(v0,vk)。

   4. 途径W=v0e1v1e2…ekvk中由相继项构成子序列viei+1vi+1…ejvj称为途径W的节。

   5. 起点与终点重合的途径称为闭途径。

   6. 起点与终点重合的路称为圈（或回路），长为k的圈称为k阶圈，记为C_k。

   7. 若在图G中存在（u,v）路，则称顶点u和v在图G中连通。

   8. 若在图G中顶点u和v是连通的，则顶点u和v之间的距离d(u,v)是指图G中最短(u,v)路的长；若没有路连接u和v，则定义为无穷大。

   9. 图G中任意两点皆连通的图称为连通图。

   10. 对于有向图G，若W=v0e1v1e2…ekvk，且ei有头vi和尾vi-1，则称W为有向途径。

       类似地，可定义有向迹，有向路和有向圈。

最短路问题及算法

两种方法：Dijkstra和Floyd算法

1. 求赋权图中从给定点到其余顶点的最短路
2. 求赋权图中任意两点间的最短路

详见离散数学