数学专业英语－The Theory of Graphs

yunjiang · 发表于 2004-5-6 09:46:35

<

>In this chapter, we shall introduce the concept of a graph and show that graphs can be defined by square matrices and versa.
<

>1. Introduction
<

>Graph theory is a rapidly growing branch of mathematics. The graphs discussed in this chapter are not the same as the graphs of functions that we studied previously, but a totally different kind. 
 Like many of the important discoveries and new areas of learning, graph theory also grew out of an interesting physical problem, the so-called Konigsberg bridge problem. (this problem is discussed in Section 2) The outstanding Swiss mathematician, Leonhard Euler (1707-1783) solved the problem in 1736, thus laying the foundation for this branch of mathematics. Accordingly, Euler is called the father of graph theory.
 Gustay Robert Kirchoff (1824-1887), a German physicist, applied graph theory in his study of electrical networks. In1847, he used graphs to solve systems of linear equations arising from electrical networks, thus developing an important class of graphs called trees.
 In 1857, Arthur Caylcy discovered trees while working on differential equations. Later, he used graphs in his study of isomers of saturated hydrocarbons.
 Camille Jordan (1838-1922), a French mathematician, William Rowan Hamilton, and Oystein Ore and Frank Harary, two American mathematicians, are also known for their outstanding contributions to graph theory. 
 Graph theory has important applications in chemistry, genetics, management science, Markov chains, physics, psychology, and sociology.
 Throughout this chapter, you will find a very close relationship between graphs and matrices. 
2. The Konigsberg Bridge Problem
The Russian city of Konigsberg (now Kaliningrad, Russia) lies on the Pregel River.(See Fig.1) It consists of banks A and D of the river and the two islands B and C. There are seven bridges linking the four parts of the city.
 Residents of the city used to take evening walks from one section of the city to another and go over some of these bridges. This, naturally, suggested the following interesting problem: can one walk through the city crossing each bridge exactly once? The problem sounds simple, doesn’t it?You might want to try a few paths before going any further. After all, by the fundamental counting principle, the number of possible paths cannot exceed 7!=5040. Nonetheless, it would be time consuming to look at each of them to find one that works.
 
<v:shapetype><v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path connecttype="rect" gradientshapeok="t" extrusionok="f"></v:path><lock aspectratio="t" v:ext="edit"></lock></v:shapetype><v:shape><v:imagedata></v:imagedata></v:shape>
 
Fig .1 The city of Konigsberg
In 1736, Euler proved that no such walk is possible. In fact, he proved a far more general theorem, of which the Konigsberg bridge problem is a special case. 
 
<v:shape><v:imagedata></v:imagedata></v:shape>
Fig .2 A mathematical model for the Konigsberg bridge problem

 Let us construct a mathematical model for this problem.rcplace each area of the city by a point in a plane. The points A, B, C,and D denote the areas they represent and are called vertices. The arcs or lines joining these points represent the represent the respective bridges. (See图２)They are called edges. The Konigsberg bridge problem can now be stated as follows: Is it possible to trace this figure without lifting your pencil from paper or going over the same edge twice? Euler proved that a figure like this can be traced without lifting pencil and without traversing the same edge twice if and only if it has no more than weo vertices with an odd number of edges joining them. Observe that more than two vertices in the figure have an odd number of edges connecting them-----in fact,they all do.

yunjiang · 发表于 2004-5-6 09:47:01

<

0cm 0cm 0pt"> <

0cm 0cm 0pt 18pt; TEXT-INDENT: -18pt; tab-stops: list 18.0pt; mso-list: l41 level1 lfo53">1. Graphs<

0cm 0cm 0pt">Let us return to the example Friendly Airlines flies to the five cities, Boston (B), Chicago (C), Detroit (D), Eden (E), and Fairyland (F) as follows: it has direct daily flights from city B to cities C, D, and F, from C to B, D, and E; from D to B, C, and F, from E to C, and from F to B and D. This information, though it sounds complicated, can be conveniently represented geometrically, as in 图3. Each city is represented by a heavy dot in the figure; an arc or a line segment between two dots indicates that there is a direct flight between these cities.<v:shapetype><v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path connecttype="rect" gradientshapeok="t" extrusionok="f"></v:path><lock aspectratio="t" v:ext="edit"></lock></v:shapetype><v:shape><v:imagedata></v:imagedata><v:textbox style="mso-next-textbox: #_x0000_s1026"></v:textbox><w:wrap type="tight"></w:wrap></v:shape> What does this figure have in common with 图２? Both consist of points (denoted by thick dots ) connected by arcs or line segments. Such a figure is called a graph. The points are the vertices of the graph; the arcs and line segments are its edges. More generally, we make the following definition:A graph consists of a finite set of points, together with arcs or line segments connecting some of them. These points are called the vertices of the graph; the arcs and line segments are called the edges og the graph. The vertices of graph are usually denoted by the letters A, B, C, and so on. An edge joining the vertices A and B is denoted by AB or A-B.Fig .3 图２and 图3 are graphs. Other graphs are shown in 图4. The graph in图２ has four vertices A, B, C, and D, and seven edges AB, AB, AC, BC, BD, CD, and BD. For the graph in图4b, there are four vertices, A, B, C, and D, but only two edges AD and CD. Consider the graph in图4c, it contains an edge emanating from and terminating at the same vertex A. Such an edge is called a loop. The graph in图4d contains two edges between the vertices A and C and a loop at the vertex C. <v:shape><v:imagedata></v:imagedata></v:shape> The number of edges meeting at a vertex A is called the valence or degree of the vertex, denoted by v(A). For the graph in图4b, we have v(A)=1, v(B)=0, v(C)=1, and v(D)=2. In图4b, we have v(A)=3, v(B)=2, and v(C)=4. A graph can conveniently be described by using a square matrix in which the entry that belong to the row headed by X and the column by Y gives the number of edges from vertex X to vertex Y. This matrix is called the matrix representation of the graph; it is usually denoted by the letter M. The matrix representation of the graph for the Konigsberg problem is <v:shape><v:imagedata></v:imagedata></v:shape>Clearly the sum of the entries in each row gives the valence of the corresponding vertex. We have v(A)=3, v(B)=5, v(C)=3, as we would expect. Conversely, every symmetric square matrix with nonnegative integral entries can be considered the matrix representation of some graph. For example, consider the matrix A B C D <v:shape><v:imagedata></v:imagedata></v:shape>Clearly, this is the matrix representation of the graph in 图5. <v:shape><v:imagedata></v:imagedata></v:shape>

yunjiang · 发表于 2004-5-6 09:47:15

<DIV class=Section1 style="LAYOUT-GRID: 15.6pt none"><

0cm 0cm 0pt; TEXT-ALIGN: center" align=center>Vocabulary</DIV> <DIV class=Section2 style="LAYOUT-GRID: 15.6pt none"><

0cm 0cm 0pt">Network 网络<

0cm 0cm 0pt">Electrical network 电网络</DIV> <DIV class=Section3 style="LAYOUT-GRID: 15.6pt none">Isomer 异构体 emanate 出发，引出</DIV> <DIV class=Section4 style="LAYOUT-GRID: 15.6pt none">Saturated hydrocarbon 饱和炭氢化合物 terminate 终止，终结</DIV> <DIV class=Section5 style="LAYOUT-GRID: 15.6pt none">Genetics 遗传学valence 度</DIV> <DIV class=Section6 style="LAYOUT-GRID: 15.6pt none">Management sciences 管理科学node 结点</DIV> <DIV class=Section7 style="LAYOUT-GRID: 15.6pt none">Markov chain 马尔可夫链interconnection 相互连接</DIV> <DIV class=Section8 style="LAYOUT-GRID: 15.6pt none">Psychology 心理学 Konigsberg bridge problem 康尼格斯堡桥问题</DIV> <DIV class=Section9 style="LAYOUT-GRID: 15.6pt none">Sociology 社会学Line-segment 线段</DIV>

yunjiang · 发表于 2004-5-6 09:47:30

<

0cm 0cm 0pt; TEXT-ALIGN: center" align=center>Notes<

0cm 0cm 0pt 18pt; TEXT-INDENT: -18pt; TEXT-ALIGN: left; tab-stops: list 18.0pt; mso-list: l13 level1 lfo54" align=left>1. Camille Jordan, a French mathematician, William Rowan Hamilton and . . .<

0cm 0cm 0pt; TEXT-ALIGN: left" align=left> 注意：a French mathematician 是Camille Jordan 的同位语不要误为W.R.Hamilton 是a French mathematician 同位语这里关于W.R.Hamilton 因在本文前几节已作介绍，所以这里没加说明。２．After all, by the fundamental counting principle, the number of possible paths cannot exceed 7!= 5040. Nonetheless, it would be time consuming to look at each of them to find one that works. 意思是：毕竟，由基本的计算原理知，可能的路径的总数，不会超过5040个。然而逐一地去考察这些路径是否有一条路适合题意，那是太耗费时间了，that works 意思是：“有效”，这里可理解为：“适合题意”。3.It is possible to trace the figure without lifting your pencil from paper or going the same edge twice? 意思是：是否能够跟踪图形而使你的铅笔不离开纸且不走过同一条边两次呢？这一句在英语上等同于without lifting your pencil from paper and without going over the same edge twice. 1. . . .in fact, they all do. 这里they代表顶点vertices; do 代表have an odd number of edges connecting them.2. A is called the valence or degree of the vertex, denoted by v(A).注意denoted 前面的逗号，可使读者不至于误会v(A)是用来记vertex的。这里v(A)是用来记Ａ的Ｖalence.６. the entry that belongs to the row headed by X and column headed by Y gives the number of edges from vertex X to vertex Y. 意思是：属于Ｘ行，Ｙ列这一项的数字给出了从顶点Ｘ到顶点Ｙ的边数。这里the row headed by X意是冠以Ｘ的行，可简称Ｘ行或等Ｘ行。

yunjiang · 发表于 2004-5-6 09:47:42

<

0cm 0cm 0pt; TEXT-ALIGN: center" align=center>Exercise<

0cm 0cm 0pt; TEXT-ALIGN: left" align=left>Ⅰ.answer the following questions:<

0cm 0cm 0pt 39pt; TEXT-INDENT: -18pt; TEXT-ALIGN: left; tab-stops: list 39.0pt; mso-list: l46 level2 lfo55" align=left>1. How is the Konigsberg Bridge problem stated?2. According to Euler’s theorem, why is the answer of the Konigsberh Bridge Problem negative?Ⅱ.Translate the following passages into Chinese: When a number of electrical components are connected together, we are said to have an electrical network. The junction between two or more components in a network are called nodes of the network, Each path joining a pair of nodes and through interconnections is best described by a diagram which eliminates all the electrical properties of the components. This graph is obtained by redrawing the circuit of the network with lines replacing the electrical components. The graph makes clear the existence of a number of closed paths which may be traced along the branches. Such closed paths are called loops. Of the total number of loops of a network, a certain number of independent loops may be chosen. One way of choosing a set of independent loops is as follows:form, from the network, a sub-network by removing branches until no loops remain, although each node is still connected by a single path to another node. Such a structure is called a tree of the network.Ⅲ.Translate the following sentences into English (in each sentence, make use of the phrase given in bracket):下面简写The Konigsberg Bridge problem 为Ｋ.B.问题１．Ｋ.B.问题只不过是尤拉所证明的定理的一个特例。(a special case)２．从尤拉关于图论的一个定理，即可得Ｋ.B.问题的答案。(follows immediately from.)３．Ｋ.B.问题的不可能性是尤拉定理的一个直接结果。(a direct consequence of)

		自动登录	找回密码
密码			注-册-帐-号