Syllabus
(PDF File)
NOTE: This file is in PDF
format and requires Adobe Acrobat Reader to view. You may download Adobe
Acrobat Reader at http://www.adobe.com/products/acrobat/readstep.html.
Dr. Sarada Herke Graph Theory Videos
Assignments (PDF File)
Review for Test II
Review for Final Examination
POWER
POINT PRESENTATIONS
NOTE: Note these PowerPoint presentations are PDF files.
Chapter 1: Graphs
Section 1.1:
Fundamental Concepts and Notation
Section 1.2:
Elementary Properties and Operations
Section 1.3:
Alternate Representations of Graphs
Section 1.4:
Algorithms
Section 1.5:
Degree Sequences
Section 1.6:
Fundamental Counting
Chapter
2: Paths and Searching
Section 2.1:
Distance
Section 2.2:
Connectivity
Section 2.4:
Problem Solving and Heuristics
Chapter
3: Trees
Section 3.1:
Fundamental Properties of Trees
Section 3.2:
Minimal Weight Spanning Trees
Section 3.3:
Counting Trees
Section 3.6:
Binary Trees
Chapter
4: Networks
Section 4.1:
Flows
Section 4.2: The
Ford and Fulkerson Approach
Section 4.3: The Dinic Algorithm and Layered Networks
Section 4.6:
Connectivity and Networks
Chapter
5: Cycles and Circuits
Section 5.1:
Eulerian Graphs
Section 5.2:
Adjacency Conditions for Hamiltonian Graphs
Section 5.3:
Related Hamiltonian-like Properties
Section 5.4: Forbidden
Subgraphs
Section 5.6: The
Traveling Salesman Problem
Chapter
6: Planarity
Section 6.1:
Euler’s Formula
Section 6.2:
Characterizations of Planar Graphs
Section 6.3: A
Planarity Algorithm
Chapter
7: Matchings
Section 7.1:
Matchings and Bipartite Graphs
Section 7.2:
Matching Algorithms and Marriage
Chapter
8: Independence
Section 8.1:
Vertex Independence and Coverings
Section 8.2:
Vertex Colorings
Section 8.3:
Approximate Coloring Algorithms
Section 8.5: The
Four Color Theorem