Math585 Algebraic Graph Theory | 代數圖論

Announcements

Course Info top

Textbook

Graphs and Matrices
   Ravindra B. Bapat
***** electronic version available at the library *****Course website

Further Resources

Spectra of Graphs
   Andries E. Brouwer and Willem H. Haemers
***** electronic version available at the library *****

A Combinatorial Approach to Matrix Theory and Its Applications
   Richard A. Brualdi and Dragoš Cvetković
***** electronic version available at the library *****

Learning objectives

Graph theory is a universal tool to model many objects, including computer networks, social networks, relationships, and so on. On the other sides, matrices provide an intuitive way to record the data on graphs (weight, flow, capacity, and so on), while the eigenvalues and eigenvectors are holding the essential information of the data. In this course, we will focus on the adjacency matrix and the Laplacian matrix of a graph and introduce their applications, for example, counting the number of walks, modeling random walks, characterization of regular graphs, counting the number of spanning trees, graph partition, graph drawing, etc. Throughout the course, you will experience various beautiful relations between graphs and matrices.

Outlines

Evaluation

30% Homework + 10% Active Learning + 20% Midterm1 + 20% Midterm2 + 20% Survey

Tentative Schedule top

Calendar

Homework/Quiz top

There are 30 homework assignments.

Homework: The homework will be assigned in each class. We will discuss how to solve the problems, but you have to type your answers in detail afterward. We will review your writing on Thursdays. See NSYS Cyber University > Announcements for more details.

Active Learning: It is critical that you cultivate your active learning skills, which are not just for this course. You have to learn how to make a learning plan for yourself and how to stick with your plan. In this course, we introduce two things that you can do on a daily basis: one is for English learning, and the other is for mathematics learning.

  1. VoiceTube Pronunciation Challenge: Listen to the sentence and record your voice. That's it! You will learn new vocabularies day by day and build your listening/speaking skills at the same time.
  2. Play with a mathematics concept: Memorizing something is the very basic level of understanding. To understand a concept, you have to keep playing with it in your brain. For example, we will learn very soon about the Rayleigh quotient. Once you have learned this idea, you may ask yourself lots of questions:
    • What is a Rayleigh quotient? Is it defined only on symmetric matrices? Or it also works for general matrices.
    • What are the relations between the Rayleigh quotient and the eigenvalues? What are the examples to illustrate the relations?
    • Does Rayleigh quotient work for Hermitian matrices?
    Try to throw a question to yourself every once in a while, and try to catch it by answering the question. You will gain deeper understand of the concept. And more importantly, it's fun!

See NSYS Cyber University > Announcements for more details.

Exams: After each exam, the questions and the sample answers will be uploaded below.

Policies/Ethics top

Accessibility

Students with diverse learning styles and needs are welcome in this course. In particular, if you have a disability/health consideration that may require accommodations, please feel free to approach me.

Grading

Percentage scores will be converted to letter grades according to the university-wide standard table.

Attendance

You are expected to attend the classes.

Missing work

If you miss some course components due to illness, accident, family affliction, or religious observances, please talk to me and provide the documentation. In such cases, the course component is excused, and your course score will be calculated by distributing the weight of the missed item(s) across the other course components. Missing components are limited to at most 20%.

Academic integrity

Do not copy others' work, including others' homework, the textbook, online materials, and others' answers in an exam; if it is really necessary, add proper citations to your references. It makes no point (and gives you no point) if the work is not yours since you learned nothing.