關(guān)于非完全覆蓋圖的重構(gòu).pdf

1、本文對(duì)非完全覆蓋圖的重構(gòu)進(jìn)行了研究。主要內(nèi)容如下：
　　 ⑴令Γ=(V(Γ)，E(Γ))表示一個(gè)以V(Γ)為點(diǎn)集，E(Γ)為邊集的有限非空無(wú)向圖。對(duì)于任意一個(gè)非負(fù)整數(shù)s及V(Γ)上的一個(gè)s+1-序列α=(α0，…，α8)，α稱為Γ上的一條s-弧，如果{αi，αi+1)∈E(Γ)，對(duì)于i=0，1，…，s-1，并且αi-1≠αi+1，對(duì)于i=1，2，…，s-1.記Arc8(Γ)為Γ上所有s-弧的集合。通常，我們將1-arc和Arc1

2、(Γ)簡(jiǎn)記為arc和Arc(Γ)。令X表示作用在V(Γ)上的一個(gè)有限群，使得對(duì)于任意的x∈X，E(Γ)x=E(Γ)(即X保持Γ的鄰接關(guān)系).Γ稱為X-點(diǎn)傳遞的，如果X在V(Γ)上的作用是傳遞的(即對(duì)于任意的αi，αj，∈V(Γ)，存在x∈X滿足αix=αj)。一個(gè)點(diǎn)傳遞圖Γ稱為是(X，s)-弧-傳遞的，如果X在Arcs(Γ)上誘導(dǎo)的作用是傳遞的.(X，1)-弧-傳遞圖又稱為X-對(duì)稱圖.
　　 ⑵稱Γ是X-非本原圖，如果V(Γ)允

3、許一個(gè)非平凡的X-不變的劃分召，也就是一個(gè)劃分B，使得對(duì)于任意的B∈B及x∈X，有1<｜B｜<｜V(Γ)｜且Bx∈B.此時(shí)我們可以定義Γ關(guān)于劃分B的商圖ΓB為以B為點(diǎn)集的一個(gè)圖，其鄰接關(guān)系為：對(duì)于任意的B，C∈B，{B，C)∈E(ΓB)當(dāng)且僅當(dāng)存Γ中的兩個(gè)點(diǎn)σ∈B和τ∈C使得{σ，τ}∈E(Γ).我們考慮ΓB不是空?qǐng)D的情形，此時(shí)由[1]我們有對(duì)于任意的B∈B，B是Γ的一個(gè)獨(dú)立集。稱Γ是ΓB的多重覆蓋圖，如果對(duì)于任意的{B，C}∈E(ΓB

4、)和σ∈B，存在τ∈C使得{σ，τ]∈E(Γ)，否則稱Γ不是ΓB的多重覆蓋圖.特別地，如果上述τ是唯一存在的，就稱Γ是ΓB的覆蓋。當(dāng)Γ是一個(gè)有限非空的(X，2)-弧-傳遞圖，B為其上一個(gè)非平凡的X-不變的劃分，使得ΓB非空且Γ不是ΓB的多重覆蓋圖時(shí)，文獻(xiàn)[2]給出了(Γ，X，B)當(dāng)｜Γ(C)∩B｜=2時(shí)的一個(gè)刻畫，這里B∈B且C∈ΓB(B).這個(gè)結(jié)果促使我們研究當(dāng)｜Γ(C)∩B｜=3的情形.完成這個(gè)工作需要研究度數(shù)為4或7的(X，2)-

5、弧-傳遞圖.基于[3]中的結(jié)果，我們將在第一章給出4度(X，2)-弧-傳遞圖的一個(gè)劃分；同時(shí)我們將證明任何一個(gè)4度的(X，2)－?。瓊鬟f的非完全圖都是準(zhǔn)n邊形，這里n≥4是一個(gè)整數(shù).對(duì)于7度的(X，2)-弧-傳遞圖∑，我們將證明∑可以作為一個(gè)滿足條件的Γ的商圖，當(dāng)且僅當(dāng)Xr∑(τ)≌PSL(3，2)，這里τ∈V(∑)。
　　 ⑶對(duì)于任意一個(gè)X-對(duì)稱圖∑，我們將給出存在一個(gè)(X，s)-弧-傳遞圖Γ以∑為商圖，且Γ不是∑的完全覆蓋圖