圖形理論

Graph theory has been widely applied to various research areas. This course introduces well-known theoretical graph models and their applications and focuses on theorem deduction. Students can know more detailed properties of these graph models and their deduction processes, which are helpful preliminary practices to develop your own solid research model. Some small cases will be studied to clarify the procedures of practical applications, such as graph model construction, design of useful theorems and efficient algorithm design based on deduced theorems.

algorithm (undergraduate)

無備註

textbook aided with slides on padPC, course web site : E3 助教: 陳立偉, TEL: 59281 柯秉廷 , TEL: 59281 王宏孝, TEL: 59281 林世庭, TEL : 59281

assignments: 30%, test: 50%, project: 20%

• Introduction to Graph Models

  a. Graphs and Digraphs b. Common Families of Graphs c. Graph Modeling Applications d. Walks and Distance e. Paths, Cycles, and Trees f. Vertex and Edge Attributes: More Applications

  講授：

  5 hrs

• Structures and Representation

  a. Graph Isomorphism b. Automorphisms and Symmetry c. Subgraphs d. Some Graph Operations e. Tests for Non-Isomorphism f. Matrix Representations g. More Graph Operations

  講授：

  5 hrs

• Trees

  a. Characterizations and Properties of Trees b. Rooted Trees, Ordered Trees, and Binary Trees c. Binary-Tree Traversals d. Binary-Search Trees e. Huffman Trees and Optimal Prefix Codes f. Priority Trees g. Counting Labeled Trees: Prufer Encoding

  講授：

  5 hrs

• Spanning Trees

  a. Tree Growing b. Depth-First and Breadth-First Search c. Minimum Spanning Trees and Shortest Paths d. Applications of Depth-First Search e. Cycles, Edege-Cut, and Spanning Trees f. Graphs and Vector Spaces g. Matroids and the Greedy Algorithm

  講授：

  5 hrs

• Connectivity

  a. Vertex- and Edge-Connectivity b. Constructing Reliable Networks c. Max-Min Duality and Menger's Theorems d. Block Decompositions

  講授：

  5 hrs

• Optimal Graph Traversals

  a. Eulerian Trails and Tours b. DeBruijn Sequences and Postman Problems c. Hamiltonian Paths and Cycles d. Gray Codes and Traveling Salesman Problems

  講授：

  5 hrs

• Planarity and Kuratowski's Theorem

  a. Planar Drawings and Some Basic Surfaces b. Subdivision and Homeomorphism c. Extending Planar Drawings d. Kuratowski's Theorem e. Algebraic Tests for Planarity f. Planarity Algorithm g. Crossing numbers and Thickness

  講授：

  6 hrs

• Drawing Graphs and Maps (Optional)

  a. The Topology of Low Dimensions b. Higher-Order Surfaces c. Mathematical Model for Drawing Graphs d. Regular Maps on a Sphere e. ImBeddings on Higher-Order Surfaces f. Geometric Drawings of Graphs

  講授：

  3 hrs

• Graph Colorings

  a. Vertex-Colorings b. Map-Colorings c. Edge Colorings d. Factorization (Optional)

  講授：

  3 hrs

• Measurement and Mappings (optional)

  a. Distance in Graphs b. Domination in Graphs c. Bandwidth (Optional) d. Intersection Graphs (Optional) e. Linear Graph Mappings (Optional) f. Modeling Network Emulation (Optional)

  講授：

  3 hrs

• Network Flows and Applications

  a. Flows and Cuts in Networks b. Solving the Maximum-Flow Problem c. Flows and Connectivity d. Matchings, Transversals, and Vertex Covers

  講授：

  4 hrs

"Graph Theory and Its Applications" by Jonathan L. Gross and Jay Yellen, Second Edition. Publisher: Chapman & Hall/CRC

地點

EC441

時間

Mon. EF

聯絡方式

TEL:31364, email: ylli@cs.nctu.edu.tw