摘 要：图论在现代科学技术中有着广泛的应用，伴随多项式是色多项式的一种代数变形， 它的引入主要是为了便于从补图的角度研究色唯一性与色等价划分，其中寻找图的伴随多 项式的最小根的序是主要方法之一。  本文主要刻画了图的最小负实根性质对已知的一个重要定理给出简化证明，图 G 的伴随多项式的最小根满足条件β G ≥− 4 时参数R1(G)的范围， 以及引入图族伴随多项式的最小根极值，用它对 R(G)  ≥− 1 的图族伴随多项式最小根极值作出了刻画。85992

毕业论文关 键 字：图，图族，伴随多项式，最小根，最小负实根，特征值

Abstract ： Graph theory is widely applied in the modern science and technology, adjoint polynomial is a kind of algebraic polynomial with deformation chromatic polynomial,  it is mainly introduced in order to study the color and uniqueness of chromatic equivalence partition from  the  complement  graph  of  point  of  view,  the  search  of  the  adjoint  polynomial  of  the minimum root sequence diagram is the main method of。 This paper mainly describes the graph with minimal negative real root properties of an important theorem known to simplify proofs   of graph G with polynomial minimum root condition β  G   ≥− 4 R1 (G) when the parameter  range,and introduces the graphswith the smallest root extremal polynomials, and makes some  descriptions on the graphs ofadjoint polynomial of the root extreme with R  G   ≥− 1。

Keywords：maps, graphs, adjoint polynomials, the root, the minimum negative real roots, eigenvalue

目录

1 前言 4

2 图论的基本知识 4

2。1 图论的起源与发展 5

2。2 图的基本概念 5

2。3 图的分类 5

3 图的伴随多项式源Q于W优H尔J论K文M网WwW.youeRw.com 原文+QQ75201.,8766 最小根性质的应用 6

3。1 基本定义 6

3。2 基本引理 6

3。3 图的伴随多项式最小根性质的应用 6

4 图 G 的伴随多项式的最小根 8

4。1 基本定义 8

4。2 基本引理 8

5 一类连通图族伴随多项式的最小根 9

5。1 基本定义 9

5。2 基本引理 10

5。3 主要结果及其证明 11

结论 14

参考文献 15

1 前言

随着科学技术的发展以及学术研究的进步，运用图的色多项式、伴随多项式，结合代 数性质对图的色性（图的着色、色唯一性、色等价、色数等）的研究越来越多。特别是对 于色的唯一性、色的等价的研究。Birkhoff 于年提出了图的多项式，认为其可能是一种攻 克 四 色 猜 想 的 一 种 手 段 ； R。C。Rcad 在 1968 年 在 文 献 《 An introduction to chromatic polynomials》中提到了色的多项式的一些性质；Chao 和 Whitehcad 在 1978 年和 1979 年提 出了色等价图和色唯一图，即用图的色多项式对图进行等价分类；1987 年刘儒英的文献中 提出了图的伴随多项式，研究了图的补图的色唯一性，在此之后，相继出现了一系列关于色的唯一性的文章。  刘儒英在文献[1]和文献[2]中分别给出了路Pn和圈Cn的色唯一性，还有在文献[3]中给出了一类树的补图和 T-形树的色唯一性；李念祖等在文献中[4]给出了森林补图的色唯一性。