Math 332 Graph Theory and Its Applications (Spring 2019)


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

Meeting time and location: TR 2-3:20pm Jones Hall 306

Web pages:

Office Hours: TR 10-11am or by appointment. Homework help session every Wednesday at 12-1pm 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 Tuesday April 30, 2-5pm. Location: Jones Hall 306 (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 Friday 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 every Wednesday 12-1pm 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