研究生课程教学大纲 the so-called spanning trees in the circuits,and then discovered Kirchhoff's current law;the tree is also a special network topology model and data storage model (especially binary trees). (2)Jordan's theorem actually gives an algorithm to find the radius and center of the tree,and this theorem corresponds to the layout in the center of the area.This theorem has a guiding role in the allocation of resources that should be placed in the regional center.If the location of a community hospital is determined,the center of the model can be modeled. (3)Radia Joy Perlman designed the Spanning Tree Protocol in 1981.This protocol is a communication protocol that works on the second layer (data link layer)of the OSI network model to prevent loops caused by redundant links in switches.It is used to ensure that there is no loop in the logical topology of the Ethernet,avoiding the broadcast storm. (4)When calculating the number of spanning trees of the graph using the Cayley recursion method,the resulting subgraph will rise exponentially (exponential explosion),which is an exponential calculation method.When the order of the graph is higher,it is generally impossible to count (5)When using the broken circle method to find the minimum spanning tree of the graph, the spanning tree is obtained by deleting the maximum weight edge in a cycle at each step by the greedy method,and the tree is the minimum survival tree.If the problem is transformed into deleting the cycle at each step by one vertex,how many vertices should be deleted to make the graph become an acyclic graph?This is the feedback vertex set (Feedback Vertex Set)problem. The broken circle method and the feedback point set problem are similar in appearance,one deletes the edge and the other deletes vertices to make the remaining graphs have no cycles. However,the complexity of the problem is quite different(a small difference,a thousand miles away).In fact,for a graph G whose maximum degree does not exceed 4,the problem is NP-hard. In graph theory,there are many such problems in,the conditions are small,but the conclusions are very different,which is a characteristic of discrete mathematics that is different from continuous mathematics. Chapter 3.Connectivity of graph(6 hr) (1).Teaching contents: a.Cut edge,cut vertex and block (2 hr); b.Connectivity of graph and its application(2 hr); c.Wide diameter and wide distance(2 hr). (2).Teaching requirements: By learning this chapter,students will understand graph theory and practical significance of connectivity,and grasp properties of connectivity and Menger Theorem. (3).Key points of teaching: a.Concepts related to connectivity; b.Definitions and concepts of connectivity 11研究生课程教学大纲 11 the so-called spanning trees in the circuits, and then discovered Kirchhoff's current law; the tree is also a special network topology model and data storage model (especially binary trees). (2) Jordan's theorem actually gives an algorithm to find the radius and center of the tree, and this theorem corresponds to the layout in the center of the area. This theorem has a guiding role in the allocation of resources that should be placed in the regional center. If the location of a community hospital is determined, the center of the model can be modeled. (3) Radia Joy Perlman designed the Spanning Tree Protocol in 1981. This protocol is a communication protocol that works on the second layer (data link layer) of the OSI network model to prevent loops caused by redundant links in switches. It is used to ensure that there is no loop in the logical topology of the Ethernet, avoiding the broadcast storm. (4) When calculating the number of spanning trees of the graph using the Cayley recursion method, the resulting subgraph will rise exponentially (exponential explosion), which is an exponential calculation method. When the order of the graph is higher, it is generally impossible to count. (5) When using the broken circle method to find the minimum spanning tree of the graph, the spanning tree is obtained by deleting the maximum weight edge in a cycle at each step by the greedy method, and the tree is the minimum survival tree. If the problem is transformed into deleting the cycle at each step by one vertex, how many vertices should be deleted to make the graph become an acyclic graph? This is the feedback vertex set (Feedback Vertex Set) problem. The broken circle method and the feedback point set problem are similar in appearance, one deletes the edge and the other deletes vertices to make the remaining graphs have no cycles. However, the complexity of the problem is quite different (a small difference, a thousand miles away). In fact, for a graph G whose maximum degree does not exceed 4, the problem is NP-hard. In graph theory, there are many such problems in, the conditions are small, but the conclusions are very different, which is a characteristic of discrete mathematics that is different from continuous mathematics. Chapter 3. Connectivity of graph (6 hr) (1). Teaching contents: a. Cut edge, cut vertex and block (2 hr); b. Connectivity of graph and its application (2 hr); c. Wide diameter and wide distance (2 hr). (2). Teaching requirements: By learning this chapter, students will understand graph theory and practical significance of connectivity, and grasp properties of connectivity and Menger Theorem. (3). Key points of teaching: a. Concepts related to connectivity; b. Definitions and concepts of connectivity