鏈接無(wú)向圖有向圖和樹(shù)

1、CHAPTER 6 GRAPHS, DIRECTED GRAPHS, AND TREESGlossarygraph：（無(wú)向）圖vertex set：頂點(diǎn)集edge set：邊集endpoint：端點(diǎn)incident on：關(guān)聯(lián)于adjacent：鄰接simple graph：簡(jiǎn)單（無(wú)向）圖loop：自回路，環(huán)multigraph：多（重）圖 labeled graph：標(biāo)號(hào)圖pseudograph：偽圖 utility：公用事業(yè)designing a chip：設(shè)計(jì)芯片planar graph：平面圖degree：度 isolated vertex：孤立結(jié)點(diǎn)subgraph：子圖 path：通

2、路，路徑 simple path：基本路徑 connected：連通的component：連通分支cycle：回路simple cycle：基本回路complete graph：完全圖bipartite graph：二部圖，偶圖complete bipartite graph：完全二部圖directed graph(digraph)：有向圖directed edge：有向邊initial vertex：起點(diǎn)terminal vertex：終點(diǎn)outdegree：出度indegree：入度source：源sink：匯directed multigraph：有向多重圖labeled directe

3、d graph：有向標(biāo)記圖directed subgraph：有向子圖directed path：有向通路（路徑）underlying graph：底圖strongly connected：強(qiáng)連通tree：樹(shù)directed tree：有向樹(shù)asymmetric：非對(duì)稱的leaf：葉（結(jié)點(diǎn)）internal vertex：分支結(jié)點(diǎn)root：根結(jié)點(diǎn)rooted tree：（有）根樹(shù)level：級(jí)height：高度parent：父結(jié)點(diǎn)child：子結(jié)點(diǎn)siblings：兄弟結(jié)點(diǎn)ancestor：祖先descendant：后代binary tree：二元（叉）樹(shù)m-ary tree：m元（叉）樹(shù)sp

4、anning tree：生成樹(shù)，支撐樹(shù)Euler cycle：歐拉回路Euler path：歐拉通路incidence matrix：關(guān)聯(lián)矩陣adjacency matrix：鄰接矩陣representation matrix：表示矩陣Warshalls algorithm：Warshall算法adjacency list representation：鄰接鏈表表示本章內(nèi)容及教學(xué)要點(diǎn)：6.1Graphs教學(xué)內(nèi)容：graph，vertex，edge，adjacent，incident，endpoints，loop，multigraph，pseudograph，degree，isolated ve

5、rtex，subgraph，path，simple path，connected，component，cycle，simple cycle，complete graph，bipartite graph6.2Directed Graphs教學(xué)內(nèi)容：directed graph，directed edge，outdegree，indegree，directed path，underlying graph，strongly connected 6.3 Trees教學(xué)內(nèi)容：tree，directed tree，leaf，internal vertex，root，rooted tree，binary t

6、ree，m-ary tree，spanning tree6.4 Euler Paths and Cycles教學(xué)內(nèi)容：Euler cycle，Euler path6.5 Incidence and Adjacency Matrices教學(xué)內(nèi)容：adjacency matrix定理證明及例題解答Graph theory is an old subject with many modern applications. Its basic ideas were introduced in the eighteenth century by the great Swiss mathematician

7、Leonard Euler. He used graphs to solve the famous Konisberg bridge problem. Graphs are used to solve problems in many fields. For instance, graphs can be used to determine whether a circuit can be implemented on a planar board. Graphs can be used to study the structure of the WWW. We can determine w

8、hether two computers are connected by a communications link using graph models of computer networks. Weighted graphs can be used to solve problems such as finding the shortest path between two cities in a transportation network. We can also use graphs to schedule exams and assign channels to televis

9、ion stations.圖論是以圖為研究對(duì)象的數(shù)學(xué)分支. 圖論中的圖指的是一些點(diǎn)以及連接這些點(diǎn)的線的總體. 通常用點(diǎn)代表事物，用連接兩點(diǎn)的線代表事物間的關(guān)系. 圖論則是研究事物對(duì)象在上述表示法中具有的特征與性質(zhì)的學(xué)科. 在自然界和人類社會(huì)的實(shí)際生活中，用圖形來(lái)描述和表示某些事物之間的關(guān)系既方便又直觀. 例如，國(guó)家用點(diǎn)表示，有外交關(guān)系的國(guó)家用線連接代表這兩個(gè)國(guó)家的點(diǎn)，于是世界各國(guó)之間的外交關(guān)系就被一個(gè)圖形描述出來(lái)了. 另外我們常用工藝流程圖來(lái)描述某項(xiàng)工程中各工序之間的先后關(guān)系，用網(wǎng)絡(luò)圖來(lái)描述某通訊系統(tǒng)中各通訊站之間信息傳遞關(guān)系，用開(kāi)關(guān)電路圖來(lái)描述IC中各元件電路導(dǎo)線連接關(guān)系(芯片設(shè)計(jì))等等.

10、事實(shí)上，任何一個(gè)包含了某種二元關(guān)系的系統(tǒng)都可以用圖形來(lái)模擬. 由于我們感興趣的是兩對(duì)象之間是否有某種特定關(guān)系，所以圖形中兩點(diǎn)之間連接與否最重要，而連接線的曲直長(zhǎng)短則無(wú)關(guān)緊要. 由此經(jīng)數(shù)學(xué)抽象產(chǎn)生了圖的概念. 研究圖的基本概念和性質(zhì)、圖的理論及其應(yīng)用構(gòu)成了圖論的主要內(nèi)容. 計(jì)算機(jī)中數(shù)據(jù)結(jié)構(gòu)離不開(kāi)數(shù)組、串、鏈表、樹(shù)和圖. 圖是計(jì)算機(jī)中數(shù)據(jù)表示、存儲(chǔ)和運(yùn)算的基礎(chǔ).圖論的產(chǎn)生和發(fā)展經(jīng)歷了二百多年的歷史，大體上可分為三個(gè)階段：第一階段是從1736年到19世紀(jì)中葉. 當(dāng)時(shí)的圖論問(wèn)題是盛行的迷宮問(wèn)題和游戲問(wèn)題. 最有代表性的工作是著名數(shù)學(xué)家Euler于1736年解決的哥尼斯堡七橋問(wèn)題(Konigsberg

11、Seven Bridges Problem). 東普魯士的哥尼斯堡城(現(xiàn)今是俄羅斯的加里寧格勒，在波羅的海南岸）位于普雷格爾(Pregel)河的兩岸，河中有一個(gè)島，于是城市被這條河、它的分支和島分成了四個(gè)部分，各部分通過(guò)7座橋彼此相通. 該城的居民喜歡在星期日繞城散步. 久而久之就產(chǎn)生了這樣一個(gè)問(wèn)題：能不能設(shè)計(jì)一條散步的路線，使得一個(gè)人從家里（或從四部分陸地任一塊）出發(fā)，經(jīng)過(guò)每座橋恰好一次再回到家里？這就是有名的哥尼斯堡七橋問(wèn)題. 哥尼斯堡七橋問(wèn)題看起來(lái)并不復(fù)雜，因此立刻吸引所有人的注意，但是實(shí)際上很難解決. 瑞士數(shù)學(xué)家(Leonhard Euler)注意到了這個(gè)問(wèn)題，并在1736年發(fā)表的“哥

12、尼斯堡七橋問(wèn)題”的文章中解決了這個(gè)問(wèn)題. 這篇論文被公認(rèn)為是圖論歷史上的第一篇論文，Euler也因此被譽(yù)為圖論之父. 歐拉把七橋問(wèn)題抽象成數(shù)學(xué)問(wèn)題一筆畫問(wèn)題，并給出一筆畫問(wèn)題的判別準(zhǔn)則，從而判定七橋問(wèn)題不存在解. Euler是這樣解決這個(gè)問(wèn)題的：將四塊陸地表示成四個(gè)點(diǎn)，橋看成是對(duì)應(yīng)結(jié)點(diǎn)之間的連線，則哥尼斯堡七橋問(wèn)題就變成了：從A，B，C，D任一點(diǎn)出發(fā)，通過(guò)每邊一次且僅一次返回原出發(fā)點(diǎn)的路線(回路)是否存在？Euler證明這樣的回路是不存在的. 第二階段是從19世紀(jì)中葉到1936年. 一開(kāi)始，圖論的理論價(jià)值似乎不大，因?yàn)閳D論主要研究一些娛樂(lè)性的游戲問(wèn)題：迷宮問(wèn)題、博弈問(wèn)題、棋盤上馬的行走線路問(wèn)題

13、. 但是隨著一些圖論中的著名問(wèn)題如四色問(wèn)題(1852年)和Hamilton環(huán)游世界問(wèn)題(1856年)的出現(xiàn)，出現(xiàn)了以圖為工具去解決其它領(lǐng)域中一些問(wèn)題的成果. 1847年德國(guó)的克?；舴?G.R.Kirchoff)將樹(shù)的概念和理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)研究. 1857年英國(guó)的凱萊(A.Cayley)也獨(dú)立地提出了樹(shù)的概念，并應(yīng)用于有機(jī)化合物分子結(jié)構(gòu)（C2H2n+2的同分異構(gòu)物數(shù)目）的研究中. 1936年匈牙利的數(shù)學(xué)家哥尼格(D.Konig)寫出了第一本圖論專著有限圖與無(wú)限圖的理論(Theory of directed and Undirected Graphs). 標(biāo)志著圖論成為一門獨(dú)立學(xué)科. 第

14、三階段是1936年以后. 由于生產(chǎn)管理、軍事、交通運(yùn)輸、計(jì)算機(jī)和通訊網(wǎng)絡(luò)等方面的大量問(wèn)題的出現(xiàn)，大大促進(jìn)了圖論的發(fā)展. 特別是電子計(jì)算機(jī)的大量應(yīng)用，使大規(guī)模問(wèn)題的求解成為可能. 實(shí)際問(wèn)題如電網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電路設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)以及社會(huì)科學(xué)中的問(wèn)題所涉及到的圖形都是很復(fù)雜的，需要計(jì)算機(jī)的幫助才有可能進(jìn)行分析和解決. 目前圖論在物理、化學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會(huì)科學(xué)及經(jīng)濟(jì)管理等幾乎所有學(xué)科領(lǐng)域都有應(yīng)用. 6.1 Graphs定義6.1.1 A graph(無(wú)向圖，圖) is a finite set V called the vertex set(頂點(diǎn)集) and

15、 a collection E of two-element subsets of V called the edge set(邊集). An element of E is called an edge(邊). A graph is denoted by G(V,E). The elements a and b of V are joined or connected(連接) by the edgea,b if a,bE.Graphs are usually represented by diagrams using dots for vertices and lines between t

16、heir dots for edges.定義6.1.2 If a,bE is an edge in a graph G(V,E), then the vertices a and b are called the endpoints(終點(diǎn)) of the edgea,b. The edge a,b is also said to be incident on(關(guān)聯(lián)于) the vertices a and b. Conversely, the vertices a and b are said to be incident on(關(guān)聯(lián)于) the edge a,b. Two vertices

17、a and b are adjacent(鄰接結(jié)點(diǎn)) if they are endpoints of an edge. Two edges are adjacent(鄰接邊) if they are incident on a common vertex.例6.1.1The graph G with V=a,b,c and E=a,b,b,c.例6.1.2The graph G with V=a,b,c,d,e and E=a,b,a,e,b,e,b,d,b,c,c,d).定義6.1.3 The graph G(V,E) is called a simple graph(簡(jiǎn)單圖) if th

18、ere is at most one edge between any two vertices and no edge from a vertex to itself. An edge from a vertex to itself is called a loop(自回路，環(huán)). Edges between two vertices are called parallel edges(平行邊，多重邊). In a multigrpah(多重圖，多圖), there may be parallel edges between two vertices. In a pseudograph(偽圖

19、), there may include parallel edges between two vertices and loops. 定義6.1.4 The degree(度數(shù)) of a vertex v, denoted by deg(v), is the number of edges that are incident on the vertex. A vertex with degree 0 is called isolated(孤立的).在一個(gè)圖中，以v為端點(diǎn)的邊數(shù)稱為v的度數(shù)，記為deg(v), 度數(shù)為0的頂點(diǎn)稱為孤立結(jié)點(diǎn).Euler握手定理定理6.1.1 (The Hands

20、haking Theorem) Let G(V,E) be a graph. Thendeg(v)=2|E|.That is, the sum of the degrees of the vertices of a graph is always even.一個(gè)圖的所有結(jié)點(diǎn)的度數(shù)之和是邊數(shù)的兩倍，從而是偶數(shù). 定理6.1.2 In any graph, there is an even number of vertices whose degree is odd.在任何圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)為偶數(shù)個(gè). 證明 定理6.1.2 定義6.1.5 A graph G(V,E) is a subgrap

21、h(子圖) of a graph G(V,E), denoted by G(V,E)G(V,E), if VV and EE. 定義6.1.6 Let G(V,E) be a graph with vertices v0,vkV. A path (通路，路徑) of length k from v0 to vk or between v0 and vk is a sequence v0e1v1e2v2e3v3vk-1ekvk such that v0,v1,vkV, e1,e2,ekE and ei=vi-1,vi. For simplicity, we denote this path as

22、 v0v1v2v3vk-1vk. A simple path(基本路徑) from v0 to vk is a path in which no vertex is repeated.在圖G(V,E)中，設(shè)v0,v1,vkV，e1,e2,ekE，其中vi-1，vi是邊ei的端點(diǎn)(i=1,2,k). 稱v0e1v1e2v2e3v3vk-1ekvk為從頂點(diǎn)v0到vk的通路(路徑)，v0和vm分別稱為該通路的起點(diǎn)和終點(diǎn)；稱通路上的邊數(shù)k為該通路的長(zhǎng)度.若通路經(jīng)過(guò)的頂點(diǎn)各不相同，則稱該通路為基本通路. 例6.1.3求下圖的通路、基本通路. 解 例6.1.3定義6.1.7 A graph G is ca

23、lled connected(連通的) if there is a path from any vertex to any other vertex in the graph. Otherwise, the graph is disconnected(不連通的). 給定無(wú)向圖G(V,E)且u,vV. 若存在從u到v的通路，則稱從u到v是可達(dá)的或稱u可達(dá)v. 若G的任何兩個(gè)頂點(diǎn)是相互可達(dá)的，則稱G是連通圖，否則稱G是不連通圖.定理6.1.3 Let G(V,E) be a graph. If there is a path from a vertex u to a vertex v, then

24、there is a simple path from u to v.證明 定理6.1.3 事實(shí)上，在一個(gè)具有n 個(gè)頂點(diǎn)的無(wú)向圖中，任何基本通路的長(zhǎng)度均不大于n-1.推論 A graph G is connected if and only if there is a simple path between any two vertices in G.定義6.1.8 Let G(V,E) be a graph. A subgraph G of G is a component (連通分支) of G if (1) G is a nonempty connected graph and(2) i

25、f G” is a connected subgraph of G and GG” then G=G”. 當(dāng)G是一個(gè)非連通圖時(shí)，它的獨(dú)立的不同連通部分稱為它的連通分支.定義6.1.9 Let G(V,E) be a graph. A cycle(回路) is a path of length greater than zero from a vertex to itself with no repeated edges. A simple cycle(基本回路) is a cycle from a vertex v to itself such that v is the only verte

26、x that is repeated.例6.1.4求下圖的回路、基本回路. 解 例6.1.4定義6.1.10 A graph is a complete graph(無(wú)向完全圖) if there is an edge between every two distinct vertices. A complete graph with n vertices is denoted by Kn. 例6.1.5K2，K3，K4，K5. 解 例6.1.5.定義6.1.11 Let G(V,E) be a graph. G is called a bipartite graph (二部圖，偶圖) if

27、its vertex set V can be partitioned into two disjoint sets A and B such that every edge in the graph connects a vertex in A and a vertex in B(so that no edge in G connects either two vertices in A or two vertices in B).A bipartite graph is called a complete bipartite graph(完全二部圖) Km,n if A contain m

28、 vertices, B contains n vertices, and for every aA,bB, a,bE. Thus, for every aA and bB, there is an edge connecting them.給定簡(jiǎn)單無(wú)向圖G(V，E)，V= AB，AB=. 若G中任一條邊的兩個(gè)端點(diǎn)，一個(gè)屬于A，另一個(gè)屬于B，則稱G為二部圖(偶圖) . 若|A|=m，|B|=n，且對(duì)任意uA，vB，u與v有邊相連，則稱G為完全二部圖，記為Km,n.ASSIGNMENTS：PP140：2，4，6，8，10，12，18，20，24，26，28，306.2Directed Graph

29、s定義6.2.1 A directed graph or digraph(有向圖) G(V,E), consists of a set V of vertices, together with a set E of ordered pairs of V called the set of directed edges(有向邊). If (a,b) E, then a is called the initial vertex(起點(diǎn)) of (a,b) and b is called the terminal vertex(終點(diǎn)).The edge (a,b) of a digraph is de

30、noted on the diagram by an arrow from a to b.例6.2.1 The digraph G with V=a,b,c and E=(a,b),(b,c),(c,b),(c,a).例6.2.2 The digraph G with V=a,b,c,d and E=(a,b),(b,c),(c,c),(b,d),(d,b),(c,d),(d,a).定義6.2.2 The outdegree(出度) of a vertex v, denoted by outdeg(v), is the number of edges for which v is the in

31、itial vertex. The indegree(入度) of a vertex v, denoted by indeg(v), is the number of edges for which v is the terminal vertex. If indeg(v)=0, then v is called a source(源). If outdeg(v)=0, then v is called a sink(匯).例6.2.3 The digraph G with V=a,b,c,d,e and E=(a,b),(a,b),(a,c),(b,c),(b,e),(c,d),(c,e),

32、(d,e).indeg(a)=0, indeg(b)=1, indeg(c)=2, indeg(d)=2, indeg(e)=3outdeg(a)=3, outdeg(b)=2, outdeg(c)=2, outdeg(d)=1, outdeg(e)=0a is a source and e is a sink. Similar to graphs, directed multigraphs, labeled digraphs and directed subgraphs can be defined.定義6.2.3 A directed path(有向通路) of length k from

33、 a to b is described by a sequence of vertices v0v1v2v3vk-1vk where v0=a and vk=b, and (vi-1,vi) is a directed edge for 1ik. 例6.2.4 The digraph G with V=a,b,c,d,e and E=(a,b),(a,b),(a,c),(b,c),(b,e),(c,d),(c,e),(d,e).定義6.2.4 Let G(V,E) be a digraph and G(V,E) be a directed subdigraph of G with the l

34、oops removed,i.e. E=E-(v,v): vV. Let E” be the symmetric closure of E and Es be the set of edges representing the relation E”. Then the graph Gs(V,Es) is called the underlying graph(底圖) of G.定義6.2.5 A digraph G(V,E) is connected(弱連通的) if its underlying graph is connected. A digraph G(V,E) is strongl

35、y connected(強(qiáng)連通的) if for every pair of vertices a,bV, there is a directed path from a to b.例6.2.5 PP144-145: 19, 21,27,29.定理6.2.1 (The Handshaking Theorem) Let G(V,E) be a digraph. Thendeg(v)=2|E|,outdeg(v)=|E|,indeg(v)=|E|.ASSIGNMENTS：PP143-145：4，6，8，20，22，24，26，28，346.3 Trees樹(shù)是圖論中一個(gè)既簡(jiǎn)單又非常重要的概念，在計(jì)算

36、機(jī)科學(xué)中應(yīng)用很廣泛，是一種基本的數(shù)據(jù)結(jié)構(gòu)和表示方法. 1847年德國(guó)的克?；舴?G.R.Kirchoff)將樹(shù)的概念和理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)研究. 1857年英國(guó)的凱萊(A.Cayley)也獨(dú)立地提出了樹(shù)的概念，并應(yīng)用于有機(jī)化合物分子結(jié)構(gòu)（C2H2n+2的同分異構(gòu)物數(shù)目）的研究中.定義6.3.1 A tree(無(wú)向樹(shù)，樹(shù)) is a connected graph that has no cycles. The vertices of degree 1 are called leaves(葉結(jié)點(diǎn)) and other vertices are called internal vertice

37、s(分支結(jié)點(diǎn)).樹(shù)是一個(gè)沒(méi)有回路的連通無(wú)向圖. 若一個(gè)不連通的無(wú)向圖的所有連通分支都是樹(shù)，則稱該無(wú)向圖為森林.定義6.3.2 A directed tree(有向樹(shù)) is a loop-free digraph, whose underlying graph is a tree.In a directed tree, if there is a path from a vertex a to a vertex b, it is unique. 例6.3.1 無(wú)向樹(shù).解 例6.3.1定理6.3.1 For any two vertices a and b of a tree T, there

38、is a unique simple path from a to b.定理6.3.2 If for any two vertices a and b in a graph G there is a unique simple path from a to b, then G is a tree.We can select a vertex as the root(根) of the tree. Then the tree has become a rooted tree(根樹(shù)). We can also change a rooted tree to a directed tree, cal

39、led the rooted directed tree derived from the rooted tree(從一棵根樹(shù)導(dǎo)出的有向根樹(shù)).定義6.3.3 In a rooted tree T, the level(級(jí)) of a vertex v is the length of the unique path from the root to v. The height(樹(shù)高) of a tree is the length of the longest path from the root to a leaf. In a rooted directed tree, if there

40、is a directed edge from u to v, then the vertex u is the parent(父結(jié)點(diǎn)) of v and v is the child(子結(jié)點(diǎn)) of u. If u is the parent of v and v, then v and v are called siblings(兄弟結(jié)點(diǎn)). If there is a directed path from vertex u to vertex v, then u is called an ancestor(祖先結(jié)點(diǎn)) of v and v is called a descendant(后

41、代結(jié)點(diǎn)) of u. If the largest outdegree for any vertex of the tree is m, then the tree is called an m-ary tree(m叉樹(shù)). In particular, if m=2, then the tree is called a binary tree(二叉樹(shù)).定理6.3.3 A tree with v vertices has v-1 edges.定理6.3.4 If a connected graph G has e edges and v vertices and v=e+1, then G

42、is a tree.定理6.3.5 A tree with at least one edge has at least two vertices with degree 1.定義6.3.4 A tree T is a spanning tree for a graph G, if T is a subgraph of G, if every vertex in G is a vertex in T.定理6.3.6 Every connected graph has a spanning tree. ASSIGNMENTS：PP148-150：2，4，10，12，18，20，22，24，26，

43、28，30，42，44，466.4 Euler Paths and Cycles 定義6.4.1 Let G(V,E) be a graph. A cycle that includes all of the edges and the vertices of G is called an Euler cycle(歐拉回路). When this occurs, we say that the graph G has an Euler cycle.給定無(wú)向圖G(V,E)，通過(guò)G中的所有邊和頂點(diǎn)的回路稱為歐拉回路. 存在歐拉回路的圖稱為歐拉圖.例6.4.1哥尼斯堡七橋問(wèn)題: 這是否是一個(gè)歐拉圖?

44、例6.4.2一筆畫問(wèn)題. 定理6.4.1 A graph with more than one vertex has an Euler cycle if and only if it is connected and every vertex has even degree.至少有兩個(gè)頂點(diǎn)的無(wú)向圖G是歐拉圖G連通且所有結(jié)點(diǎn)的度數(shù)都是偶數(shù).證明 定理6.4.1例6.4.3這些圖是否是歐拉圖?解 例6.4.3例6.4.4下列圖形是否可以一筆畫成. 解 例6.4.4定義6.4.2 Let G(V,E) be a graph. A path that includes each of the edge

45、s of G exactly once is called an Euler path(歐拉通路). When this occurs, we say that the graph G has an Euler path.給定無(wú)向圖G(V,E)，通過(guò)G中的所有邊恰好一次的通路稱為歐拉通路. 我們稱該圖存在歐拉通路.定理6.4.2 A connected graph has an Euler path if and only if exactly two vertices have odd degree.無(wú)向連通圖G有歐拉通路G恰好只有兩個(gè)結(jié)點(diǎn)的度數(shù)是奇數(shù).定義6.4.3 Let G(V,E)

46、be a digraph. A directed cycle that includes all of the edges and the vertices of G is called an Euler cycle(歐拉回路). When this occurs, we say that the graph G has an Euler cycle.給定有向圖G(V,E)，通過(guò)G中的所有邊和頂點(diǎn)的有向回路稱為歐拉回路. 存在歐拉回路的圖稱為歐拉圖.定理6.4.3 A digraph has an Euler cycle if and only if it is strongly connec

47、ted and the indegree of every vertex is equal to its outdegree.有向圖G是歐拉圖G強(qiáng)連通且所有頂點(diǎn)的出度等于入度.定理6.4.4 A strongly connected digraph has an Euler path if and only if there is a vertex whose indegree is equal to its outdegree+1, and there is a vertex whose indegree is equal to its outdegree-1, and the indegr

48、ee of all other vertices is equal to its outdegree.強(qiáng)連通的有向圖G有歐拉通路G恰有一個(gè)頂點(diǎn)其出度比入度多1，另一個(gè)頂點(diǎn)其出度比入度少1，且所有其他頂點(diǎn)的出度等于入度.ASSIGNMENTS：PP148-150：2，6，10，126.5 Incidence and Adjacency MatricesHow to represent a graph in a computer?定義6.5.1 Let G(V,E) be a graph(digraph). Let B be a matrix whose rows are labeled by t

49、he vertices of G and whose columns are labeled by the same vertices in the same order. Bij=1 or 0 whether there is an edge from the ith vertex to the jth vertex. The matrix B is called the adjacency matrix(鄰接矩陣) of G.鄰接矩陣的一個(gè)重要應(yīng)用是尋圖中固定長(zhǎng)度的通路.例6.5.1求下列圖的鄰接矩陣.解 例6.5.1Boolean matrix operations(布爾矩陣運(yùn)算)A Boolean matrix is an m×n matrix whose entries are either zero or one. Let A=a and B=b be m×n Boolean matrices. We define AB=C=c, the join of A and B(布爾矩陣的并), by and AB=C=d, the meet of A and B(布爾矩陣的交), by 例6.5.2 Let A= and B=. We haveAB= , AB=Let A=aij is an m×p Boolea