圖形理論導論

Elementary graph theory

學期

111-1

學分

3 學分

當期課號

515612

永久課號

CSCS20009

開課單位

資訊工程學系

授課教師

李毅郎

校區

光復

類別

選修

上課時間表

節	週一
5 13:20–14:10	圖形理論導論 EC022 2 節連堂
6 14:20–15:10	圖形理論導論 EC022 2 節連堂

* 根據陽明交大上課時間表所列

概述

介紹圖形理論中常見的問題、定理以及應用。課程著重在常見問題與其相關基礎定理的介紹,在各章節中也會介紹章節主題在各領域的應用範例。此外也會透過程式作業,讓同學練習圖形理論相關的程式設計,使同學具有圖形理論的基礎知識與實作能力。

先修科目

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

教學方式

基礎圖論課程目前規劃先以線上教學、實體考試為主。底下是課程群組的連結,請欲選修同學透過連結申請加入群組,方能參與線上課程。加選結束後會再剔除未選修同學。 https://teams.microsoft.com/l/team/19%3aQ3wET2_9cNce45zOBb9kOrfzj5Ur7KAoTTTN_7zoZ8k1%40thread.tacv2/conversations?groupId=4e5b538d-ff49-4222-b46f-c31973ecf6f5&tenantId=80a9abdb-7cef-443c-b040-3f8e75e9232e Slides with blackboard All materials and course information will be available on E3. 課程助教:李庭緯,劉祐誠, 林廷昕,郭家佑,鄭宇軒:59281 程式作業助教:楊秉宇,王昱宸,吳柏橙

評分方式

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

課程大綱

1. Graph models, terminology, and proofs
2. Graph routes
3. Trees
4. Connectivity and flow
5. Matching
6. Graph coloring
7. Planarity

教科書

1. "Graph theory: An introduction to proofs, algorithms, and applications", Karin R. Saoub, CRC press , 1st Ed., 2021 2. "Graph Theory and Its Applications" by Jonathan L. Gross and Jay Yellen, Second Edition. Publisher: Chapman & Hall/CRC

Office Hours

地點: EC441
時間: M 7,8
聯絡方式: 31364 ylli@cs.nctu.edu.tw