【摘要】：在信息化時(shí)代,圖論也被廣泛的應(yīng)用在人們的日常生活、生產(chǎn)中,尤其是計(jì)算機(jī)技術(shù)、大規(guī)模網(wǎng)絡(luò)技術(shù),圖論與其更是有著密切的聯(lián)系.圖論中圖的邊連通度的問(wèn)題就是來(lái)源于網(wǎng)絡(luò)設(shè)計(jì)的穩(wěn)定性與可靠性的分析.對(duì)于多處理機(jī)網(wǎng)絡(luò)的分析,經(jīng)常會(huì)涉及到某些圖類模型,即用圖中的點(diǎn)和邊分別表示網(wǎng)絡(luò)中的節(jié)點(diǎn)和連線,從而構(gòu)成連通的網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).一個(gè)重要的模型就是人們將網(wǎng)絡(luò)模型化為一個(gè)連通有向(無(wú)向)圖,圖中的點(diǎn)集和弧集分別表示所有的處理機(jī)和系統(tǒng)中各處理機(jī)之間的通信聯(lián)系.從而網(wǎng)絡(luò)的可靠性,可通過(guò)有向圖或無(wú)向圖中的一些概念,比如連通度、邊連通度、弧連通度等來(lái)刻畫.因此,連通度成為反映網(wǎng)絡(luò)穩(wěn)定的重要參數(shù),這也就促成了圖的連通性成為圖論研究中的熱點(diǎn).利用簡(jiǎn)單圖的點(diǎn)連通度或邊連通度來(lái)精確分析網(wǎng)絡(luò)的穩(wěn)定性還存在一些不足.經(jīng)過(guò)研究,人們發(fā)現(xiàn)某些圖類,比如說(shuō),線圖、笛卡爾積、字典積、強(qiáng)積等變換圖都是由已知圖經(jīng)過(guò)特殊構(gòu)造而得到的更大的圖的重要結(jié)果,而通過(guò)這些變換圖可以得到各種各樣的網(wǎng)絡(luò)結(jié)構(gòu),從而,對(duì)各種變換圖或有向圖的連通性、邊連通性、弧連通性的研究,可以從理論上為可靠性網(wǎng)絡(luò)的設(shè)計(jì)提供科學(xué)的解決方法和手段.人們從對(duì)圖的連通度的研究發(fā)展到對(duì)各種變換圖的高階連通性的研究.本文主要研究某些特殊變換圖的連通性問(wèn)題.論文的正文部分分為三章:第一章,主要介紹了圖的連通性理論的研究背景和一些基本概念,給出了全變換有向圖Dxyz、笛卡爾積和字典積等的定義.最后介紹了本文的研究?jī)?nèi)容以及羅列出本文的主要研究成果.第二章,根據(jù)全變換有向圖的定義,可以得到27種全變換有向圖,但在這篇文章中我們主要研究與符號(hào)′0′有關(guān)的10種全變換有向圖的基本性質(zhì),例如:正則性、強(qiáng)連通性、λ-最優(yōu)以及超弧連通性.證明了這些全變換有向圖是強(qiáng)連通、λ-最優(yōu)以及超弧連通的充要條件.第三章,首先介紹了兩個(gè)有向圖的線圖、笛卡爾積和字典積有向圖的研究歷史及現(xiàn)狀.其次,定義了有向圖的bi-super性,并證明了線圖是bi-super的充要條件.最后,在已有的笛卡爾積和字典積有向圖的連通性研究的基礎(chǔ)上,繼續(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.
【學(xué)位授予單位】：新疆師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

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

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

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

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

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

5 吳靜;王鵬濤;魏國(guó)利;;帶周期的強(qiáng)連通有向圖的研究與應(yīng)用[J];天津工業(yè)大學(xué)學(xué)報(bào);2007年05期

6 劉愛霞;楊愛民;;擴(kuò)張的局部?jī)?nèi)(外)半完全有向圖的可跡性[J];中北大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年05期

7 師海忠;;有向圖語(yǔ)言[J];計(jì)算機(jī)工程與應(yīng)用;2011年22期

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

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

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

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

1 李剛;童，

本文編號(hào)：2476335