研究生课程教学大纲 Curriculum ideology: (1)The adjacency matrix and the incidence matrix of graphs are important ways for computers to store graphs.Studying graphs from the perspective of matrices naturally links the knowledge of linear algebra and matrix theory with graph theory,which is a major research direction of algebraic graph theory,such as the application of the incidence matrix to prove the handshake theorem is a good example. (2)The example of identifying different configurations of NaNiOz crystals by applying the graph isomorphism method illustrates that the graph isomorphism method also has important applications in other disciplines. (3)The crystals of many chemical substances are in the shape of a regular polyhedron.For example,the crystal of table salt is a regular hexahedron,and the crystal of alum is a regular octahedron.The study of regular polyhedrons can be traced back to the Plato era.Plato regards the "four classical elements"as elements,and its shape is like four regular polyhedrons.The study of regular polyhedrons is also related to the famous Euler polyhedron formula(there are only 5 types of regular polyhedrons). (4)Hypercube is an important graph class (it can be defined in three equivalent ways, namely set method,sequence method,Cartesian product method).Due to its good symmetry and high connectivity,it has been widely studied,especially,it is also an interconnection network topology. Chapter 2.Tree(6 hr) (1).Teaching contents: a.Definition and properties of tree(2 hr); b.Spanning tree(2 hr); c.Minimum spanning tree (2 hr); (2).Teaching requirements: By learning this chapter,students will understand practical significance and theories of tree, grasp the concepts of tree,spanning tree and algorithms of minimum spanning tree. (3).Key points of teaching: a.Definition and properties of tree; b.Algorithms of minimum spanning tree and their applications. (4).Teaching difficulties:Proof of Kruskal's algorithm. Curriculum ideology: (1)Trees are not only a relatively simple structure of graphs(in many cases as a test field for some conclusions),but also have applications in other fields.British mathematician Arthur Cayley used the tree model to study the counting of chemical isomers in 1875;As early as the 19th century,the physicist Kirchhoff had noticed the relationship between the independent circuits and 10研究生课程教学大纲 10 Curriculum ideology: (1) The adjacency matrix and the incidence matrix of graphs are important ways for computers to store graphs. Studying graphs from the perspective of matrices naturally links the knowledge of linear algebra and matrix theory with graph theory, which is a major research direction of algebraic graph theory, such as the application of the incidence matrix to prove the handshake theorem is a good example. (2) The example of identifying different configurations of NaNiO2 crystals by applying the graph isomorphism method illustrates that the graph isomorphism method also has important applications in other disciplines. (3) The crystals of many chemical substances are in the shape of a regular polyhedron. For example, the crystal of table salt is a regular hexahedron, and the crystal of alum is a regular octahedron. The study of regular polyhedrons can be traced back to the Plato era. Plato regards the "four classical elements" as elements, and its shape is like four regular polyhedrons. The study of regular polyhedrons is also related to the famous Euler polyhedron formula (there are only 5 types of regular polyhedrons). (4) Hypercube is an important graph class (it can be defined in three equivalent ways, namely set method, sequence method, Cartesian product method). Due to its good symmetry and high connectivity, it has been widely studied, especially, it is also an interconnection network topology. Chapter 2. Tree (6 hr) (1). Teaching contents: a. Definition and properties of tree (2 hr); b. Spanning tree (2 hr); c. Minimum spanning tree (2 hr); (2). Teaching requirements: By learning this chapter, students will understand practical significance and theories of tree, grasp the concepts of tree, spanning tree and algorithms of minimum spanning tree. (3). Key points of teaching: a. Definition and properties of tree; b. Algorithms of minimum spanning tree and their applications. (4). Teaching difficulties: Proof of Kruskal’s algorithm. Curriculum ideology: (1) Trees are not only a relatively simple structure of graphs (in many cases as a test field for some conclusions), but also have applications in other fields. British mathematician Arthur Cayley used the tree model to study the counting of chemical isomers in 1875; As early as the 19th century, the physicist Kirchhoff had noticed the relationship between the independent circuits and