CSC 565 Graph Theory

Basic concepts of graph theory, including: paths and connectivity, Euler tours and Hamilton cycles, matchings and independence, graph coloring, planarity, directed graphs and network flows, vector spaces associated with a graph, and applications with emphasis on organizing problems for computer solution. 3 credit hours.

 
   
   
Prerequisite
  

Linear Algebra and Discrete Mathematics (prerequisites)
Proof techniques, induction, logic, generating counterexamples

 
Course Objectives  
  • To introduce students to the language of graph theory and the utility of graphs to model a wide variety of problems.
  • To teach the fundamental results of graph theory and the mathematical tools required to prove those results.
  • To teach the mathematical techniques required to reason about graphs and to solve graph problems.
  • To impart an understanding of the relative di±culty of graph problems from a computational standpoint.

 
Course Topics  
  • definitions, cliques, independent sets, bipartite graphs, complement, special graphs
  • vertex degrees, regular graphs, graph representation, isomorphism, subgraphs, induced subgraphs
  • paths and connection, induction and proof techniques
  • cut vertices and edges, Eulerian circuits, directed graphs
  • trees, spanning trees, characterizations
  • distance in graphs, diameter, eccentricity, center, radius, Wiener index
  • spanning trees and enumeration
  • optimization and trees
  • maximum matchings
  • vertex covers, independent sets, edge covers
  • connectivity, blocks, edge connectiviy, bonds
  • 2-connectivity, Menger's theorem
  • network flows
  • graph coloring
  • edge coloring
  • hamiltonian cycles
  • planarity

 
Course Requirements  

HOMEWORK PROJECTS:

  • There will be biweekly homework projects. These will be challenging problem-solving exercises, and will be the fundamental mechanism for learning the skills described in the course objectives.
  • Homework projects must be typeset, preferably using LaTeX, including all figures.

EXAMINATIONS:

  • Three exams of roughly equal weight (Exam 1, Exam 2, Final Exam (cumulative))
  • (All exams will be in-class, closed-book, closed-notes exams.)

 
Textbooks  

Introduction to Graph Theory, Second Edition, by Douglas B. West, Prentice Hall, ISBN 0130144002.
Computer and Internet Requirements  

NCSU has recommended minimum specifications for computers used for classes. Depending on your computer needs, we recommend your computer meet or exceed the following minimum specifications below.

PCs must have an Intel-compatible 1 GHz processor, 512 MB RAM, 60 GB hard drive with 1 GB free space available, 256 Color Display, CD-ROM drive, 1024x768 (min.) video adapter, sound card, and speakers. The operating system should be Windows XP Pro. Real One Player Basic (available free online) and high speed Internet connection such as cable, DSL, T1 or LAN will be required for EOL courses.

MAC users must have a G4 processor with firewire and USB factory built-in, 512 MB RAM, 60 GB with 1GB free space available, 256 Color Display, CD-ROM drive, 1024x768 (min) video adapter, sound card, and speakers. The operating system must be MacOS 10.4 (minimum) along with the above RealOne and Internet specifications above.

For more detailed information on computer specifications and recommendations, please refer to our website at: http://engineeringonline.ncsu.edu/currentstudents/computeraccess.htm

 

Instructor  

Dr. Carla D Savage, Professor
Engineering Bldg II (COE II) 3-262, Box 8206
NCSU Campus
Raleigh, NC 27695

Phone: 919-515-7863
EMail: savage@eos.ncsu.edu
Instructor Website: http://www.csc.ncsu.edu/faculty/savage/