Futher-mathematics-Topic-9-network.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2017/5/11,#,Chapter 9:Undirected,graphsand networks,Thomas Zhou,总体浏览,9.1,Kick off with CAS,9.2,Basic concepts of a network,9.3,Planar graphs and Eulers formula,9.4,Walks,trails,paths,cycles and circuits,9.5,Trees and their applications,9.6,Review,单词,Vertex-,顶点,Edge-,边,Isolated vertex-,孤立顶点,Loop-,回路,Parallel edges-,平行边,Multiple edges-,多重边,Simple connection-,简单连接,Node-,节点，结点，网点,单词,Degree-,度,Isomorphic-,同形,Diagonally symmetric-,对角对称,例,1,：,Count the number of vertices and edges in,the network,shown.,例,2,Determine the degree of each vertex in the figure shown.,例,3,Label the vertices and edges for the figure shown,There are several points to note about this representation:,1,.there is no 3 in the list of edges(,E,).This implies it is an isolated vertex.,2.the number of pairs in,E,(1,4),(1,2),.=8 which must be the same as,the number,of edges,3.the number of times a vertex appears anywhere inside,E,equals the,degree of,the vertex.For example,the digit 4 appears 5 times,so the degree,of vertex,4=5.,4.from this representation of,V,and,E,we can construct(or reconstruct),the original,graph.,例,4,Construct a graph(network)from the following list of vertices and edges.,V,=,A,B,C,D,E,E,=,(A,B),(A,C),(A,D),(B,C),(B,D),(B,D),(C,E),(D,E),(E,E),例,5,Represent the network shown(from Worked example 4)as a matrix.,矩阵方法数度的时候，要将对角线上的数加,*2,，因为是回路是二度的。,作业：,9.2,T1,3,5,7,9,10,12,13,16,例题,Construct a network from the following list of vertices and edges.then calculate the degree of each vertex,a,V=1,2,3,4,E=(1,2),(1,4),(2,3),(3,4),例题,Construct a network from the following list of vertices and edges.then calculate the degree of each vertex,b,V=A,B,C,D,E,E=(A,B),(A,C),(A,C),(B,B),(B,C),(B,D),(C,D),例题,Consider a network of 4 vertices,where each vertex is connected to each of the other 3 vertices with a single edge(no loops,isolated vertices or parallel edges).,a List the vertices and edges.,b Construct a diagram of the network.,c List the degree of each vertex,例题,Construct a network representing the following family tree.Use a single node to represent each married couple.,Allan and Betty had 3 children:Charles,Doris and Earl.,Charles married Frances and had 2 children,George and Harriet.,Doris married Ian and had 1 child,John.,Earl married Karen and had 3 children,Louise,Mary and Neil.,例题,Represent the following networks by matrices,例题,Represent the following networks by matrices,例题,Represent the following networks by matrices,例题,Construct networks from the following matrix representations.,Note that the number of rows=number of columns=number of vertices.,Watch out for loops,例题,Construct networks from the following matrix representations.,Note that the number of rows=number of columns=number of vertices.,Watch out for loops,例题,Construct networks from the following matrix representations.,Note that the number of rows=number of columns=number of vertices.,Watch out for loops,9.3Planar graphs,平面图形,and Eulers formula,欧拉公式,1.Degenerate graph,退化图像,2.Complete graph,完整图像,3.,planar graph.,-If a graph has no edges which cross,then it is a planar graph.,平面图形是指一个图形没有交错的边,The regions of a planar graph,faces,Converting non-planar graphs,例题：,Convert the graph below to a planar graph.Indicate the faces(regions)of the planar graph.,Convert the graph below to a planar graph.Indicate the faces(regions)of the planar graph.,Degree of the each face,=the number of edges defining that region,例题,Find the degree of each face of the graph shown in the figure.,Converting three-dimensional solids to planar graphs,将三维几何体转化成平面图形,The figure blow shows a cube with vertices,V=A,B,C,D,E,F,G,H.,Convert this to a planar graph,Vertex,3,4,5,6,Edge,Face,Eulers formula,欧拉公式,Vertices=edges faces+2,V=E F+2,作业,9.3,9.4,Walks,trails,paths,cycles and,circuits,通路,，足迹，路径，回路,Walks,通路,trails,小径,;,足迹,Paths,路径,;,小路,Cycles,回路,Circuit,回路,;,无向图中的概念,1.Walks,通路,从一个顶点通到另一个顶点,1-3-4,；,A-B-C,2.Connected graphs,连通图,If there is a walk between all possible pairs,of vertices,then it is a connected graph,.,一,个能够通遍所有的顶点的图，叫,连通图,3.,Trail,足迹,A trail is a walk in which no edges are repeated,.,没有任何边是被重复的走法叫,足迹,哥尼斯堡问题,18,世纪初,普鲁士,的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如右上图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点,。,后来大数学家,欧拉,把它转化成一个几何,问题,一笔画问题,。他不仅解决了此问题，且给出了连通图可以一笔画的充要条件是：,奇点的数目不是,0,个就是,2,个,（,连到一点的数目如是奇数条，就称为奇点，如果是偶数条就称为偶点，要想一笔画成，必须中间点均是偶点，也就是有来路必有另一条去路，奇点只可能在两端，因此任何图能一笔画成，奇点要么没有要么在两端,4.,Euler trail,欧拉足迹,An Euler trail is one which uses every edge exactly once,.,恰好将每一条边都使用一次的足迹叫,欧拉足迹,莱昂哈德,欧拉,Leonhard Euler,，,1707,年,4,月,15,日,1783,年,9,月,18,日,），,瑞士,数学家、,自然科学家,。,1738,年，瑞典数学家,欧拉,(Leornhard Euler,),解决,了柯尼斯堡问题,。,由此,图论诞生。欧拉也成为图论的创始人,欧拉足迹的判断方法,1.For an Euler trail to exist,all vertices must be of an even degree,or,there must,be exactly,two vertices of odd degree,.,所有点的,偶数度,；或者,恰有两个点是,奇数度,2.If the degrees of,all,the vertices are even numbers,start with,any,vertex.In,this case,the starting vertex and ending vertex are the same,.,所有点为,偶数度,的情况下，可以从任意一点开始行走,3.If there are two vertices whose degree is an odd number use either as a,starting point,.The other vertex of odd degree must be the ending point,.,如果有两个点为,奇数度,，则可以从这两个点中的任何一个点出发，另一个点就是终点,欧拉足迹的判断方法,均为偶数度顶点,从任意一顶点出发都可以,恰有两个奇数度顶点,从其中一个顶点出发，则另一个就是终点,例,10,Using the following figure,identify an Euler trail.,起点,3,中点,5,例,10,Using the following figure,identify an Euler trail.,起点,3,中点,5,例,10,Using the following figure,identify an Euler trail.,终点,3,起点,5,例,10,Using the following figure,identify an Euler trail.,终点,3,起点,5,5.Circuit,s:kt,回路,A,circuit,is a trail beginning and ending at the same vertex,.,一个具有相同起点和终点的足迹叫回路,6.,Euler circuit.,欧拉回路,An Euler circuit is an Euler trail where the starting and ending,vertices are,the same,.,具有相同起点和终点的欧拉足迹叫欧拉回路,备注：,An,Euler circuit,cannot,exist for planar graphs that,have,any,vertices whose,degree is odd,.,欧,拉回路的判断前提是确定所有顶点均为,偶数度,例,11,：,Find,an Euler circuit for the planar graph shown,vertex,Degree,1,2,3,4,5,An Euler circuit,algorithm,欧拉回路的运算法则,前提,Consider,a network where all vertices are of even,degree,Step1,：,Starting a vertex,选个顶点,Choose smallest possible path which returns to vertex,找小路径,choose a single vertex in turn as the starting vertex,再选顶点,Add any new vertices,from,subcircuits,加入新点,Repeat steps 3 and 4,重复三四,Join points.,联合顶点,例,12,.,Find one possible Euler circuit for the network,shown using,the Euler circuit algorithm.,S=1,2,3,CHOOSE 1,1-2-3-1,CHOOSE 2,2-6-5-4-2,S=1,2,3,4,5,6,CHOOSE 3,3-9-8-7-6-10-3,S=1,2,3,4,5,6,7,8,9,10=V,1-2-3-9-8-7-6-10-3,7.Path,路径,A path is a walk in which no vertices are repeated(except,possibly the,start and finish,).,一个没有是任何顶点重复的走法叫,路径,（除了可能的,起点和终点,）,8.Cycle,回路,A cycle is a path beginning and ending at the same,vertex,具有相同起点和终点的路线叫,回路,哈密顿,1.,哈密顿,(William Rowan Hamilton 1805,1865),英国数学家，物理学家，力学家。,1805,年,8,月,4,日生于爱尔兰,都柏林,；,1865,年,9,月,2,日卒于爱尔兰,都柏林,2.,哈密顿图,（哈密尔顿图）（英语：,Hamiltonian path,，或,Traceable path,）是一个无向图，由天文学家,哈密顿,提出，由指定的,起点,前往指定的,终点,，途中经过所有其他,节点且只经过一次,。,3.,在,图论中是指含有哈密顿回路的图，闭合的哈密顿,路径,称作哈密顿回路（,Hamiltonian cycle,），含有图中所有顶点的路径称作哈密顿路径。,天文学家,哈密顿,(William Rowan Hamilton),提出，,在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径,。,哈密顿,问题寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。,9.,Hamiltonian,path,哈密尔顿路径,In Euler trails and circuits each edge was used,exactly once,while vertices could be re-used.,Now,consider the case where it is desirable to use each vertex,exactly once,as in our travelling salesman problem mentioned at the start of this section,A,Hamiltonian path uses every vertex exactly once,.,所有顶点只被使用了一次的路径叫,哈密尔顿,路径,。,But,not all edges need to be,used.,但并不是所有的边都要被使用。,例,13,Determine a Hamiltonian path in the planar,graph shown.,Hamiltonian,hmltnn,10.,Hamiltonian,cycles,哈密尔顿回路,A Hamiltonian cycle is a Hamiltonian path which starts and finishes at,the same,vertex,.,拥有相同起点和终点的,哈密尔顿路径,叫,哈密尔顿回路,闭合的哈密尔顿路径叫,哈密尔顿回路,例,14,Determine a Hamiltonian cycle in the planar graph shown.,作业：,9.4 T1,，,3,，,5,，,7,，,9,，,10,温故知新,单词以及含义,Walk,；,trials,；,path,；,cycle,；,circuit,；,Euler trial;Euler circuit;,Hamiltonian path;,Hamiltonian cycle:,欧拉回路的判断方法：,哈密尔顿回路的寻找方法：,9.5Trees and their applications,1.Graphs and subgraphs,图像和子图,2.If the graph contains such quantities,then it is called a,weighted graph.,加权图,3.Trees,A tree is a connected subgraph which cannot contain any:,1.loops,2.parallel(or multiple)edges,3.cycles.,例题：,Determine whether each of the figures is a tree,and if not,explainwhy not.,树的好处,The advantage of trees within a network is that the tree could determine an efficient connection between vertices in the sense that there is a minimum distance,cost or time.,Shortest paths,Determine the shortest path between nodes A and F in the figure shown.Nodes are labelled A,.,G and distances(in metres)between them are labelled in blue.,Find the shortest path from vertex 1 to vertex 9.Vertices are labelled in black,distances in blue.(,Note:Lines are not to scale.),