19467.幾類變換有向圖的連通性研究

1、分分分類類類號號號:密密密級級級:學(xué)學(xué)學(xué)號號號:107622012210440單單單位位位代代代碼碼碼:10762新新新疆疆疆師師師范范范大大大學(xué)學(xué)學(xué)2015屆碩士學(xué)位論文幾幾幾類類類變變變換換換有有有向向向圖圖圖的的的連連連通通通性性性研研研究究究Theresearchaboutconnectivityofseveralkindsoftransfmationdigraphs研研研究究究生生生姓姓姓名名名:李李李靜靜靜靜靜靜學(xué)學(xué)學(xué)科科科

2、、、、專專專業(yè)業(yè)業(yè):應(yīng)應(yīng)應(yīng)用用用數(shù)數(shù)數(shù)學(xué)學(xué)學(xué)研研研究究究方方方向向向:圖圖圖論論論與與與組組組合合合數(shù)數(shù)數(shù)學(xué)學(xué)學(xué)院院院系系系、、、年年年級級級:數(shù)數(shù)數(shù)學(xué)學(xué)學(xué)科科科學(xué)學(xué)學(xué)學(xué)學(xué)學(xué)院院院、、、2012級級級指指指導(dǎo)導(dǎo)導(dǎo)老老老師師師:劉劉劉娟娟娟（（（教教教授授授）））新疆師范大學(xué)2015年5月26日中文摘要在信息化時(shí)代圖論也被廣泛的應(yīng)用在人們的日常生活、生產(chǎn)中尤其是計(jì)算機(jī)技術(shù)、大規(guī)模網(wǎng)絡(luò)技術(shù)圖論與其更是有著密切的聯(lián)系.圖論中圖的邊連通度的問題

3、就是來源于網(wǎng)絡(luò)設(shè)計(jì)的穩(wěn)定性與可靠性的分析.對于多處理機(jī)網(wǎng)絡(luò)的分析經(jīng)常會涉及到某些圖類模型即用圖中的點(diǎn)和邊分別表示網(wǎng)絡(luò)中的節(jié)點(diǎn)和連線從而構(gòu)成連通的網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).一個(gè)重要的模型就是人們將網(wǎng)絡(luò)模型化為一個(gè)連通有向（無向）圖圖中的點(diǎn)集和弧集分別表示所有的處理機(jī)和系統(tǒng)中各處理機(jī)之間的通信聯(lián)系.從而網(wǎng)絡(luò)的可靠性可通過有向圖或無向圖中的一些概念比如連通度、邊連通度、弧連通度等來刻畫.因此連通度成為反映網(wǎng)絡(luò)穩(wěn)定的重要參數(shù)這也就促成了圖的連通性成為圖論

4、研究中的熱點(diǎn).利用簡單圖的點(diǎn)連通度或邊連通度來精確分析網(wǎng)絡(luò)的穩(wěn)定性還存在一些不足.經(jīng)過研究人們發(fā)現(xiàn)某些圖類比如說線圖、笛卡爾積、字典積、強(qiáng)積等變換圖都是由已知圖經(jīng)過特殊構(gòu)造而得到的更大的圖的重要結(jié)果而通過這些變換圖可以得到各種各樣的網(wǎng)絡(luò)結(jié)構(gòu)從而對各種變換圖或有向圖的連通性、邊連通性、弧連通性的研究可以從理論上為可靠性網(wǎng)絡(luò)的設(shè)計(jì)提供科學(xué)的解決方法和手段.人們從對圖的連通度的研究發(fā)展到對各種變換圖的高階連通性的研究.本文主要研究某些特殊變換

5、圖的連通性問題.論文的正文部分分為三章:第一章主要介紹了圖的連通性理論的研究背景和一些基本概念給出了全變換有向圖Dxyz、笛卡爾積和字典積等的定義.最后介紹了本文的研究內(nèi)容以及羅列出本文的主要研究成果.第二章根據(jù)全變換有向圖的定義可以得到27種全變換有向圖但在這篇文章中我們主要研究與符號′0′有關(guān)的10種全變換有向圖的基本性質(zhì)例如:正則性、強(qiáng)連通性、λ最優(yōu)以及超弧連通性.證明了這些全變換有向圖是強(qiáng)連通、λ最優(yōu)以及超弧連通的充要條件.第三