Kneser圖的若干性質(zhì)及其自同構(gòu)群.pdf

1、設(shè)Ω是一個給定的集合，其勢為n。定義在這個集合上的Kneser圖J(n,k)的頂點集V是Ω的所有k元子集，若兩個k元子集不相交則它們在圖中關(guān)聯(lián)(其中：n，k是給定的正整數(shù)，并且n>2k，k>1)。Kneser圖是十分重要的一類圖，這是因為許多關(guān)于集合的計數(shù)以及計算問題可以轉(zhuǎn)換為此類圖中的問題加以探討。關(guān)于Kneser圖的研究在國外比較多見，而國內(nèi)在這一方面的研究相對較少。關(guān)于Kneser圖最著名的結(jié)果莫過于被Lovász.L證明的Kne

2、ser猜想。C.D.GodsiI和G.Royle從多個角度對這類圖進行了深入研究并且取得豐富成果。 本文嘗試利用代數(shù)理論主要是群理論來討論Kneser圖的部分性質(zhì)，得到了如下主要結(jié)論。 首先，我們引入確定數(shù)的概念利用群論方法證明了Kneser圖J(n，k)的自同構(gòu)群與n次對稱群Sym(n)同構(gòu)。其次，我們進一步的證明了Kneser圖的半徑為2，由此，可以得到Kneser圖自中心的一個充分條件。最后，借助計算機程序，我們分