不含平衡圈的符号图的分解

Decomposition of Signed Graphs without Contain Balanced Cycle

摘要: 本文主要在符号图框架拟阵的定义下，通过证明所含的圈中没有平衡圈的符号图G上的参数大于等于，从而证明在k=1，以及任意的非负整数d的条件下，不含平衡圈的符号图能分解成两个独立集B₁和I，且I在G中导出图G[I]中顶点最大度为d。

Abstract: In this paper, we study the signed graph based on the frame matroid. For the signed graph G with-out contains any balanced cycle, we prove the parameter is greater than , then we prove when k=1 and any positive integers d, the signed graph G without con-tains any balanced cycle can decompose into two independent sets B₁ and I, the degree of vertex in the induced graph G[I] is at most d.

1. 基本概念

在本文中，我们只研究有限图，所研究的有限图中允许存在平行边但不存在环，给定一个图G，我们用 $V\left(G\right)$ 来定义图G的顶点集，用 $E\left(G\right)$ 来定义图G的边集。令 $v\left(G\right)=\left|V\left(G\right)\right|$ 是图G中顶点的个数， $e\left(G\right)=\left|E\left(G\right)\right|$ 是图G中的边的个数。如果X是顶点集 $V\left(G\right)$ 的子集，则用 $G\left[X\right]$ 来表示是G的由顶点集X所导出的的导出子图，以及 $G-X$ 是图G通过删去顶点集X后得到的子图。如果S是一组边集，则边导出子图 $G\left[S\right]$ 是指G的一个子图且它的边集是S，顶点集合是由所有S中的边的端点所构成的。

用 $N_G\left(v\right)$ 定义为所有v的邻点的集合， $E_G\left(v\right)$ 是所有与v相关联的边的集合，令 $d_G\left(v\right)$ 表示v的度，我们有 $d_G\left(v\right)=\left|E_G\left(v\right)\right|$ 。

给定一个图G，图G的分解组成了所有边不交的子图使得它们的并是G。图G的荫度是指最小数目的森林需要去分解图G的。图G的分数荫度定义如下：

${\Gamma }_f\left(G\right)={\max }_{H\subseteq G,v\left(H\right)>1}\frac{e\left(H\right)}{v\left(H\right)-1}.$

一个符号图 $\left(G,\sigma \right)$ ，它是由一个基础图 $G=\left(V\left(G\right),E\left(G\right)\right)$ 和一个映射 $\sigma$ 组成。这个映射满足 $\sigma :E\left(G\right)\to \left\{+1,-1\right\}$ ，它是G的边集映到 $\left\{+1,-1\right\}$ 的有序对。设e为图G的一条边，当 $\sigma \left(e\right)=1$ 时称e为正边，当 $\sigma \left(e\right)=-1$ 时称e为负边。如果符号图 $\left(G,\sigma \right)$ 中的一个圈包含偶数条负边，则称这个圈为平衡圈，如果它包含奇数条负边，则称这个圈为非平衡圈。有时候平衡圈被称为正圈而非平衡圈也被称为负圈。

下面我们介绍一些拟阵的相关性质。拟阵的性质在很多场合都有用到，尤其是在组合领域。给定一个有限集E，E上的一个遗传系统M是由 $2^E$ 的子集的集合 $I_M$ 组成， $I_M$ 中的每个元素都是 $2^E$ 的一个子集。我们称 $I_M$ 是拟阵M上的一个独立集，并且 $2^E-I_M$ 中的任何集合都不是独立集。记 $B_M$ 是所有基的集合(基指的是最大独立集)。记 $C_M$ 是所有最小非独立集的集合。若 $X\subseteq E$ ，用 $r_M\left(X\right)$ 表示为集合X的秩函数，它代表X中所包含的最大独立集的个数。

一个E中的元素e被称为环，如果它不出现在任何独立集中。在这篇文章中所讨论的拟阵都是无环的。对于E上的拟阵M，下面的两个参数是我们主要感兴趣的：

$\beta \left(M\right)=ma{x}_{\varnothing \ne X\subseteq E}\frac{\left|X\right|}{r_M\left(X\right)},\phi \left(M\right)=mi{n}_{r_M\left(X\right)<r\left(M\right)}\frac{\left|E\right|-\left|X\right|}{r_M\left(E\right)-r_M(\; X\; )}$

令 $X=E$ 且 $X\ne \varnothing$ ，我们能得到 $\beta \left(M\right)\ge \frac{\left|E\right|}{r\left(M\right)}\ge \phi \left(M\right)$ 。以下两个定理已经被学者Edmonds证明了。

定理1.1 ( [1] )对于E上的拟阵M，它的独立集的并能覆盖E的最小数目为 $\beta \left(M\right)$ 。

定理1.2 ( [2] )对于E上的拟阵M，E上含有最大的不相交的基的数目为 $\phi \left(M\right)$ 。

下面我们回到图论上，给出一个图G最大平均度的定义，图G的最大平均度数 $mad\left(G\right)$ 定义如下：

$mad\left(G\right)=ma{x}_{H\subseteq G}\frac{2e\left(H\right)}{v(\; H\; )}$

其中H是G的子图。

下面的定理是我们所熟知的。

定理1.3 ( [3] )令G是一个图，则存在G的一个定向 $\sigma$ 使得 ${\Delta }^{+}\left(G^{\sigma }\right)\le k$ 当且仅当 $mad\left(G\right)\le 2k$ 。

推论1.4对任何图G，如果 $mad\left(G\right)\le 2k$ ，则G可以分解成k个伪森林。

一个伪树是一个连通图且包含至多一个圈的，一个图是一个伪森林是指它的每个连通分支中包含至多一个圈，在文献 [4] 中证明了如下伪森林分解的类九龙树猜想。

定理1.5 ( [4] )对于任意的非负整数 $k,d$ ，如果G是一个图且满足 $mad\left(G\right)\le 2k+\frac{2d}{k+d+1}$ ，则G可以分解成 $k+1$ 个伪森林，且其中一个伪森林它的顶点最大度为d。

2. 主要定理

本文主要证明的定理如下：

定理2.1对 $k=1$ 和任意的非负整数d，令G是所含圈中不含平衡圈的连通符号图。M是 $E\left(G\right)$ 上的一个框架拟阵。若它的边集满足 $\beta \left(M\right)=ma{x}_{\varnothing \ne X\subseteq E}\frac{\left|X\right|}{r_M\left(X\right)}\le 1+\frac{d}{d+2}$ ，则G能分解成两个独立集 $B_1$ 和I，

且I在G中的导出图 $G\left[I\right]$ 的顶点最大度为d。

3. 主要定理证明

在这一章节中我们证明定理2.1，我们先给出符号图上框架拟阵的定义：

定义3.1对于符号图 $\left(G,\sigma \right)$ 的边集E，E上的框架拟阵 $\left(E,I_M\right)$ 定义如下：它的独立集是指它的每个连通分支中至多包含一个圈，且如果恰好包含一个圈，则这个圈一定是非平衡圈。

下面我们开始证明定理2.1。

证明采用反证法，假设定理2.1是不正确的，令G是一个顶点极小反例。若G中至多含有一个非平衡圈，这种情况已经在文献 [5] 中被证明。下面我们证明G中至少存在两个非平衡圈的情况。首先我们能证明如下的定理。

定理3.1对于G中的任意一个基B，都满足B中包含一个非平衡圈。

在证明上述定理之前，我们可以得到如下引理。

引理3.2 G的边集能分解成一个基 $B_1$ 和一个独立集I。

这个引理的证明已经在文献 [5] 中被证明。下面我们回过头来证明定理3.1。

定理3.1的证明假设 $G\left[B_1\right]$ 中不包含非平衡圈，因为G中至少包含两个非平衡圈，并且G中不含平衡圈，则存在一条边 $e\in G\left[I\right]=G-G\left[B_1\right]$ ，使得 $G\left[B_1\right]+e$ 中至多包含一个非平衡圈，因此 $G\left[B_1\right]+e$ 还是一个独立集，但 $\left|G\left[B_1\right]+e\right|>\left|G\left[B_1\right]\right|$ ，这与 $B_1$ 是一个基矛盾。这就完成了定理3.1的证明。

下面我们开始证明定理2.1。对于这个定理的证明，我们需要用到定理1.3的 $k=1$ 的特殊情况。

引理3.3令G是一个图，则存在一个G的定向 $\sigma$ 使得 ${\Delta }^{+}\left(G^{\sigma }\right)\le 1$ 当且仅当 $mad\left(G\right)\le 2$ 。

我们首先证明它满足 $mad\left(G\right)\le 2$ 这个条件。

假设我们找了一个子图H，且有 $\beta \left(M\right)=\frac{\left|H\right|}{r_M\left(H\right)}$ ，则我们能得到这个子图H一定是连通的。假设H不连通，因为G是一个连通图，则存在边 $e\in G-H$ ，使得 $H+e$ 这个子图有 $\frac{\left|H+e\right|}{r_M\left(H+e\right)}\ge \frac{\left|H\right|}{r_M\left(H\right)}$ 。这样我们就得到了一个子图 $H+e$ ，使得 $\frac{\left|H+e\right|}{r_M\left(H+e\right)}=\frac{\left|H\right|}{r_M\left(H\right)}$ 。如果 $\frac{\left|H+e\right|}{r_M\left(H+e\right)}>\frac{\left|H\right|}{r_M\left(H\right)}$ ，这就矛盾于我们选择 $\beta \left(M\right)=ma{x}_{\varnothing \ne X\subseteq E}\frac{\left|X\right|}{r_M\left(X\right)}=\frac{\left|H\right|}{r_M\left(H\right)}$ 。因此如果我们选择了一个不连通的子图H，则通过增加一条边 $e\in G-H$ 使得 $H+e$ 这个子图满足 $\beta \left(M\right)=ma{x}_{\varnothing \ne X\subseteq E}\frac{\left|X\right|}{r_M\left(X\right)}=\frac{\left|H+e\right|}{r_M\left(H+e\right)}=\frac{\left|H\right|}{r_M\left(H\right)}$ ，如果 $H+e$ 是连通图，则它就是我们想要的，如果 $H+e$ 不连通，则继续通过加边的方式使得新得到的子图的参数是等于 $\frac{\left|H\right|}{r_M\left(H\right)}$ ，每经过一次这个过程，子图的连通分支数就会少1，不断重复上述过程最后能得到一个连通的子图。

下面我们通过对H中是否包含非平衡圈来证明 $mad\left(G\right)\le 2\beta \left(M\right)$ 。如果H中不包含非平衡圈，那么H中就无圈，因为G是不含平衡圈的图，则我们有H是一棵树，所以 $\beta \left(M\right)=\frac{\left|H\right|}{r_M\left(H\right)}=\frac{e\left(H\right)}{v\left(H\right)-1}=1$ 。如果H中包含非平衡圈，则H中至少包含一个非平衡圈，我们有 $\beta \left(M\right)=\frac{\left|H\right|}{r_M\left(H\right)}=\frac{e\left(H\right)}{v\left(H\right)}\ge 1$ 。又因为我们假设G中至少包含两个非平衡圈且 $r_M\left(H\right)\le v\left(H\right)$ ，可以得到 $2\beta \left(M\right)\ge mad\left(G\right)$ 。

我们知道定理2.1中的条件 $\beta \left(M\right)\le 1+\frac{d}{d+2}$ ，则有 $mad\left(G\right)\le 2\beta \left(M\right)\le 2+\frac{2d}{d+2}$ ，我们忽视符号图G中边的符号，由引理3.3可以得到存在G的一个定向 $\sigma$ 使得 ${\Delta }^{+}\left(G^{\sigma }\right)\le 1$ 。通过定理1.5的得到的特殊情况如下：

引理3.4 对于 $k=1$ 以及任意的非负整数d，如果G是一个图且满足 $mad\left(G\right)\le 2+\frac{2d}{d+2}$ ，则G可以分解成2个伪森林，且其中一个伪森林它的顶点最大度为d。

由引理3.4知道G能分解成2个伪森林且其中一个伪森林中顶点的最大度为d。回想起我们在定理2.1中对符号图的限制可得，符号图中是不含平衡圈的，因此在忽视符号的图G中加上边集的符号之后会发现，对于符号图 $\left(G,\sigma \right)$ ，它的每个连通分支中至多含有一个圈，且如果含有一个圈，这个圈一定是非平衡圈不可能是平衡圈，这就结束了证明。

4. 结语

在图论中，对森林分解方向的研究，很多学者做出了杰出的贡献，但对于不同的拟阵，在不同的图类上的分解研究还值得进一步探讨。本文给出了在符号图的框架拟阵下，通过应用伪森林类似的九龙树猜想，来证明符号图上框架拟阵下，不含平衡圈的符号图能分解成两个独立集 $B_1$ 和I，且I在G中导出图 $G\left[I\right]$ 中顶点最大度为d，对于把k拓展成任意的非负整数后的研究是值得进一步探讨的问题。