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

        ?

        四葉樹Hosoya指標(biāo)顯式公式及其序列

        2016-12-08 03:01:40民,燕,
        大連理工大學(xué)學(xué)報 2016年6期
        關(guān)鍵詞:大連理工大學(xué)利民初值

        楊 利 民, 段 麗 燕, 王 天 明

        ( 1.大理大學(xué) 數(shù)學(xué)與計算機學(xué)院, 云南 大理 671003;2.大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 遼寧 大連 116024 )

        ?

        四葉樹Hosoya指標(biāo)顯式公式及其序列

        楊 利 民*1, 段 麗 燕1, 王 天 明2

        ( 1.大理大學(xué) 數(shù)學(xué)與計算機學(xué)院, 云南 大理 671003;2.大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 遼寧 大連 116024 )

        為研究四葉樹Hosoya指標(biāo)的規(guī)律,利用圖論的分支分析法,解決了四葉樹Hosoya指標(biāo)的顯式公式和序列.對于一般的t葉樹,仍然用同樣分支分析法,得到相應(yīng)的t葉樹Hosoya指標(biāo)的顯式公式和序列.發(fā)現(xiàn)了一族初值不一樣的Fibonacci序列,在科學(xué)上對組合數(shù)學(xué)和圖論提供了一定參考.

        四葉樹;t葉樹;S(n)-因子;Fibonacci數(shù);Hosoya指標(biāo)

        0 引 言

        四葉草又名幸運草,是三葉草或苜蓿草的稀有變種.苜蓿草,是多年生草本植物,一般只有三片小葉子,葉形呈心形,葉心較深色的部分亦是心形.最為有趣也最特別的是,在十萬株苜蓿草中,可能只會發(fā)現(xiàn)一株是四葉草,因為概率是十萬分之一,四葉草成為國際公認(rèn)的幸運的象征.

        由四葉草引出四葉樹,四片葉子、頂點數(shù)為n的樹叫做四葉樹.

        Fibonacci數(shù)列,也稱為“兔子數(shù)列”,其數(shù)列為0,1,1,2,3,5,8,13,21,34,55,89,144,…,滿足遞歸關(guān)系式Fn=Fn-1+Fn-2,初值F0=0,F(xiàn)1=1[1-3].

        本文研究四葉樹Hosoya指標(biāo)的顯式公式和序列.

        1 定義和引理

        1.1 定 義

        定義1[4]設(shè)S(n)={Ki:1≤i≤n}(n≥1),Ki是i個頂點的完全圖.假設(shè)M是G的子圖并且M的每一個分支都同構(gòu)于S(n)={Ki:1≤i≤n}(n≥1)中的某一個元素,則稱M為圖G的一個S(n)={Ki:1≤i≤n}-子圖.假設(shè)M是圖G的生成子圖,則稱M為圖G的一個S(n)={Ki:1≤i≤n}-因子.

        令A(yù)(G)是圖G的所有S(n)={Ki:1≤i≤n}-因子個數(shù).圖G是簡單圖,不包括多重邊和環(huán).

        定義2 圖G的所有k-匹配個數(shù)稱作Hosoya指標(biāo).Hosoya指標(biāo)用Z(G)表示.

        1.2 基本引理

        引理2 如果G和H的交為空圖,即G∩H=?,則A(G∪H)=A(G)·A(H).

        引理3[5]假設(shè)Pn是長為n的路,且有n+1個頂點,則Pn的S(n)={Ki:1≤i≤n}-因子個數(shù)是A(Pn)=Fn+2(n≥1),其中Fn+2是第n+2個Fibonacci數(shù).

        引理4[6]假設(shè)圖G的頂點數(shù)為n并且無K3子圖,則Hosoya指標(biāo)Z(G)等于圖G的所有S(n)={Ki:1≤i≤n}-因子個數(shù):Z(G)=A(G).

        2 主要結(jié)果

        2.1 四葉樹Hosoya指標(biāo)的顯式公式

        下面給出四葉樹的Hosoya指標(biāo)的顯式公式并證明[7-8].

        定理1 如圖1所示n個頂點的四葉樹,它的Hosoya指標(biāo)為

        Z(G1)=5Fn-4+Fn-5;n≥5

        圖1 四葉樹圖G1

        證明 利用圖的分支分析法[9-10],對給定點Vn-4進行分析,過Vn-4頂點的一切完全圖只有K1和5個K2,無Ki(3≤i≤n),討論分3種情況:

        情況一 過Vn-4點完全圖為K1,即為點Vn-4,Vn-4作為一個完全分支,則S(n)-因子個數(shù)如下:

        A(G1-V(K1))=

        A(Vn-3∪Vn-2∪Vn-1∪Vn∪Pn-6)=

        A(Vn-3)A(Vn-2)A(Vn-1)A(Vn)A(Pn-6)=

        1×1×1×1×A(Pn-6)=A(Pn-6)

        根據(jù)引理3就有

        A(G1-V(K1))=Fn-4

        情況二 過Vn-4點完全圖為vn-4vn-3,vn-4vn-2,vn-4vn-1和vn-4vn,這4個完全圖K2是對稱的,K2作為兩個點的完全分支,則S(n)-因子個數(shù)如下:

        4A(G1-V(K2))=

        4A(Vn-2∪Vn-1∪Vn∪Pn-6)=

        4A(Vn-2)A(Vn-1)A(Vn)A(Pn-6)=

        4×1×1×1×A(Pn-6)=4Fn-4

        情況三 過Vn-4點完全圖為vn-5vn-4,K2作為兩個點的一個完全分支,則S(n)-因子個數(shù)如下:

        “我說我快要活不成了?!蔽沂チ伺c他斗嘴的樂趣和力氣,我的眼前一陣陣發(fā)黑,手腕處那種汩汩的聲音讓我覺得害怕。

        A(G1-V(K2))=

        A(Vn-3∪Vn-2∪Vn-1∪Vn∪Pn-7)=

        A(Vn-3)A(Vn-2)A(Vn-1)A(Vn)A(Pn-7)=

        1×1×1×1×A(Pn-7)=A(Pn-7)=Fn-5

        據(jù)引理1得到

        A(G1-V(K1))+4A(G1-V(K2))+

        A(G1-V(K2))=

        Fn-4+4Fn-4+Fn-5=5Fn-4+Fn-5

        Z(G1)=A(G1)=5Fn-4+Fn-5;n≥5

        有趣的是,四葉樹序列的初值f0=5,f1=6,通項fn=fn-1+fn-2,這好像是Fibonacci序列,只是初值不一樣.下面將證明這個規(guī)律是對的.

        證明 因為fn=5Fn-4+Fn-5,所以fn-1=5Fn-5+Fn-6,fn-2=5Fn-6+Fn-7,又因為fn-1+fn-2=5(Fn-5+Fn-6)+(Fn-6+Fn-7)=5Fn-4+Fn-5,則fn=fn-1+fn-2.

        Tab.1 Some initial values of Hosoya index of four

        nZ(T4n)nZ(T4n)55928661045711117381712118

        5,6,11,17,28,45,73,118,191,309,500,809,1 309,2 118,3 427,5 545,8 972,14 517,23 489,38 006,61 495,99 501,160 996,260 497,421 493,681 990,1 103 483,…

        2.2 t葉樹Hosoya指標(biāo)的顯式公式

        定理2 如圖2所示n個頂點、t片樹葉的t葉樹,它的Hosoya指標(biāo)為

        圖2 t葉樹

        證明 利用圖的分支分析法,對給定點Vn-t進行分析,過Vn-t頂點的一切完全圖只有K1和(t+1)個K2,無Ki(3≤i≤n),討論分3種情況:

        情況一 過Vn-t點完全圖為K1,即為點Vn-t,Vn-t作為一個完全分支,則S(n)-因子個數(shù)如下:

        A(Vn-t+1∪Vn-t+2∪…∪Vn∪Pn-t-2)=

        A(Vn-t+1)A(Vn-t+2)…A(Vn)A(Pn-t-2)=

        1×1×…×1×A(Pn-t-2)=A(Pn-t-2)

        根據(jù)引理3有

        情況二 過Vn-t點完全圖為vn-tvn-t+1,vn-tvn-t+2,…,vn-tvn,這t個完全圖K2是對稱的,K2作為兩個點的完全分支,則S(n)-因子個數(shù)如下:

        tA(Vn-t+2∪…∪Vn∪Pn-t-2)=

        tA(Vn-t+2)…A(Vn)A(Pn-t-2)=

        t×1×…×1×A(Pn-t-2)=tA(Pn-t-2)=tFn-t

        情況三 過Vn-t點完全圖為vn-tvn-t-1,K2作為兩個點的一個完全分支,則S(n)-因子個數(shù)如下:

        A(Vn-t+1∪Vn-t+2∪…∪Vn∪Pn-t-3)=

        A(Vn-t+1)A(Vn-t+2)…A(Vn)A(Pn-t-3)=

        1×1×…×1×A(Pn-t-3)=

        A(Pn-t-3)=Fn-t-1

        據(jù)引理1得到

        Fn-t+tFn-t+Fn-t-1=

        (t+1)Fn-t+Fn-t-1

        據(jù)引理4得到

        n≥t+1,t≥2

        圖3 二葉樹

        同樣有趣的是,二葉樹序列的初值f0=3,f1=4,通項fn=fn-1+fn-2,這好像是Fibonacci序列,只是初值不一樣.下面將證明這個規(guī)律是對的.

        因為fn=3Fn-2+Fn-3,所以fn-1=3Fn-3+Fn-4,fn-2=3Fn-4+Fn-5,又因為fn-1+fn-2=3(Fn-3+Fn-4)+(Fn-4+Fn-5)=3Fn-2+Fn-3,則fn=fn-1+fn-2.

        3,4,7,11,18,29,47,76,123,199,322,521,843,1 364,2 207,3 571,5 778,9 349,…

        圖4 三葉樹

        三葉樹序列的初值f0=4,f1=5,通項fn=fn-1+fn-2,這好像是Fibonacci序列,只是初值不一樣.下面將證明這個規(guī)律是對的.

        因為fn=4Fn-3+Fn-4,所以fn-1=4Fn-4+Fn-5,fn-2=4Fn-5+Fn-6,又因為fn-1+fn-2=4(Fn-4+Fn-5)+(Fn-5+Fn-6)=4Fn-3+Fn-4,則fn=fn-1+fn-2.

        4,5,9,14,23,37,60,97,157,254,411,665,1 076,1 741,2 817,4 558,7 375,11 933,…

        對于一般的t葉樹,發(fā)現(xiàn)它的Hosoya指標(biāo)序列呈現(xiàn)同樣規(guī)律.初值f0=t+1,f1=t+2,通項fn=fn-1+fn-2.

        證明 因為fn=(t+1)Fn-t+Fn-t-1,所以fn-1=(t+1)Fn-t-1+Fn-t-2,fn-2=(t+1)Fn-t-2+Fn-t-3,又因為fn-1+fn-2=(t+1)(Fn-t-1+Fn-t-2)+(Fn-t-2+Fn-t-3)=(t+1)Fn-t+Fn-t-1,則fn=fn-1+fn-2.

        t+1,t+2,2t+3,3t+5,5t+8,8t+13,13t+21,21t+34,34t+55,…

        推論3 如圖5所示的五葉樹的Hosoya指標(biāo)為

        令t=5,五葉樹的Hosoya指標(biāo)與t葉樹的呈同樣規(guī)律,初值f0=6,f1=7,通項fn=fn-1+fn-2.

        6,7,13,20,33,53,86,139,225,364,589,953,1 542,2 495,…

        圖5 五葉樹

        3 結(jié) 語

        本文解決了四葉樹Hosoya指標(biāo)的顯式公式和序列,并將它推廣到一般的t葉樹上,有趣的是,發(fā)現(xiàn)了一族初值不一樣的Fibonacci序列,在科學(xué)上對組合數(shù)學(xué)和圖論提供了一定參考價值.

        [1] 王天明. 近代組合學(xué)[M]. 大連:大連理工大學(xué)出版社, 2008.

        WANG Tian-ming. Modern Combinatorics [M]. Dalian:Dalian University of Technology Press, 2008. (in Chinese)

        [2] Comtet L. 高等組合學(xué):有限和無限展開的藝術(shù)[M]. 譚明術(shù),楊利民,等譯. 大連:大連理工大學(xué)出版社, 1991.

        Comtet L. Advanced Combinatorics: The Art of Finite and Infinite Unfolding [M]. TAN Ming-shu, YANG Li-min,etal., trans. Dalian: Dalian University of Technology Press, 1991. (in Chinese)

        [3] Harary F, Palmer E M. Graphical Enumeration [M]. New York: Academic Press Inc., 1973.

        [4] 楊利民,王天明. 色多項式的顯示公式[J]. 數(shù)學(xué)進展, 2006, 35(1):55-66.

        YANG Li-min, WANG Tian-ming. The explicit formula of the chromatic polynomial [J]. Advances in Mathematics, 2006, 35(1):55-66. (in Chinese)

        [5] 楊利民.S(n)={Ki:1≤i≤n}-因子數(shù)的遞歸關(guān)系式[J]. 數(shù)學(xué)研究與評論, 1991, 11(1):78.

        YANG Li-min. A recurrence relation for the number of factors ofS(n)={Ki:1≤i≤n} [J]. Journal of Mathematical Research and Exposition, 1991, 11(1):78. (in Chinese)

        [6] 楊利民,楊正亮. Fibonacci數(shù)的圖論應(yīng)用[J]. 大理學(xué)院學(xué)報, 2011, 10(4):12-16.

        YANG Li-min, YANG Zheng-liang. Graphic applications on Fibonacci numbers [J]. Journal of Dali University, 2011, 10(4):12-16. (in Chinese)

        [7] 楊利民,王天明,年四洪. 完全i部圖N[(X1,X2,…,Xi),k]計數(shù)公式[J]. 大連理工大學(xué)學(xué)報, 2007, 47(6):925-930.

        YANG Li-min, WANG Tian-ming, NIAN Si-hong. Counting formulas ofN[(X1,X2,…,Xi),k] of completei-partite graphs [J]. Journal of Dalian University of Technology, 2007, 47(6):925-930. (in Chinese)

        [8] 楊利民. 理想子圖計數(shù)及其應(yīng)用[J]. 大連理工大學(xué)學(xué)報, 1989, 29(5):605-609.

        YANG Li-min. Enumeration of ideal subgraphs and its applications [J]. Journal of Dalian University of Technology, 1989, 29(5):605-609. (in Chinese)

        [9] YANG Li-min, WANG Tian-ming. The representing formula ofN(G,k) [J]. International Journal of Analyzing Methods of Combinatorial Biology in Mathematics, 2008, 1(1):1-26.

        [10] 楊利民.S(n)-因子計數(shù)理論及其應(yīng)用[D]. 大連:大連理工大學(xué), 2006.

        YANG Li-min. Counting theory ofS(n)-factors and applications [D]. Dalian: Dalian University of Technology, 2006. (in Chinese)

        Explicit formula of Hosoya index of four leaf tree with its sequence

        YANG Li-min*1, DUAN Li-yan1, WANG Tian-ming2

        ( 1.School of Mathematics and Computer, Dali University, Dali 671003, China;2.School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China )

        To research into the laws of Hosoya index for four leaf tree, by means of analyzing method of components in graph theory, the explicit formula of Hosoya index of four leaf tree and its sequence are solved. For generaltleaf tree, by adopting the same method, the explicit formula of Hosoya index of correspondingtleaf tree and its sequence are obtained. A family of Fibonacci sequences whose initial values are not the same are discovered, which provides some scientific

        for combinatorics and graph theory.

        four leaf tree;tleaf tree;S(n)-factor; Fibonacci number; Hosoya index

        2016-04-10;

        2016-09-25.

        大理大學(xué)高層次人才科研啟動基金資助項目(KY0719203410).

        楊利民*(1965-),男,博士,教授,E-mail:yanglm65@aliyun.com.

        1000-8608(2016)06-0657-05

        O157.5

        A

        10.7511/dllgxb201606015

        猜你喜歡
        大連理工大學(xué)利民初值
        新型捕收劑BK610和BK612在利民選煤廠的應(yīng)用
        具非定常數(shù)初值的全變差方程解的漸近性
        一種適用于平動點周期軌道初值計算的簡化路徑搜索修正法
        果樹大容器育苗技術(shù)的研究
        傅利民
        心聲歌刊(2019年1期)2019-12-07 09:19:38
        垃圾分類:雖然“繁瑣”但利已利民
        華人時刊(2019年13期)2019-11-26 00:54:38
        Research on the Globalization of English in the Internet era
        大東方(2019年1期)2019-09-10 20:30:40
        三維擬線性波方程的小初值光滑解
        偽隨機碼掩蔽的擴頻信息隱藏
        中泰化學(xué)與大連理工大學(xué)簽署戰(zhàn)略合作框架協(xié)議
        中國氯堿(2014年11期)2014-02-28 01:05:06
        亚洲AV无码一区二区水蜜桃| 风韵多水的老熟妇| 国产999精品久久久久久| 国产女奸网站在线观看| 美女射精视频在线观看| 少妇性l交大片7724com| 国产日产亚洲系列最新| 国产午夜亚洲精品午夜鲁丝片| 久久亚洲欧洲无码中文| 日韩久久久黄色一级av| 92自拍视频爽啪在线观看| 丝袜美腿福利视频在线| 免费观看国产短视频的方法| 国产精品vⅰdeoxxxx国产| 人妻少妇精品专区性色av| 日韩www视频| 精品不卡久久久久久无码人妻| 亚洲视频在线播放免费视频| 蜜臀人妻精品一区二区免费| 日韩a级精品一区二区| 性色av免费网站| 精品国产亚洲AⅤ麻豆| 丰满熟妇人妻av无码区 | 国产91色综合久久免费| 久久精品国产成人| 久久久久亚洲精品无码网址| 中文字幕人妻丝袜成熟乱| 亚洲激情一区二区三区不卡| 久久人人爽av亚洲精品| 亚洲国产综合精品 在线 一区 | 两个人看的www中文在线观看| 国产熟女精品一区二区三区| 老岳肥屁熟女四五十路| 日本妇人成熟免费2020| 日本公妇在线观看中文版| 精品国产性色av网站| 人妻少妇中文字幕av| 亚洲av色香蕉一区二区三区| 一个人看的视频www免费| 可以免费在线看黄的网站| 亚洲熟妇夜夜一区二区三区 |