【作者】 冯文丽；

【导师】 李胜家；

【作者基本信息】 山西大学 ， 运筹学与控制论， 2005， 硕士

【摘要】 本文分为两章,第一章研究了连通无向图G的顶点扩张图（见定义1.13）的最小直径定向问题。图的最小直径定向问题的研究来自对单行街和流言问题的研究,目前这两个问题仍为研究的热点。单行街问题可以追溯到Robbins的经典论文[3],文[3]给出著名的单行街定理:一个连通的无向图G有强连通定向当且仅当G无桥。对一个无桥的连通无向图G,设Ω（G）表示G的强连通定向集合,对每一个D∈Ω（G）,我们用d（D）（相应d（G））表示D（相应G）的直径。定义（?）（G）=min{d（D）|D∈Ω（G）}。G（s₁,s₂,…,s_n）（此记号来自[1]）为连通无向图G的顶点扩张图（n≥3,s_i≥2,i=1,2,…,n）,Koh和Tay在他们的论文[1]中得到不等式: d（G）≤（?）（G（s₁,s₂,…,s_n））≤d（G）+2因而所有形如G（s₁,s₂,…,s_n）的图被分为三类, φ_i={G（s₁,s_<sub>2,…,s_n）|（?）（G（s₁,s₂,…,s_n））=d（G）+i},i=0,1,2并且他们还提出一个猜想:如果G是直径至少为3的无向图,那么G的顶点扩张图不属于第三类图φ₂,即G（s₁,s₂,…,s_n）（?）φ₂,（s_i≥2,i=1,2,…,n）,举出反例和给出证明都很困难,本文验证了对于一类特殊二部图—树,它的顶点扩张图是成立的,即当G是树时猜想是成立的。同时它也是文[1]中的一个结果的推广。 第二章中从图的不减度序列角度给出了一类度极大的非哈密尔顿简单平衡二部图,并且证明了:任何非哈密尔顿的简单平衡二部图,它的不减度序列一定弱于此类图中的某个图b_m,n的度序列。本文给出了这类图b_m,n的结构。更多还原

【Abstract】 This paper have two chapters, in the first chapter we deal with the problem on minimum diameter orientations of graph G vertex-multiplications(see Definition 1.13). It is the one-way and gossip problems that lead to consinder minimum diameter orientations of graph. Graph theoretical modelling of the one-way street problem can be traced back to the classical paper of Robbins[3]. In [3] Robbins’ celebrated one-way street theorem states that a connected graph G has a strong orientation if and only if no edge of G is a brige. For a brigeless connected graph G, let Ω,(G) be the family of strong orientations of G, and for any D∈Ω(G), we denote by d{D)(resp., d(G)) the diamiter of D(resp., G). Define d(G)=min{d(D)|DΩ(G)}. G(s1,S2,...,sn)(this notation comes from [1]) is a G vertex-multiplication for any connected graph G of order n>3 and any sequence (si) with Si≥2, i = 1,2,..., n. Koh and Tay in their paper[1] give a inequality as follows:All graphs of the form G(s1,S2,...,sn) are thus divided into the following three classes: φ = {G(s1,s2 ... sn)\d(G(s1 S2,...,sn)) = d(G) + i}, i = 0,1,2In[l] Koh and Tay also give such a conjecture: if G is a graph such that d(G) > 3 then G(s1, s2,..., sn)∈φ2, Si ≥ 2, (i = l,2,...,n). It is very defficult to give a counterexample or a proof. In this paper we’ll verify that it is true for tree(a special type of bipartite graph)vertex-multiplications, and it is a extention to one of the results in paper[l].In the second chapter, from the point of view of non-decreasing degree sequence we give a degree-maximal non-Hamilton simple balanced bipartite graph bm,n. We give a result below. For arbitrary non-Hamilton simple balanced bipartite graph, its non-decreasing degree sequence is majorised~[2] by that of a degree-maximal non-Hamilton simple balanced bipartite graph, i.e, bm,n In this paper, we give the structure of bm,n更多还原