本文選題：符號圖 + 符號模流　； 參考：《安徽大學(xué)》2017年碩士論文

【摘要】：為研究四色問題,Tutte提出了整數(shù)流理論.隨后,整數(shù)流理論逐漸成為圖論的經(jīng)典研究方向.符號圖是既含正邊又含負(fù)邊的圖,是一般圖模型的自然推廣.在可定向曲面上,頂點(diǎn)染色的對偶問題是一般圖上的整數(shù)流;在不可定向曲面上,頂點(diǎn)染色的對偶問題是符號圖上的整數(shù)流.相比于一般圖上的整數(shù)流,符號圖上的流尚處于起步階段,有廣闊的研究空間,有很多有意義的研究工作值得探討.模流與圓流是討論一般圖上流問題的經(jīng)典研究工具.然而在符號圖上,模流、圓流與整數(shù)流之間的關(guān)系更為復(fù)雜.本文即討論了關(guān)于符號模流與符號圓流的幾個(gè)問題.本文第一章首先介紹了符號流理論的研究背景,其次介紹了常用的概念和符號,最后介紹了文章所研究的問題,研究進(jìn)展及本文所得的主要結(jié)果.本文第二章主要是討論了符號模流中的兩個(gè)問題.在[17]中,Macajova等刻畫了連通的非平衡符號圖存在處處非零整數(shù)流的等價(jià)條件.本章的第二節(jié)給出了連通的非平衡符號圖存在處處非零模流的等價(jià)條件.在[31]中,魏二玲等證明了如果符號6-流猜想在符號立方圖是成立的,則符號6-流猜想就是成立的.因此,符號立方圖上的流問題非常值得關(guān)注.在[18]中,Macajova等刻畫了存在處處非零的Z3-流和Z4-流的符號立方圖.第二章的第三節(jié),我們刻畫了存在處處非零的Z5-流的符號立方圖.本文第三章主要討論了符號圓流的一個(gè)問題.設(shè)φc(G,σ)和φ(G,σ)分別是(G,σ)的符號圓流數(shù)和符號整數(shù)流數(shù).2011年,Raspaud和朱緒鼎[20]證明了φ(G,σ)2[φc(G,σ)]-1.2015年,Macajova和Steffen[19]給出一個(gè)例子,證明上面上界不能被改進(jìn).本章,我們證明了在有流的環(huán)歐拉符號圖上,φ(G,σ)≤[φ(G,σ)]even.
[Abstract]:In order to study the four-color problem Tutte puts forward the integer flow theory. Subsequently, integer flow theory has gradually become the classical research direction of graph theory. Symbolic graph is a graph with both positive and negative edges. It is a natural generalization of the general graph model. On orientable surfaces, the dual problem of vertex coloring is an integer flow on a general graph, and on an unorientable surface, the dual problem of vertex coloring is an integer flow on a symbolic graph. Compared with the integer flow on the general graph, the flow on the symbol graph is still in its infancy, and there is a wide space for research, and a lot of meaningful research work is worth discussing. Mode flow and circular flow are the classical research tools to discuss the flow problem on a general graph. However, in symbolic graph, the relationship between mode flow, circular flow and integer flow is more complicated. In this paper, some problems about symbolic mode flow and symbolic circular flow are discussed. In the first chapter, the research background of symbolic flow theory is introduced, then the commonly used concepts and symbols are introduced. Finally, the problems studied in this paper, the research progress and the main results obtained in this paper are introduced. In the second chapter, two problems in symbolic mode flow are discussed. In [17], Macajova et al characterizes the equivalent conditions for the existence of everywhere nonzero integer flows in connected nonequilibrium signed graphs. In the second section of this chapter, we give the equivalent conditions for the existence of everywhere nonzero mode flow in a connected nonequilibrium symbolic graph. In [31], Wei Erling and others proved that if the symbolic 6-flow conjecture is true in the symbolic cubic graph, then the symbolic 6-flow conjecture is true. Therefore, the flow problem on symbolic cubic graphs is of great concern. In [18], Macajova et al characterizes the symbolic cubic graphs of Z _ 3-stream and Z _ 4-stream with everywhere nonzero. In the third section of Chapter 2, we characterize the symbolic cubic graphs of Z _ 5-flows with nonzero everywhere. In the third chapter, a problem of symbolic circular flow is discussed. Let 蠁 C G, 蟽) and 蠁 G G, 蟽) be the signed circle flow number and signed integer flow number of G, 蟽, respectively. In 2011, Raspaud and Zhu Xuding [20] proved that 蠁 G, 蟽 n 2 [蠁 C G, 蟽]-1. In 2015, Macajova and Steffen [19] give an example to prove that the upper bound can not be improved. In this chapter, we prove that 蠁 G, 蟽) 鈮，

本文編號：2047371