Advances in Applied Mathematics
Vol.
12
No.
04
(
2023
), Article ID:
64072
,
4
pages
10.12677/AAM.2023.124153
不含平衡圈的符号图的分解
朱晨波
浙江师范大学数学科学学院,浙江 金华
收稿日期:2023年3月13日;录用日期:2023年4月9日;发布日期:2023年4月19日
摘要
本文主要在符号图框架拟阵的定义下,通过证明所含的圈中没有平衡圈的符号图G上的参数 大于等于 ,从而证明在 ,以及任意的非负整数d的条件下,不含平衡圈的符号图能分解成两个独立集 和I,且I在G中导出图 中顶点最大度为d。
关键词
符号图,拟阵,图的分解,最大平均度
Decomposition of Signed Graphs without Contain Balanced Cycle
Chenbo Zhu
School of Mathematical Science, Zhejiang Normal University, Jinhua Zhejiang
Received: Mar. 13th, 2023; accepted: Apr. 9th, 2023; published: Apr. 19th, 2023
ABSTRACT
In this paper, we study the signed graph based on the frame matroid. For the signed graph G without contains any balanced cycle, we prove the parameter is greater than , then we prove when and any positive integers d, the signed graph G without contains any balanced cycle can decompose into two independent sets and I, the degree of vertex in the induced graph is at most d.
Keywords:Signed Graphs, Matroids, Decomposition of Graphs, Maximum Average Degree
Copyright © 2023 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 基本概念
在本文中,我们只研究有限图,所研究的有限图中允许存在平行边但不存在环,给定一个图G,我们用 来定义图G的顶点集,用 来定义图G的边集。令 是图G中顶点的个数, 是图G中的边的个数。如果X是顶点集 的子集,则用 来表示是G的由顶点集X所导出的的导出子图,以及 是图G通过删去顶点集X后得到的子图。如果S是一组边集,则边导出子图 是指G的一个子图且它的边集是S,顶点集合是由所有S中的边的端点所构成的。
用 定义为所有v的邻点的集合, 是所有与v相关联的边的集合,令 表示v的度,我们有 。
给定一个图G,图G的分解组成了所有边不交的子图使得它们的并是G。图G的荫度是指最小数目的森林需要去分解图G的。图G的分数荫度定义如下:
一个符号图 ,它是由一个基础图 和一个映射 组成。这个映射满足 ,它是G的边集映到 的有序对。设e为图G的一条边,当 时称e为正边,当 时称e为负边。如果符号图 中的一个圈包含偶数条负边,则称这个圈为平衡圈,如果它包含奇数条负边,则称这个圈为非平衡圈。有时候平衡圈被称为正圈而非平衡圈也被称为负圈。
下面我们介绍一些拟阵的相关性质。拟阵的性质在很多场合都有用到,尤其是在组合领域。给定一个有限集E,E上的一个遗传系统M是由 的子集的集合 组成, 中的每个元素都是 的一个子集。我们称 是拟阵M上的一个独立集,并且 中的任何集合都不是独立集。记 是所有基的集合(基指的是最大独立集)。记 是所有最小非独立集的集合。若 ,用 表示为集合X的秩函数,它代表X中所包含的最大独立集的个数。
一个E中的元素e被称为环,如果它不出现在任何独立集中。在这篇文章中所讨论的拟阵都是无环的。对于E上的拟阵M,下面的两个参数是我们主要感兴趣的:
令 且 ,我们能得到 。以下两个定理已经被学者Edmonds证明了。
定理1.1 ( [1] )对于E上的拟阵M,它的独立集的并能覆盖E的最小数目为 。
定理1.2 ( [2] )对于E上的拟阵M,E上含有最大的不相交的基的数目为 。
下面我们回到图论上,给出一个图G最大平均度的定义,图G的最大平均度数 定义如下:
其中H是G的子图。
下面的定理是我们所熟知的。
定理1.3 ( [3] )令G是一个图,则存在G的一个定向 使得 当且仅当 。
推论1.4对任何图G,如果 ,则G可以分解成k个伪森林。
一个伪树是一个连通图且包含至多一个圈的,一个图是一个伪森林是指它的每个连通分支中包含至多一个圈,在文献 [4] 中证明了如下伪森林分解的类九龙树猜想。
定理1.5 ( [4] )对于任意的非负整数 ,如果G是一个图且满足 ,则G可以分解成 个伪森林,且其中一个伪森林它的顶点最大度为d。
2. 主要定理
本文主要证明的定理如下:
定理2.1对 和任意的非负整数d,令G是所含圈中不含平衡圈的连通符号图。M是 上的一个框架拟阵。若它的边集满足 ,则G能分解成两个独立集 和I,
且I在G中的导出图 的顶点最大度为d。
3. 主要定理证明
在这一章节中我们证明定理2.1,我们先给出符号图上框架拟阵的定义:
定义3.1对于符号图 的边集E,E上的框架拟阵 定义如下:它的独立集是指它的每个连通分支中至多包含一个圈,且如果恰好包含一个圈,则这个圈一定是非平衡圈。
下面我们开始证明定理2.1。
证明采用反证法,假设定理2.1是不正确的,令G是一个顶点极小反例。若G中至多含有一个非平衡圈,这种情况已经在文献 [5] 中被证明。下面我们证明G中至少存在两个非平衡圈的情况。首先我们能证明如下的定理。
定理3.1对于G中的任意一个基B,都满足B中包含一个非平衡圈。
在证明上述定理之前,我们可以得到如下引理。
引理3.2 G的边集能分解成一个基 和一个独立集I。
这个引理的证明已经在文献 [5] 中被证明。下面我们回过头来证明定理3.1。
定理3.1的证明假设 中不包含非平衡圈,因为G中至少包含两个非平衡圈,并且G中不含平衡圈,则存在一条边 ,使得 中至多包含一个非平衡圈,因此 还是一个独立集,但 ,这与 是一个基矛盾。这就完成了定理3.1的证明。
下面我们开始证明定理2.1。对于这个定理的证明,我们需要用到定理1.3的 的特殊情况。
引理3.3令G是一个图,则存在一个G的定向 使得 当且仅当 。
我们首先证明它满足 这个条件。
假设我们找了一个子图H,且有 ,则我们能得到这个子图H一定是连通的。假设H不连通,因为G是一个连通图,则存在边 ,使得 这个子图有 。这样我们就得到了一个子图 ,使得 。如果 ,这就矛盾于我们选择 。因此如果我们选择了一个不连通的子图H,则通过增加一条边 使得 这个子图满足 ,如果 是连通图,则它就是我们想要的,如果 不连通,则继续通过加边的方式使得新得到的子图的参数是等于 ,每经过一次这个过程,子图的连通分支数就会少1,不断重复上述过程最后能得到一个连通的子图。
下面我们通过对H中是否包含非平衡圈来证明 。如果H中不包含非平衡圈,那么H中就无圈,因为G是不含平衡圈的图,则我们有H是一棵树,所以 。如果H中包含非平衡圈,则H中至少包含一个非平衡圈,我们有 。又因为我们假设G中至少包含两个非平衡圈且 ,可以得到 。
我们知道定理2.1中的条件 ,则有 ,我们忽视符号图G中边的符号,由引理3.3可以得到存在G的一个定向 使得 。通过定理1.5的得到的特殊情况如下:
引理3.4 对于 以及任意的非负整数d,如果G是一个图且满足 ,则G可以分解成2个伪森林,且其中一个伪森林它的顶点最大度为d。
由引理3.4知道G能分解成2个伪森林且其中一个伪森林中顶点的最大度为d。回想起我们在定理2.1中对符号图的限制可得,符号图中是不含平衡圈的,因此在忽视符号的图G中加上边集的符号之后会发现,对于符号图 ,它的每个连通分支中至多含有一个圈,且如果含有一个圈,这个圈一定是非平衡圈不可能是平衡圈,这就结束了证明。
4. 结语
在图论中,对森林分解方向的研究,很多学者做出了杰出的贡献,但对于不同的拟阵,在不同的图类上的分解研究还值得进一步探讨。本文给出了在符号图的框架拟阵下,通过应用伪森林类似的九龙树猜想,来证明符号图上框架拟阵下,不含平衡圈的符号图能分解成两个独立集 和I,且I在G中导出图 中顶点最大度为d,对于把k拓展成任意的非负整数后的研究是值得进一步探讨的问题。
文章引用
朱晨波. 不含平衡圈的符号图的分解
Decomposition of Signed Graphs without Contain Balanced Cycle[J]. 应用数学进展, 2023, 12(04): 1483-1486. https://doi.org/10.12677/AAM.2023.124153
参考文献
- 1. Edmonds, J. (1965) Minimum Partition of a Matroid into Independent Subsets. Journal of Research of the National Bu-reau of Standards, Section B, 69B, 67-72. https://doi.org/10.6028/jres.069B.004
- 2. Edmonds, J. (1965) Leh-man’s Switching Game and a Theorem of Tutte and Nash-Williams. Journal of Research of the National Bureau of Standards, Section B, 69B, 73-77. https://doi.org/10.6028/jres.069B.005
- 3. Kierstead, H.A. and Yang, D. (2005) Very Asymmetric Marking Games. Order, 22, 93-107. https://doi.org/10.1007/s11083-005-9012-y
- 4. Fan, G., Li, Y., Song, N. and Yang, D. (2015) Decomposing a Graph into Pseudoforests with One Having Bounded Degree. Journal of Combinatorial Theory, Series B, 115, 72-95. https://doi.org/10.1016/j.jctb.2015.05.003
- 5. 方旭倩. 强九龙树猜想及九龙树定理的推广研究[D]: [硕士学位论文]. 金华: 浙江师范大学, 2021.