Math 332 Graph Theory and Its Applications (Fall 2024)


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

Meeting time and location: MW 3:30-4:50pm Jones Hall 301

Web pages:

Office Hours: TBD or by appointment. Homework help session TBD at Jones 131.

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 on TBD. Location: Jones Hall 301 (tentatively).

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 Sunday 11:59pm. Late homework sets will be accepted with a penalty (1% off per late hour). The lowest homework grade will be dropped.

Start homework early and work steadily!

Help Session: A weekly homework help session will be offer TBD at Jones Hall 131.

Attendance: Regular attendance is critical for your success in this course. I expect your presence at every lecture.

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