圖形理論導論

介紹圖形理論中常見的問題、定理以及應用。課程著重在常見問題與其相關基礎定理的介紹,在各章節中也會介紹章節主題在各領域的應用範例。此外也會透過程式作業,讓同學練習圖形理論相關的程式設計,使同學具有圖形理論的基礎知識與實作能力。 ** 疫情期間,暫時採用線上教學,第一堂的上課網址: https://nycu.webex.com/nycu/j.php?MTID=m146a57a4f90742c21f5760e55ab301ee 密碼:E2fmpSB2cD6 之後上課方式會在E3課程網站上公布。

離散數學、計算機概論與程式設計

無備註

Slides with blackboard All materials and course information will be available on E3. 呂爾軒:59280 宋秉軒:59280 凃岳昕:59280 萬芊伶:59280 黃信富:59280 邱昱翔:59280

1. Program assignment: 50% 2. Test: 50%

• 1. Graph models, terminology, and proofs

  1.1 Tournaments 1.2 Introduction to Graph Models and Terminology 1.3 Matrix Representation 1.4 Proof Techniques 1.5 Degree Sequence 1.6 Tournaments Revisited

  講授：

  6 hrs

• 2. Graph routes

  2.1 Eulerian Circuits 2.2 Hamiltonian Cycles 2.3 Shortest Paths

  講授：

  9 hrs

• 3. Trees

  3.1 Spanning Trees 3.2 Tree Properties 3.3 Rooted Trees 3.4 Additional Applications

  講授：

  6 hrs

• 4. Connectivity and flow

  4.1 Connectivity Measures 4.2 Connectivity and Paths 4.3 Network Flow

  講授：

  9 hrs

• 5. Matching

  5.1 Matching in Bipartite Graphs 5.2 Matching in General Graphs 5.3 Stable Matching

  講授：

  9 hrs

• 6. Graph coloring

  6.1 Four Color Theorem 6.2 Vertex Coloring 6.3 Edge Coloring

  講授：

  6 hrs

• 7. Planarity

  7.1 Kuratowski's Theorem

  講授：

  3 hrs

Graph theory: An introduction to proofs, algorithms, and applications Karin R. Saoub CRC press 1st Ed., 2021

地點

EC441

時間

M 7,8

聯絡方式

31364 ylli@cs.nctu.edu.tw