Math 332 Graph Theory and Its Applications (Fall 2020)


Instructor: Gexin Yu, Jones 127, phone: 221-2040, gyu@wm.edu

Meeting time and location: TR remote asynchronous

Web pages:

Office Hours:by appointment via zoom. Homework help session every Thursday 9-10pm via Zoom.

Text: (for reference)

Course goal: This is an introductory course about graph theory and its applications on natural and social sciences. We discuss many famous applications and study graph-theoretic concepts such as paths, Eulerian circuits, trees, distance, matchings, connectivity, network flows, colorings, planarity, and spanning cycles. We will also talk about how to apply graph theory concepts in the analysis of social networks.

This is intended to be a COLL 200 course. It sits in the NQR (the Natural world and Quantitative Reasoning) domain, but contains significant applications and motivations in Cultures, Societies, and the Individual (CSI) domain. At each topic, there is a case study/project/reading component, which requires students to read or work on some related topics in natural or social sciences. Throughout the course, the students will be guided to explore the properties and structures of social networks and at the last two weeks, we will introduce how to model and analyze the social networks. Our reading examples including molecule constitutional isomers and graph isomorphism in chemistry, Nobel Prize laureate's speech on matching theory and applications in economics, the philosophical significance of Four Color Problem, gene recombination, and how NFL schedule the games et al. Projects includes design Apps to improve the course registration process, design routes for more efficient door-to-door campaign, and model popular social medias, just to name a few.

Tests: there is no mid-term tests.

Final Exam: a comprehensive final exam will be offered remotely).

Homework: There will be weekly homework assignments. We cannot emphasize the importance of homework enough. Although understanding material while you read the text or listen to lecture is certainly important, your most important studying will be in completing the homework assignments. Homework sets (with .tex and .pdf files) will be posted on blackboard. You are expected to type them with latex and submit a pdf file on the site. Homework usually will be due on Saturday 11:59pm and a solution set will be posted shorter after that. Late homework sets will NOT be accepted. The lowest homework grade will be dropped.

Start homework early and work steadily!

Help Session: A weekly homework help session will be offer Thursday 9-10pm via Zoom.

Attendance: I do expect to see your present at the homework help sessions.

Grading: Your final grade is calculated as follows:

Honor Code: Students will uphold William and Mary's stated honor code as it is written, any infractions will be referred to the Honor Council.

ADA accommodation: William & Mary accommodates students with disabilities in accordance with federal laws and university policy. Any student who feels s/he may need an accommodation based on the impact of a learning, psychiatric, physical, or chronic health diagnosis should contact Student Accessibility Services staff at 757-221-2509 or at sas@wm.edu to determine if accommodations are warranted and to obtain an official letter of accommodation. For more information, please see www.wm.edu/sas