Questions in category: 图论 (Graph Theory)
计算数学 >> 离散数学 >> 图论

1. 旅行商问题(TSP)

Posted by haifeng on 2018-05-10 18:40:13 last update 2018-05-10 18:40:59 | Answers (0) | 收藏


旅行商问题(TSP) 也称旅行售货员问题

 

设 $c_1,c_2,\ldots,c_n$ 是 $n$ 个不同的城市. 有个售货员居住在某个城市 $c_{i_0}$, 他从 $c_1$ 出发到其他城市 $c_2,\ldots,c_n$ 去推销商品(货物), 最后要回到城市 $c_{i_0}$.

假定任意两个城市间的距离是已知的, $d_{ij}:=d(c_i,c_j)$.

问他应沿着怎样的路线走, 才能使得所走的路线最短?

 

References:

赵静、但琦主编《数学建模与数学实验》(第四版)P.106--107

宋增民 主编 《图论及其应用》1.1.3

2. 中国邮递员问题

Posted by haifeng on 2018-05-10 18:27:58 last update 2018-05-10 18:41:27 | Answers (0) | 收藏


问题描述:

邮递员发送邮件时, 要从邮局出发, 经过他投递范围内的每条街道至少一次, 最后返回邮局. 邮递员希望能选择一条行程最短的路线.


 

模型

这里用点表示交叉路口, 点与点之间的连线(边)表示街道. 每条边赋予一个数(权)表示街道的长度.

 

这个问题是遍历所有边且使得权最小的问题.

 

Remark:

由于此问题是由中国的管梅谷教授首先研究的, 国际上通称为中国邮递员问题.

 

 


References:

赵静、但琦主编《数学建模与数学实验》(第四版)P.104

宋增民 主编 《图论及其应用》1.1.2

3. [Def]关于图(graph)的基本概念---路径(path),道路(trail),通路(walk)

Posted by haifeng on 2018-04-11 10:36:56 last update 2018-04-17 17:04:19 | Answers (0) | 收藏


所谓的路径(path)是指一个图 $P$, 满足

\[
V(P)=\{x_0,x_1,\ldots,x_{\ell}\},\quad E(P)=\{x_0x_1, x_1x_2,\ldots,x_{\ell-1}x_{\ell}\}.
\]

这里 $x_i\neq x_j$, $\forall\ i\neq j$.

这条路径 $P$ 通常记为 $x_0x_1x_2\ldots x_{\ell}$. 顶点 $x_0$ 和 $x_{\ell}$ 是路径 $P$ 的两个端点. 而 $\ell=e(P)$ 是路径 $P$ 的长度.

我们称 $P$ 是从 $x_0$ 到 $x_{\ell}$ 的一条路径(path), 或简记为 $x_0-x_{\ell}$ path.  当然 $P$ 也是一条从 $x_{\ell}$ 到 $x_0$ 的路径, 或简记为 $x_{\ell}-x_0$ path.

有时, 我们将强调 $P$ 是从 $x_0$ 到 $x_{\ell}$ 的, 并且称 $x_0$ 为起点(或始点)(initial vertex), $x_{\ell}$ 为终点(terminal vertex).

以 $x$ 为起点的道路称为 $x$-path.

 

大多数路径可以视为某给定图 $G$ 的一个子图. 图 $G$ 的一条通路(walk)是指一条由顶点与边组成的交错序列:

\[
x_0,\alpha_1,x_1,\alpha_2,x_2,\ldots,\alpha_{\ell},x_{\ell}.
\]

其中 $\alpha_i=x_{i-1}x_i$, $i=1,2,\ldots,\ell$. 这里顶点和边都可以重复.

$\ell$ 称为这条通路(walk)的长度.

 

如果通路(walk)中限定边不能重复, 顶点可以重复, 则称这条通路为道路(trail).

因此, 所谓的路径, 实际上就是顶点和边均不重复的通路.

 

若道路(trail)的两端点重合(也即是一条闭合道路 a closed trail),则称其为一个回路(circuit).

 

设 $W=x_0x_1\ldots x_{\ell}$ 是一条通路(walk), 满足 $\ell\geqslant 3$,  $x_0=x_{\ell}$. 并且诸 $x_i(0 < i < \ell)$ 互不相同, 也不同于 $x_0$, 则称 $W$ 是一个 圈(cycle).

为简单起见, 这个 cycle 记为 $x_1x_2\ldots x_{\ell}$. 注意到这里的记号不同于之前的, 这里 $x_1x_{\ell}$ 也是该 cycle 的一条边. 进一步的, $x_1x_2\ldots x_{\ell}$, $x_{\ell}x_{\ell-1}\ldots x_1$, $x_2x_3\ldots x_{\ell}x_1$, $x_ix_{i-1}\ldots x_1x_{\ell}x_{\ell-1}\ldots x_{i+1}$ 都指的是同一个 cycle.

 

记号:

符号 涵义
$P^{\ell}$ 长度为 $\ell$ 的一条路径(path)
$C^{\ell}$ 长度为 $\ell$ 的一个圈 (cycle)

 

我们称 $C^3$ 是一个三角形(triangle), $C^4$ 是一个四边形(quadrilateral), $C^5$ 是一个五边形(pentagon), 等等.

一个 cycle 被称为是 even (或 odd) 的, 如果它的长度是 even (或 odd) 的.

给定顶点 $x,y$, 它们之间的距离 $d(x,y)$ 指连接这两点的所有路径中长度最短的那条路径的长度.

\[
d(x,y)=\min\{\text{length of } x-y\ \text{path}\}
\]

若 $x,y$ 之间不存在 $x-y$ path, 则令 $d(x,y)=\infty$.

 

一个图称为是连通的(connected), 如果对于任意两个不同点组成的点对 $\{x,y\}$, 都存在一条从 $x$ 到 $y$ 的路径(path).

 

 

设无向图 $G(V,E)$ 是连通的, 设边集 $E_1\subset E$. 在图 $G$ 中删除 $E_1$ 中所有的边后得到的子图是不连通的, 而删除了 $E_1$ 的任一真子集后得到的子图是连通图, 则称 $E_1$ 是 $G$ 的一个割边集.

若割边集仅由一条边组成, 则称这条边为割边, 或桥(bridge).

 

 

 


References:

Béla Bollobas, Graph Theory, An introductory course.   GTM 63.
 

4. 图的匹配与覆盖之间的关系

Posted by haifeng on 2018-04-10 23:04:20 last update 2018-04-10 23:04:20 | Answers (0) | 收藏


定理. 设 $M$ 是图 $G$ 的匹配, $K$ 是覆盖, 则:

(1) $|M|\leqslant |K|$;

(2) 若 $|M|=|K|$, 则 $M$ 是最大匹配, $K$ 是最小覆盖.


 

5. chromatic number

Posted by haifeng on 2014-04-14 09:22:08 last update 2014-04-14 09:22:47 | Answers (0) | 收藏


将一个图 $G$ 的各顶点着色, 使相邻顶点不同颜色的最少颜色数, 称为该图的 chromatic number.

 


References:

http://mathworld.wolfram.com/ChromaticNumber.html

6. [Thm]Cayley 图的笛卡尔乘积仍为 Cayley 图

Posted by haifeng on 2011-08-19 08:55:21 last update 2011-08-19 08:55:21 | Answers (0) | 收藏


该结果由徐俊明, 徐克力所证明.

References
徐俊明, 徐克力. Cayley 图的笛卡尔乘积, 中国科学技术大学学报 Vol.31, No.6, Dec. 2001, 635--640.

7. [Def]Cayley 图的定义

Posted by haifeng on 2011-08-19 08:50:35 last update 2011-08-19 08:50:35 | Answers (0) | 收藏


假设 $\Gamma$ 是一个非平凡有限群, $S$ 是 $\Gamma$ 的非空子集, 且不含单位元. 定义一个有向图 $G$ 如下:

\[ V(G)=\Gamma;\quad (x,y)\in E(G)\Leftrightarrow x^{-1}y\in S,\ \forall\ x,y\in\Gamma. \]

称 $G$ 为群 $\Gamma$ 关于子集 $S$ 的 Cayley 图, 记为 $C_\Gamma(S)$.

8. [Def] n 个图的笛卡尔乘积

Posted by haifeng on 2011-08-19 08:34:33 last update 2011-08-19 10:58:41 | Answers (0) | 收藏


假设 $G_i=(V_i,E_i),\ i=1,2,\ldots,n$ 是 $n$ 个图, 它们的笛卡尔乘积 $G=G_1\times G_2\times\cdots\times G_n$ 定义为, $V(G)=V_1\times V_2\times\cdots\times V_n$, 且 顶点 $(x_1,x_2,\ldots,x_n)$ 与 $(y_1,y_2,\ldots,y_n)$ 之间存在一条边当且仅当这两个顶点(向量)的坐标仅有一个分量是不同的, 比如 $x_{i_0}\neq y_{i_0}$, 并且 $(x_{i_0},y_{i_0})\in E_{i_0}$.

9. Hamiltonian Weight Conjecture

Posted by haifeng on 2011-08-09 08:37:06 last update 2011-08-09 08:37:06 | Answers (0) | 收藏


http://www.math.uiuc.edu/~west/openp/cqhamwt.html

10. 亏格为 $g$ 的二维曲面上地图着色的最少颜色数公式

Posted by haifeng on 2011-05-07 15:33:07 last update 0000-00-00 00:00:00 | Answers (0) | 收藏


希伍德(Heawood)的猜想