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

        ?

        圖的逆符號邊全控制的性質(zhì)

        2010-10-16 01:51:08黃中升
        關(guān)鍵詞:廊坊師范學(xué)院定理

        黃中升

        (廊坊師范學(xué)院 數(shù)信學(xué)院,河北 廊坊 065000)

        圖的逆符號邊全控制的性質(zhì)

        黃中升

        (廊坊師范學(xué)院 數(shù)信學(xué)院,河北 廊坊 065000)

        本文將圖的符號邊全控制引申為圖的逆符號邊全控制,并在此基礎(chǔ)上研究圖的逆符號邊全控制數(shù)的性質(zhì).

        圖;逆符號邊全控制函數(shù);逆符號邊全控制數(shù)

        1 引言

        本文所指的圖均為無向簡單圖,文中未說明的符號和術(shù)語同于文獻[1].

        近年來,圖的控制概念得到延伸和推廣[2-3],2006年徐寶根教授定義了符號邊全控制[4].本文將圖的符號邊全控制引申為圖的逆符號邊全控制,并在此基礎(chǔ)上研究圖的逆符號邊全控制數(shù)的性質(zhì).

        定義1[4]設(shè)G=(V,E)為一個非空圖,一個函數(shù)f:E→{-1,1},如果對每一條邊 e∈E,均有 f(N(e))≥1成立,則稱f為圖G的一個符號邊全控制函數(shù),圖G的符號邊全控制數(shù)γ'st(G)=min{f(E)|f為圖G的符號邊控制函數(shù)}.

        下面引入圖的逆符號邊全控制的概念.

        定義2 設(shè)G=(V,E)為一個非空圖,對于圖G的一個函數(shù)f:E→{-1,1},如果對任意e∈E(G),均有f(N(e))≤1成立,則稱f為圖G的一個逆符號邊全控制函數(shù),圖G的逆符號邊全控制數(shù)為γ'st(G)=max{f(E)|f為圖G的逆符號邊全控制函數(shù)}.對于圖G的一個逆符號邊全控制函數(shù)f,如果不存在圖G的逆符號邊全控制函數(shù)g(f≠g),使得對于任意的e∈E,均有g(shù)(e)≥f(e),則稱f是G的一個極大逆符號邊全控制函數(shù).如果圖G的一個逆符號邊全控制函數(shù)f的權(quán)重 f(E)=γ'st(G),則稱 f是圖 G 的一個 γ'st(G)函數(shù).特別地,補充定義 γ'st(K1)=γ'st(K2)=0.

        利用定義2能夠解決圖論中關(guān)于邊集的一個劃分問題:如果將一個給定圖G的邊集E劃分為E1和E2兩類,使得G的每條邊的邊鄰域中第一類邊至多比第二類邊多一條,那么兩類邊的數(shù)目之差|E1|-|E2|的最大值就是這個圖的逆符號邊全控制數(shù).

        2 主要結(jié)果

        定理1 對任意非空簡單圖G,均有γ'st(G)≡|E(G)|(mod2)

        證明 設(shè)f是圖G的一個γ'st函數(shù),令P={e∈E|f(e)=1},M={e∈E|f(e)=-1},則 |E(G)|=|P|+|M|.

        當(dāng)|E(G)|為奇數(shù)時,令|E(G)|=2k+1,則|P|+|M|=2k+1,γ'st(G)=|P|-|M|=|P|-(2k+1-|P|)=2|P|-2k-1為奇數(shù);當(dāng)|E(G)|為偶數(shù)時,令|E(G)|=2k,則|P|+|M|=2k,γ'st(G)+|P|-|M|=|P|-(2k-|P|)=2(|P|-k)為偶數(shù).從而有 γ'st(G)≡|E(G)|(mod2).

        定理2 對任意兩個不交的圖G1和G2,均有

        由定義顯然可得.

        定理3 設(shè)f為圖G的一個逆符號邊全控制函數(shù),則f為圖G的一個極大的逆符號邊全控制函數(shù)當(dāng)且僅當(dāng)對于滿足f(e)=-1的任意一條邊e∈E,都存在邊e0∈N(e),使得f(N(e0))∈{0,1}.

        充分性 若f不是極大的逆符號邊全控制函數(shù),則存在一個極大的逆符號邊全控制函數(shù)g,使得g>f,即對任意e∈E,有g(shù)(e)≥f(e),且至少存在一條邊 e'∈E,有 g(e')>f(e')成立.因而有 f(e')=-1,g(e')=1.由假設(shè)可知存在一條邊e0∈N(e'),使得f(N(e0))∈{0,1},但由于對任意 e∈N(e')),有 g(e)≥f(e),且 g(e')=f(e')+2,我們有 g(N(e0))=f(N(e0))+2≥2,與 g為逆符號邊全控制函數(shù)相矛盾.證畢.

        定理4 對于任意非空圖G,均有γ'st(G)+γ'st(G)≥2,并且此下界是最好可能的.

        證明 設(shè)f為G的一個權(quán)重最小的符號邊全控制函數(shù),則γ'st(G)=f(E).令g=-f,則對于任意e∈E,有g(shù)(N(e))=-f(N(e))≤-1,由定義2和定理3可知,g是G的一個逆符號邊全控制函數(shù),但不是G的一個極大逆符號.從而 γ'st(G)>g(E)=-f(E)=-γ'st(G),故 γ'st(G)+γ'st(G)>0.由于 γ'st(G)和 γ'st(G)具有相同的奇偶性,因此 γ'st(G)+γ'st(G)≥2.

        對于2n階星圖K1,2n-1,由定義1和定義2易知,γ'st(K1,2n-1)=-1,γ'st(K1,2n-1)=3,從而 γ'st(K1,2n-1)+γ'st(K1,2n-1)=2,因此定理給出的下界是最好可能的.證畢.

        這樣,定理4給出了圖G的逆符號邊全控制數(shù)和符號邊全控制數(shù)的關(guān)系.

        〔1〕Bondy J A,Murty V S R.Graph Theory with Applications[M],Elsevier,Amsterdam,1976.

        〔2〕Haynes T W,Hedetniemi S T,Slater P J,Fundamentals ofDominationinGraphs[M].New York,1998.

        〔3〕Haynes T W,Hedetniemi S T,Slater P J,Domination in Graphs[M].New York,1998.

        〔4〕徐寶根.關(guān)于圖的符號邊全控制[J].華東交通大學(xué)學(xué)報,2006,23(2):129-131.

        O157.5

        A

        1673-260X(2010)06-0010-02

        河北省教育廳2009年自然科學(xué)研究計劃(2009331);河北省自然科學(xué)基金(A2008000128);廊坊師范學(xué)院青年項目(LSZQ200225); 廊坊師范學(xué)院科學(xué)研究項目(LSZY200901)

        猜你喜歡
        廊坊師范學(xué)院定理
        遵義師范學(xué)院作品
        大眾文藝(2022年21期)2022-11-16 14:49:06
        J. Liouville定理
        《通化師范學(xué)院報》 征稿啟事
        廊坊專場(二)
        大眾文藝(2020年20期)2020-11-05 14:33:56
        A Study on English listening status of students in vocational school
        洛陽師范學(xué)院
        蒸蒸日上的廊坊百冠
        “三共定理”及其應(yīng)用(上)
        今夜我們與廊坊相愛
        大慶師范學(xué)院簡介
        国产成人国产三级国产精品 | 扒开腿狂躁女人爽出白浆| 先锋影音最新色资源站| 日本欧美在线播放| 青青草伊人视频在线观看| 亚洲精品一区二区三区52p| 高潮潮喷奶水飞溅视频无码| 亚洲最大中文字幕无码网站| 亚洲日日噜噜噜夜夜爽爽| 中文字日产幕码三区做法| 国模冰莲自慰肥美胞极品人体图| 亚洲中文字幕无码mv| 91福利国产在线观看网站| 国产夫妻自偷自拍第一页| 中文字幕无码中文字幕有码| 内射无码专区久久亚洲| 久久天堂av色综合| a级三级三级三级在线视频| 一边摸一边抽搐一进一出口述| 无码精品人妻一区二区三区人妻斩| 亚洲都市校园激情另类| 亚洲一区二区三区免费av| 国产精品美女一区二区视频| 欧美第一黄网免费网站| 欧美激情精品久久999| 亚洲一区二区三区重口另类 | 人妻少妇精品视中文字幕免费| 成人免费直播| 正在播放一区| 青青自拍视频成人免费观看| 精品人伦一区二区三区蜜桃91| 在线不卡av片免费观看| 亚洲最大无码AV网站观看| 婷婷久久亚洲中文字幕| 天堂中文а√在线| 国产精品后入内射日本在线观看 | 久久不见久久见中文字幕免费| 99热最新在线观看| 白白在线免费观看视频| 狠狠97人人婷婷五月| 一本一本久久a久久精品综合|