亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        關于冠圖與queens-圖的若干結(jié)果

        2011-07-05 11:21:14鄧毅雄
        華東交通大學學報 2011年5期
        關鍵詞:縱坐標橫坐標子圖

        鄧毅雄

        (華東交通大學軟件學院,江西南昌330013)

        Deng Yixiong

        (School of Software,East China Jiaotong University,Nanchang 330013,China)

        本文討論的圖都是簡單無向圖,文中未加說明的術語和符號參閱文獻[1][2]。

        L.W.Beineke等[3]引入了queens-圖的概念,并且證明了在一定條件下的完全塊圖、樹、Kn×Pm、Pn×Pm,C2n×Pm等是queens-圖,并解決了二部及多部圖的問題。到目前,這方面的研究成果比較少,另外的結(jié)果有:證明了θ-圖是queens-圖,并給出了B(m,n,r)圖是queens-圖的充分必要條件[4];討論了queens-圖的構(gòu)造問題,也得到了一些queens-圖[5]。

        1 定義及引理

        設A是(0,1)-矩陣。一個圖稱為A的queens-圖,記為Q(A),如果這個圖的點與A中的1相對應,圖的兩個點鄰接當且僅當A中對應的1同在某線或?qū)蔷€上。(這里的“線”是指矩陣的行或列。)

        我們稱一個圖G是queens-圖,如果存在某(0,1)-矩陣A,使得G是A的queens-圖。注意到,給出一個(0,1)-矩陣,很容易獲得其對應的queens-圖,但是,給出一個圖G,判斷它是否為queens-圖,卻常常不是一件容易的事情。所以,這方面研究的一個主要問題是:哪些圖是queens-圖?

        文獻[3]給出了下面兩個引理:

        引理1[3]圖G是queens-圖當且僅當它的點可以對應坐標(i,j),并且兩個不同的點(i,j)和(k,l)鄰接當且僅當1i=k,或 2j=l,或 3i+j=k+l,或4i-j=k-l。

        引理2[3]如果圖G是queens-圖,那么G不包含導出子圖K1,5。

        引理1給出的4個條件,依次分別指的是兩個點在同一行、列、主對角線和斜對角線上,用于queens-圖的驗證和判斷。引理2給出的queens-圖的必要條件是基于矩陣只有4條“線”,它在判斷一個圖不是queens-圖時,非常有用。

        確定一個圖G是否為queens-圖,就是構(gòu)造對應的(0,1)-矩陣A,也就是確定1的位置,或者說是1的坐標(i,j),而1的位置就是圖G的點的位置,所以,圖G是否為queens-圖,就是看能否構(gòu)造滿足定義或者說滿足引理1要求的點的坐標(i,j)。

        另外,如果queens-圖G對應的(0,1)-矩陣為A,那么A的轉(zhuǎn)置矩陣AT對應的queens-圖仍然是G。

        懸掛邊是度為1的點所關聯(lián)的邊。我們注意到,去掉一個queens-圖的懸掛點,就相當于在其對應的(0,1)-矩陣中把該懸掛點所對應的元素“1”改為元素“0”,而這不會影響其它的元素。特別由于它是懸掛點,這個元素的改變,不會影響其它點的結(jié)構(gòu)關系,所以我們有:

        引理3 如果G是queens-圖,那么去掉G的若干懸掛點所得之子圖仍然是queens-圖。易知:

        引理4 完全圖Kn、圈Cn是queens-圖。

        定義 圖G的r-正則冠圖Ir(G)是指在G的每個點上都粘接r條懸掛邊所得之圖,而圖G的r-弱冠圖Ir(G)是指在G的每個點上至多粘接r條懸掛邊所得之圖。圖G的1-正則冠圖稱為王冠圖,記為I(G)。

        當G=Kn時,稱Ir(Kn)為完全r-冠圖;而當G=Cn時,稱Ir(Cn)為r-皇冠圖,記為Cn⊙rK1。

        2 主要結(jié)論

        根據(jù)引理3,易于得到:

        定理1 如果冠圖Ir(G)是queens-圖,那么圖G也是queens-圖。

        由定理1引出問題:如果圖G也是queens-圖,那么冠圖Ir(G)是queens-圖嗎?顯然,一般情況下并不是這樣的,這個命題一般是不成立的。下面的定理2給出了一個必要條件,定理3和定理4給出了兩類滿足這個問題的圖。

        所謂零圖是沒有邊的圖。注意到,當r≥4時,如果G不是零圖,冠圖Ir(G)含有導出子圖K1,5,結(jié)合引理2,有

        定理2 當G不是零圖時,如果冠圖Ir(G)是queens-圖,那么r≤3。

        定理3完全r-冠圖I(rKn)是queens-圖當且僅當r=1,2,3。

        首先,r≤3是Ir(G)是queens-圖的必要性由定理1獲知。其次,我們證明當r=3時,完全r-冠圖Ir(Kn)是queens-圖。事實上?

        ,令各點的坐標分別為

        首先,ui(i=0,1,…,n-1)的橫坐標均為0,他們相互鄰接構(gòu)成Kn。

        注意到,對ui與wi0,它們的橫坐標與縱坐標之和為0+(3i+1)=(4i+1)+(-i-1),則ui與wi0鄰接;對ui與wi1,它們的縱坐標均為 3i,則ui與wi1鄰接;對ui與wi2,它們的橫坐標減縱坐標為0-3i=(9n+2i-5)-(9n+5i-5),則ui與wi2鄰接。

        另外,注意到0≤i≤n-1,wi0、wi1、wi2之間橫坐標、縱坐標,以及橫坐標與縱坐標之和分別均不相同,并且wi0、wi1、wi2的橫坐標減縱坐標分別為5i+2、5n+i-2、-3i(i=0,1,…,n-1),這3組數(shù)據(jù)之間相互不可能存在相等的情況,根據(jù)引理1,wi0、wi1、wi2互不鄰接;很容易驗證,當j≠i時,wi0、wi1、wi2與uj也均不鄰接。

        綜上,完全 3-冠圖I3(Kn)是如上坐標對應的queens-圖。

        最后,由引理3,我們從完全3-冠圖I3(Kn)是queens-圖,立即得到完全2-冠圖I2(Kn)和完全1-冠圖I1(Kn)都是queens-圖。

        由引理3和定理3,得

        推論1 當r≤3時,完全r-弱冠圖是queens-圖。

        定理4 皇冠圖Cn⊙rK1是queens-圖當且僅當r=1或r=2。

        證明 首先我們注意到,當r>2時,Cn⊙rK1含有導出子圖K1,5,根據(jù)引理2,Cn⊙rK1不是queens-圖。類似于定理3的證明,我們只要證明Cn⊙rK1是queens-圖即可。

        設V(Cn)={u0,u1,…,un-1},與ui(i=0,1,…,n-1)鄰接的2個懸掛點為wij(j=0,1),而Cn⊙2K1的各點的坐標定義如下:

        下面驗證情形1給出的坐標按照定義得到的queens-圖恰好就是圖Cn⊙2K1。

        首先,對于u2i與u2i+1(i=0,1,...,k-2),由于i-3i=(i+1)-(3i+1),所以點u2i與u2i+1(i=0,1,...,k-2)鄰接;由于(k-1)+(3k-3)=0+(4k-4),所以u2k-2與u2k-1鄰接;而u0與u2n-1的橫坐標均為0,所以u0與u2n-1鄰接,故ui(i=0,1,…,2k-1)恰構(gòu)成圈Cn。

        由于ui和wi0(i=0,1,…,2k-1)的縱坐標對應分別相同,所以ui與wi0鄰接;且容易驗證,當i≠j(i、j=0,1,…,2k-1)時,ui與wj0不鄰接。

        注意到,由wi1,ui(i=0,1,...,2k-3)的橫坐標與縱坐標之和相同,即 (-4k-i+3)+(4k+3i-3)=2i,所以wi1與ui鄰接;而u2k-2與w2k-2,1各自的橫坐標與縱坐標之差均為 -2k+2,u2k-1與w2k-1,1各自的橫坐標與縱坐標之差均為 -4k-4,所以u2k-2與w2k-2,1,u2k-1與w2k-1,1分別鄰接;且容易驗證,當i≠j(i、j=0,1,…,2k-1)時,ui與wj1不鄰接。

        同樣根據(jù)引理1,可以證明wi0、wi1(i=0,1,...,2k-1)均不相互鄰接。

        類似可以驗證情形2。

        綜上,Cn⊙2K1是queens-圖。

        由引理3和定理4,得:

        推論2 當r=1或r=2,皇冠圖Cn⊙rK1的弱冠圖是queens-圖。

        [1]HARARY F.Graph theory[M].NewYork:Addison Wesley,Publishing Company,1969:1-274.

        [2]BONDY J A,MURTY U S R.Graph theory with application[M].NewYork:Elsevier Science Publishing Company,1976:1-65.

        [3]BEINEKE LW,BROERE I,HENNING MA.Queens graphs[J].Discrete Mathematics,1999,206(1-3):63-75.

        [4]鄧毅雄,熊金泉,等.關于Queens-圖的若干結(jié)果[J].華東交通大學學報,2003,20(1):82-85.

        [5]鄧毅雄,周尚超,等.Queens-圖的構(gòu)造[J].華東交通大學學報,2004,21(4):119-121.

        [6] GALLIAN J A.A survey:recent results,conjectures,and open problems in labeling graphs[J].Graph Theory,1989,13(4):491-504.

        [7]胡紅亮.圖Cn及其r-冠的新的優(yōu)美標號[J].純粹數(shù)學與應用數(shù)學,2010,26(6):454-457.

        [8]斯琴巴特爾,等.關于皇冠Qn調(diào)和的相關性質(zhì)[J].大學數(shù)學,2010,26(12):71-75.

        猜你喜歡
        縱坐標橫坐標子圖
        變化的“魚”
        更正
        勘 誤
        不可輕用的位似形坐標規(guī)律
        例談二次函數(shù)的頂點橫坐標x=-b/2a的簡單應用
        “平面直角坐標系”解題秘籍
        臨界完全圖Ramsey數(shù)
        基于頻繁子圖挖掘的數(shù)據(jù)服務Mashup推薦
        第五屆播睿智杯“奇思妙想”有獎數(shù)學知識競賽
        不含2K1+K2和C4作為導出子圖的圖的色數(shù)
        国产乱人伦av在线麻豆a| 完整在线视频免费黄片| 日本一区二区高清视频在线| 99久久99久久久精品蜜桃| 啦啦啦中文在线观看日本| 亚洲a∨无码一区二区| 久久99精品波多结衣一区| 国产一区二区熟女精品免费| 亚洲 日本 欧美 中文幕| 久久黄色国产精品一区视频| 免费无码av一区二区三区| 国农村精品国产自线拍| 精品亚洲一区二区99| 精品极品视频在线观看| 亚洲国产精彩中文乱码av| 少妇内射高潮福利炮| 天堂AV无码AV毛片毛| 亚洲精品一区二区三区在线观| 亚洲精品一区二区国产精华液| 国产精品麻豆欧美日韩ww| 国产三级精品美女三级| 日韩极品在线观看视频| 婷婷色香五月综合缴缴情| 国产午夜福利短视频| 国产欧美日本亚洲精品一5区| 中国男女黄色完整视频| 久久久久久九九99精品| 欧美自拍视频在线| 肉丝高跟国产精品啪啪| 精品国产一区二区三区三级| 精品久久欧美熟妇www| 欧美人与禽交zozo| 一区二区亚洲熟女偷拍| 在线中文字幕乱码英文字幕正常 | 911香蕉视频| 国产一区二区三区在线观看蜜桃| 狠狠色欧美亚洲狠狠色www| 国产无遮挡又黄又爽在线视频| 欧美在线成人免费国产| 日本免费看片一区二区三区| 粗大猛烈进出白浆视频|