Farey图及其对偶图的色多项式和流多项式 Chromatic Polynomials and Flow Polynomials of Farey Graphs and Their Dual Graphs

doi:10.12677/ORF.2018.84018

Operations Research and Fuzziology
Vol. 08 No. 04 ( 2018 ), Article ID: 27384 , 6 pages
10.12677/ORF.2018.84018

Chromatic Polynomials and Flow Polynomials of Farey Graphs and Their Dual Graphs

Meiling Shan

●How to Cite this Article

School of Science, Minzu University of China, Beijing

Received: Oct. 12^th, 2018; accepted: Oct. 25^th, 2018; published: Nov. 1^st, 2018

ABSTRACT

Liao Yunhua introduced the explicit polynomials of chromatic polynomials of the Farey graphs. In this paper, the flow polynomials and the face chromatic polynomials of the Farey graphs are derived, and the chromatic polynomials and the flow polynomials of the dual graphs of the Farey graphs are derived by the relations between the Farey graphs and their dual graphs.

Keywords:Chromatic Polynomials, Flow Polynomials, Farey Graphs

Farey图及其对偶图的色多项式和流多项式

单美玲

中央民族大学理学院，北京

收稿日期：2018年10月12日；录用日期：2018年10月25日；发布日期：2018年11月1日

摘要

廖云华推出了第n代Farey图G_n的点色多项式的显式。本文推出了第n代Farey图G_n的流多项式和面色多项式，并通过Farey图及其对偶图的关系，推出了Farey图的对偶图的色多项式和流多项式。

关键词 :色多项式，流多项式，Farey图

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

图的多项式包含着关于图的各种信息，并且被用来分析图和网络的特性。其中被研究最多的就有色多项式和流多项式。色多项式最早是在1912年由Birkhoff开始研究的，主要为了攻克四色问题，具体见文献 [1] 。围绕流多项式也有很多重要的理论问题，例如五流猜想和其他流存在性定理。李慰萱等 [2] 求出了以顶点个数、边数和内部面是 $i -$ 圈的内部面的个数为参数的外平面图的色多项式的显式。Boris Brimkov等 [3] 推出了轮图的色多项式及其对偶图的色多项式和流多项式。本文主要在前人研究的基础上，推导出了Farey图及其对偶图的色多项式(包括点色多项式和面色多项式)、流多项式。

2. 预备知识

$G = (V (G), E (G))$ 表示一个图；其中 $V (G)$ 为 $G$ 的顶点集， $E (G)$ 为 $G$ 的边集。

定义1 [4] ：设 $G = (V (G), E (G))$ 为一个图， $| V (G) |$ 、 $| E (G) |$ 和 $k (G)$ 分别为 $G$ 的顶点数、边数和连通分支数。令

$r (G) = | V (G) | - k (G), n (G) = | E (G) | - r (G) = | E (G) | - | V (G) | + k (G)$ ，

分别称 $r (G)$ 和 $n (G)$ 为图 $G$ 的秩和零度。

定义2 [4] ：令 $G$ 为一个图， $H$ 为图 $G$ 的一个生成子图，则 $G$ 的Tutte多项式可以定义为 $T (G; x, y) = \sum_{H \in G} {(x - 1)}^{r (G) - r (H)} {(y - 1)}^{n (H)}$ ，其中 $r (H)$ 和 $n (H)$ 分别为 $H$ 的秩和零度。

定义3 [5] ：图 $G$ 的一个 $λ$ 着色是指 $λ$ 种颜色 $1, 2, \dots, λ$ 对 $G$ 的各顶点的一个分配，且任意两个相邻的顶点都分配到不同的颜色；定义色多项式 $P (G; λ)$ 是图 $G$ 的不同 $λ -$ 着色的数目。

定义4 [3] ：平图 $G$ 的一个 $λ$ 面可着色是指 $λ$ 种颜色 $1, 2, \dots, λ$ 对面的集合 $F (G)$ 中元素的一种分配，使得有公共边的两个面的颜色不同；定义面色多项式 $P * (G; λ)$ 是图 $G$ 的不同 $λ$ 面可着色的数目。

定义5 [3] ：设 $G = (V (G), E (G))$ 是一个图， $D$ 为 $G$ 的任意一个定向， $A$ 为一个Abelian加法群。若映射 $f : D \to A$ 满足：对于 $G$ 中的任意顶点 $v$ ，都有流进 $v$ 的流量与流出 $v$ 的流量相等，则称映射 $f$ 为图 $G$ 上的一个 $A -$ 流。若对于任意弧 $u v \in D$ ，有 $f (u v) \neq 0$ ，则称 $f$ 为一个处处非零的 $A -$ 流。若 $A$ 为一个 $λ$ 阶群，图 $G$ 中处处非零的 $A -$ 流的数目是关于 $λ$ 的一个多项式，这个多项式称为 $G$ 的流多项式，记为 $F (G; λ)$ 。

定义6 [5] ：给出平图 $G$ ，可以定义另一个图 $G *$ 如下：对于 $G$ 的每个面 $f$ 都有 $G *$ 的顶点 $v *$ 与之对应； $G *$ 中顶点 $v *$ 和 $u *$ 由边 $e *$ 连接，当且仅当 $G$ 中与顶点 $v *$ 和 $u *$ 对应的面 $f$ 和 $g$ 被 $e$ 分隔。图 $G *$ 称为 $G$ 的对偶图。

引理1 [6] ：设 $G (V (G), E (G))$ 是一个图，则

$F (G; λ) = {(- 1)}^{- | V (G) | + | E (G) | + k (G)} T (G; 0, 1 - λ)$

其中 $| V (G) |$ 、 $| E (G) |$ 、 $k (G)$ 分别是 $G$ 的顶点数、边数和连通分支的个数。

引理2 [3] ：若图 $G$ 为平面图，则 $F (G; λ) = \frac{P (G *; λ)}{λ}$ 。

3. Farey图的色多项式和流多项式

Farey图是一类自相似的外平面图，可以由2种方法构造得到。

1) 迭代构造法 [4] (见图1)：设 $G_{n}$ 为第 $n$ 代Farey图。

Figure 1. Iterative construction method of Farey graphs

图1. Farey图迭代构造法

a) $n = 0$ 时， $G_{0} = K_{2}$ 。

b) $n \geq 1$ 时， $G_{n}$ 可以通过下面的迭代得到： $G_{n - 1}$ 在第 $n - 1$ 步加的每条边 $e$ ，对应一个新的顶点 $v$ ，并将 $e$ 的顶点与顶点 $v$ 相连，便得到图 $G_{n}$ 。

2) 递归构造法 [4] (见图2)：设 $G_{n}$ 为第 $n$ 代Farey图，且 $G_{n}$ 有两个特殊的顶点，分别设为 $A_{n}$ 和 $B_{n}$ 。

Figure 2. Recursive construction method of Farey graphs

图2. Farey图递归构造法

a) $n = 0$ 时， $G_{0} = K_{2}$ 。由一条边连接点 $A_{0}$ 和 $B_{0}$ 得到。

b) $n \geq 1$ 时， $G_{n}$ 可以通过两个 $G_{n - 1}$ 得到：用 ${G^{'}}_{n - 1}$ 和 ${G^{″}}_{n - 1}$ 分别表示这两个 $G_{n - 1}$ 。记 ${G^{'}}_{n - 1}$ 中的两个特殊的点分别为 ${A^{'}}_{n - 1}$ 和 ${B^{'}}_{n - 1}$ 。 ${B^{'}}_{n - 1}$ 记 ${G^{″}}_{n - 1}$ 中的两个特殊的点分别为 ${A^{″}}_{n - 1}$ 和 ${B^{″}}_{n - 1}$ 。将点 ${A^{″}}_{n - 1}$ 和 ${B^{'}}_{n - 1}$ 两点重合得到一个新的点，记为 $C_{n}$ 。再将 ${A^{'}}_{n - 1}$ 和 ${B^{″}}_{n - 1}$ 用一条新边相连，将和 ${B^{″}}_{n - 1}$ 分别记为 $A_{n}$ 和 $B_{n}$ 。这样便得到图了 $G_{n}$ 。

推论1 [4] ：为了表示方便，用 $T_{n} (x, y)$ 表示Farey图 $G_{n}$ 的Tutte多项式 $T (G_{n}; x, y)$ ，对于每个 $n \geq 1$ ，Farey图 $G_{n}$ 的Tutte多项式为

$T_{n} (x, y) = T_{1, n} (x, y) + (x - 1) N_{n} (x, y)$ ， (1)

其中 $T_{1, n} (x, y)$ 和 $N_{n} (x, y)$ 都是整系数多项式且满足以下递归关系

$T_{1, n} (x, y) = y T_{1, n - 1}^{2} (x, y) + 2 T_{1, n - 1} (x, y) N_{n - 1} (x, y) + (x - 1) N_{n - 1}^{2} (x, y)$ ， (2)

$N_{n} (x, y) = 2 T_{1, n - 1} (x, y) N_{n - 1} (x, y) + (x - 1) N_{n - 1}^{2} (x, y)$ ， (3)

初始条件为

$T_{1, 0} (x, y) = 1$ ， $N_{0} (x, y) = 1$ 。 (4)

定理1 [4] ：Farey图 $G_{n} (n \geq 1)$ 的色多项式为

$P (G_{n}; λ) = λ (1 - λ) {(2 - λ)}^{2^{n} - 1}$ 。

定理2：Farey图 $G_{n} (n \geq 1)$ 的流多项式为

$F (G_{n}; λ) = (λ - 1) \prod_{i = 0}^{n - 1} {(b_{i}^{2 (n - 1 - i)})}^{2}$

其中 $b_{0} = 1$ ，且 $n \geq 2$ 时， $b_{n} = 2 - λ - {(\frac{1 - λ}{b_{n - 1}})}^{2}$ ，初始值 $b_{1} = 2 - λ$ 。

证明：为了表示方便，设 $T (G_{n}; 0, 1 - λ) = T_{n} (0; 1 - λ)$ 并代入引理1，得

$\begin{matrix} F (G_{n}; λ) = {(- 1)}^{- | V (G_{n}) | + | E (G_{n}) | + k (G_{n})} T (G_{n}; 0, 1 - λ) \\ = {(- 1)}^{- | V (G_{n}) | + | E (G_{n}) | + k (G_{n})} T_{n} (0, 1 - λ) \end{matrix}$ 。 (5)

其中 $| V (G_{n}) |$ 、 $| E (G_{n}) |$ 、 $k (G_{n})$ 分别是 $G_{n}$ 的顶点数、边数和连通分支的个数。

我们先求 $T_{n} (0, 1 - λ)$ ，为了好表示，我们令 $1 - λ = y$ ，所以我们要将 $T_{n} (0, y)$ 表示出来。将 $x = 0$ 代入推论2中的式子(1)、(2)、(3)、(4)得

$T_{n} (0, y) = T_{1, n} (0, y) - N_{n} (0, y)$ ， (6)

其中 $T_{1, n} (0, y)$ 和 $N_{n} (0, y)$ 都是整系数多项式且满足以下递归关系

$T_{1, n} (0, y) = y T_{1, n - 1}^{2} (0, y) + 2 T_{1, n - 1} (0, y) N_{n - 1} (0, y) - N_{n - 1}^{2} (0, y)$ ， (7)

$N_{n} (0, y) = 2 T_{1, n - 1} (0, y) N_{n - 1} (0, y) - N_{n - 1}^{2} (0, y)$ ， (8)

初始条件为

$T_{1, 0} (0, y) = 1$ ， $N_{0} (0, y) = 1$ 。 (9)

由(8)、(9)得

$N_{n} (0, y) = T_{1, n} (0, y) - y T_{1, n - 1}^{2} (0, y)$ (10)

由(6)、(10)得

$T_{n} (0, y) = y T_{1, n - 1}^{2} (0, y)$ (11)

由(7)、(10)得

$T_{1, n} (0, y) = y T_{1, n - 1}^{2} (0, y) + 2 T_{1, n - 1} (0, y) (T_{1, n - 1} (0, y) - y^{2} T_{1, n - 2}^{2} (0, y)) - {(T_{1, n - 1} (0, y) - y^{2} T_{1, n - 2}^{2} (0, y))}^{2}$

化简得

$T_{1, n} (0, y) - (1 + y) T_{1, n - 1}^{2} (0, y) + y^{2} T_{1, n - 2}^{4} (0, y) = 0$ (12)

由(12)变换得

$\frac{T_{1, n} (0, y)}{T_{1, n - 1}^{2} (0, y)} = 1 + y - \frac{y^{2} T_{1, n - 2}^{4} (0, y)}{T_{1, n - 1}^{2} (0, y)}$ ，

对 $n \geq 2$ 时，引入中间变量 $\frac{T_{1, n} (0, y)}{T_{1, n - 1}^{2} (0, y)} = b_{n}$ ，故可以推出

$b_{n} = 1 + y - {(\frac{y}{b_{n - 1}})}^{2}$ ， (13)

由(7)、(9)可推得 $T_{1, 1} (0, y) = 1 + y$ ，令 $n = 1$ ，代入 $\frac{T_{1, n} (0, y)}{T_{1, n - 1}^{2} (0, y)} = b_{n}$ ，得初始值

$b_{1} = 1 + y$ ， (14)

因为 $\frac{T_{1, n} (0, y)}{T_{1, n - 1}^{2} (0, y)} = b_{n}$ ，所以 $T_{1, n} (0, y) = b_{n} T_{1, n - 1}^{2} (0, y)$ ，故有

$\begin{matrix} T_{1, n - 1} (0, y) = b_{n - 1} T_{1, n - 2}^{2} (0, y) = b_{n - 1} {(b_{n - 2} T_{1, n - 3}^{2} (0, y))}^{2} \\ = b_{n - 1} b_{n - 2}^{2} {(b_{n - 3} T_{1, n - 4}^{2} (0, y))}^{4} = \prod_{i = 1}^{n - 1} b_{_{i}}^{2^{(n - 1 - i)}} {(T_{1, 0}^{2} (0, y))}^{2^{(n - 1 - i)}} = \prod_{i = 1}^{n - 1} b_{_{i}}^{2^{(n - 1 - i)}} \end{matrix}$ (15)

将(16)代入(11)得

$T_{n} (0, y) = y T_{1, n - 1}^{2} (0, y) = y {\prod_{i = 1}^{n - 1} (b_{i}^{2^{(n - 1 - i)}})}^{2}$ (16)

由Farey图 $G_{n}$ 的结构，我们不难计算出 $G_{n}$ 的顶点数、边数和连通分支个数分别为 $| V (G_{n}) | = 2^{n} + 1$ ， $| E (G_{n}) | = 2^{n + 1} - 1$ ， $k (G_{n})$ ，令 $y = 1 - λ$ ，由(5)、(16)、(13)、(14)式得 $n \geq 2$ 时，

$\begin{matrix} F (G_{n}; λ) = {(- 1)}^{- | V (G_{n}) | + | E (G_{n}) | + k (G_{n})} T (G_{n}; 0, 1 - λ) = {(- 1)}^{- | V (G_{n}) | + | E (G_{n}) | + k (G_{n})} T_{n} (0, 1 - λ) \\ = {(- 1)}^{- 2^{n} - 1 + 2^{n + 1} - 1 + 1} T_{n} (0, 1 - λ) = - T_{n} (0, 1 - λ) \\ = (λ - 1) \prod_{i = 1}^{n - 1} {(b_{i}^{2 (n - 1 - i)})}^{2} \end{matrix}$ ， (17)

其中 $b_{n} = 2 - λ - {(\frac{1 - λ}{b_{n - 1}})}^{2}$ ， $b_{1} = 2 - λ$ 。

又因为 $n = 1$ ，时 $G_{1} = K_{3}$ ，所以 $F (G_{1}) = (λ - 1)$ ，令 $b_{0} = 1$ ，则 $n = 1$ 时，也满足(17)式，综上，定理得证。

定理3：Farey图 $G_{n} (n \geq 1)$ 的面色多项式为

$P * (G_{n}; λ) = λ (λ - 1) \prod_{i = 1}^{n - 1} {(b_{i}^{2 (n - 1 - i)})}^{2}$

其中 $b_{0} = 1$ ，且 $n \geq 2$ 时， $b_{n} = 2 - λ - {(\frac{1 - λ}{b_{n - 1}})}^{2}$ ，初始值 $b_{1} = 2 - λ$ 。

证明：由引理2得， $F (G_{n}; λ) = \frac{P (G_{n} *; λ)}{λ}$ 。再由对偶图的定义可知

$P * (G_{n}; λ) = P (G_{n} *; λ)$ ，

所以

$P * (G_{n}; λ) = λ F (G_{n}; λ)$ ，

在定理2中已经推导出 $F (G_{n}; λ)$ 的结果，代入 $P * (G_{n}; λ) = λ F (G_{n}; λ)$ ，定理得证。

4. Farey图的对偶图的色多项式和流多项式

定理4：Farey图 $G_{n} (n \geq 1)$ 的对偶图 $G_{n} *$ 点色多项式为

$P (G_{n} *; λ) = λ (λ - 1) \prod_{i = 1}^{n - 1} {(b_{i}^{2 (n - 1 - i)})}^{2}$

其中 $b_{0} = 1$ ，且 $n \geq 2$ 时， $b_{n} = 2 - λ - {(\frac{1 - λ}{b_{n - 1}})}^{2}$ ，初始值 $b_{1} = 2 - λ$ 。

证明：由对偶图的定义可知 $P * (G_{n}; λ) = P (G_{n} *; λ)$ ，又因为定理3，此定理得证。

定理5：Farey图 $G_{n} (n \geq 1)$ 的对偶图 $G_{n} *$ 的面色多项式为

$P * (G_{n} *; λ) = λ (λ - 1) {(λ - 2)}^{2^{n} - 1}$ 。 (20)

证明：由对偶图的定义可知， $G_{n}$ 的对偶图 $G_{n} *$ ，和 $G_{n} *$ 的对偶图 $(G_{n} *) *$ 存在以下关系式，

$P * (G_{n} *; λ) = P ((G_{n} *) *; λ)$ ， (18)

又因为 $G_{n}$ 是连通图，所以 $(G *) * ≅ G$ ，

故 $P * (G_{n} *; λ) = P (G_{n}; λ)$ ， (19)

又因为定理1，此定理得证。

定理6：Farey图 $G_{n} (n \geq 1)$ 的对偶图 $G_{n} *$ 的流多项式为

$F (G_{n} *; λ) = (1 - λ) {(2 - λ)}^{2^{n} - 1}$

证明：由引理2得， $F (G_{n} *; λ) = \frac{P ((G_{n} *) *; λ)}{λ}$ 。又因为式子(19)、(18)、(20)

所以定理得证。

文章引用

单美玲. Farey图及其对偶图的色多项式和流多项式
Chromatic Polynomials and Flow Polynomials of Farey Graphs and Their Dual Graphs[J]. 运筹与模糊学, 2018, 08(04): 145-150. https://doi.org/10.12677/ORF.2018.84018

参考文献

1. Birkhoff, G.D. (1912) A Determinant Formula for the Number of Ways of Coloring a Map. Annals of Mathematics, 14, 42-46. https://doi.org/10.2307/1967597

2. 李慰萱, 田丰. 关于图的色多项式的若干问题[J]. 数学学报, 1978, 21(3), 223-230.

3. Brimkov, B. and Hicks, I.V. (2010) Chromatic and Flow Polynomials of Generalized Vertex Join Graphs and Outerplanar Graphs. Discrete Applied Mathematics, 204, 13-21. https://doi.org/10.1016/j.dam.2015.10.016

4. 廖云华. 图多项式若干问题研究[D]: [博士学位论文]. 长沙: 湖南师范大学, 2015.

5. J.A.邦迪, U.S.R.默蒂. 图论及其应用[M]. 北京: 科学出版社, 1987.

6. Ellis-Monaghan, J.A. and Merino, C. (2011) Graph Polynomials and Their Applications I: The Tutte Poly-nomial. In: Dehmer, M., Ed., Structural Analysis of Complex Networks, Birkhäuser, Boston, 219-255. https://doi.org/10.1007/978-0-8176-4789-6_9

期刊菜单