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

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

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

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

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

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