【摘要】：在信息化時代,圖論也被廣泛的應用在人們的日常生活、生產(chǎn)中,尤其是計算機技術(shù)、大規(guī)模網(wǎng)絡技術(shù),圖論與其更是有著密切的聯(lián)系.圖論中圖的邊連通度的問題就是來源于網(wǎng)絡設計的穩(wěn)定性與可靠性的分析.對于多處理機網(wǎng)絡的分析,經(jīng)常會涉及到某些圖類模型,即用圖中的點和邊分別表示網(wǎng)絡中的節(jié)點和連線,從而構(gòu)成連通的網(wǎng)絡的拓撲結(jié)構(gòu).一個重要的模型就是人們將網(wǎng)絡模型化為一個連通有向(無向)圖,圖中的點集和弧集分別表示所有的處理機和系統(tǒng)中各處理機之間的通信聯(lián)系.從而網(wǎng)絡的可靠性,可通過有向圖或無向圖中的一些概念,比如連通度、邊連通度、弧連通度等來刻畫.因此,連通度成為反映網(wǎng)絡穩(wěn)定的重要參數(shù),這也就促成了圖的連通性成為圖論研究中的熱點.利用簡單圖的點連通度或邊連通度來精確分析網(wǎng)絡的穩(wěn)定性還存在一些不足.經(jīng)過研究,人們發(fā)現(xiàn)某些圖類,比如說,線圖、笛卡爾積、字典積、強積等變換圖都是由已知圖經(jīng)過特殊構(gòu)造而得到的更大的圖的重要結(jié)果,而通過這些變換圖可以得到各種各樣的網(wǎng)絡結(jié)構(gòu),從而,對各種變換圖或有向圖的連通性、邊連通性、弧連通性的研究,可以從理論上為可靠性網(wǎng)絡的設計提供科學的解決方法和手段.人們從對圖的連通度的研究發(fā)展到對各種變換圖的高階連通性的研究.本文主要研究某些特殊變換圖的連通性問題.論文的正文部分分為三章:第一章,主要介紹了圖的連通性理論的研究背景和一些基本概念,給出了全變換有向圖Dxyz、笛卡爾積和字典積等的定義.最后介紹了本文的研究內(nèi)容以及羅列出本文的主要研究成果.第二章,根據(jù)全變換有向圖的定義,可以得到27種全變換有向圖,但在這篇文章中我們主要研究與符號′0′有關(guān)的10種全變換有向圖的基本性質(zhì),例如:正則性、強連通性、λ-最優(yōu)以及超弧連通性.證明了這些全變換有向圖是強連通、λ-最優(yōu)以及超弧連通的充要條件.第三章,首先介紹了兩個有向圖的線圖、笛卡爾積和字典積有向圖的研究歷史及現(xiàn)狀.其次,定義了有向圖的bi-super性,并證明了線圖是bi-super的充要條件.最后,在已有的笛卡爾積和字典積有向圖的連通性研究的基礎上,繼續(xù)研究它們的bi-super性.
[Abstract]:In the information age, graph theory is also widely used in people's daily life, production, especially computer technology, large-scale network technology, graph theory is closely related to it. The problem of edge connectivity of graphs in graph theory comes from the analysis of stability and reliability of network design. For the analysis of multiprocessor networks, some graph models are often involved, that is, the points and edges in the graph are used to represent the nodes and connections in the network respectively, thus forming the topological structure of the connected network. An important model is that people model the network into a connected directed (undirected) graph, in which the point set and arc set represent the communication relationship between all processors and each processor in the system, respectively. Thus, the reliability of the network can be characterized by some concepts in directed graph or undirected graph, such as connectivity, edge connectivity, arc connectivity and so on. Therefore, connectivity has become an important parameter to reflect the stability of the network, which makes the connectivity of graphs become a hot spot in graph theory. There are still some shortcomings in the accurate analysis of the stability of the network by using the point connectivity or edge connectivity of a simple graph. After research, it is found that some graph classes, such as graph, Cartesian product, dictionary product, strong product and so on, are the important results of larger graphs obtained by special construction of known graphs. Through these transformation graphs, a variety of network structures can be obtained, thus, the connectivity, edge connectivity and arc connectivity of various transformation graphs or directed graphs can be studied. It can provide scientific solutions and means for the design of reliability network in theory. People have developed from the study of the connectivity of graphs to the study of higher-order connectivity of various transformation graphs. In this paper, we mainly study the connectivity of some special transformation graphs. The main body of the paper is divided into three chapters: in the first chapter, the research background and some basic concepts of the connectivity theory of graphs are introduced, and the definitions of Dxyz, Cartesian product and dictionary product of fully transformed directed graphs are given. Finally, it introduces the research content of this paper and lists the main research results of this paper. In chapter 2, according to the definition of total transformation directed graph, 27 kinds of total transformation directed graph can be obtained, but in this paper, we mainly study the basic properties of 10 kinds of total transformation directed graph related to symbol'0', such as regularity, strong connectivity, 位-optimal and super-arc connectivity. The necessary and sufficient conditions for these fully transformed directed graphs to be strongly connected, 位-optimal and super-arc connected are proved. In the third chapter, the research history and present situation of two directed graphs, Cartesian product and dictionary product directed graph, are introduced at first. Secondly, the bi- superability of directed graphs is defined, and the necessary and sufficient conditions for graphs to be bi-super are proved. Finally, on the basis of the existing studies on the connectivity of Cartesian products and dictionary product directed graphs, we continue to study their bi- superproperties.
【學位授予單位】：新疆師范大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5

【相似文獻】

相關(guān)期刊論文 前10條

1 李煒,施永兵;有向圖的有向圈長分布(英文)[J];上海師范大學學報(自然科學版);2003年02期

2 劉愛霞;楊愛民;;局部內(nèi)(外)半完全有向圖的可跡性[J];中北大學學報(自然科學版);2006年02期

3 白竹香;邵燕靈;;一類雙色有向圖的指數(shù)(英文)[J];山西大學學報(自然科學版);2007年01期

4 張彬;;局部半完全有向圖中的王[J];太原師范學院學報(自然科學版);2007年02期

5 吳靜;王鵬濤;魏國利;;帶周期的強連通有向圖的研究與應用[J];天津工業(yè)大學學報;2007年05期

6 劉愛霞;楊愛民;;擴張的局部內(nèi)(外)半完全有向圖的可跡性[J];中北大學學報(自然科學版);2008年05期

7 師海忠;;有向圖語言[J];計算機工程與應用;2011年22期

8 周鎮(zhèn)海;極小和極大線有向圖[J];數(shù)學雜志;1984年03期

9 宋增民;有向圖中的弧數(shù)和回路[J];自然雜志;1986年10期

10 陳仕洲;;半距離度正則有向圖[J];韓山師范學院學報;1987年03期

相關(guān)會議論文 前4條

1 李剛;童，

本文編號：2476335