Go to Main Content

Lebanese American University WWW Information System

 

HELP | EXIT

Detailed Course Information

 

Date
Apr 24, 2017
Transparent Image
Information Select the desired Level or Schedule Type to find available classes for the course.

MTH 309 - Graph Theory
This course covers the fundamental concepts and methods of graph theory, and their applications in various areas of computing. Topics include graphs as models, representation of graphs, trees, distances, matching, connectivity, and flows in networks, graph colorings, Hamiltonian cycles, traveling salesman problem, and planarity.

Course Learning Outcomes:
1) Students will be familiar with classical graph-theoretic terms. In particular, they will be able to define graphs, paths, cycles, trees, cliques, connectivity, and coloring.
2) Students will be able to prove classical results in graph theory.
3) Students will be able to understand algorithmic techniques for graph problems such as graph traversals, topological sorting, Euler formula and tours, minimum spanning trees, shortest path problems, and matching problems.
4) Students will be able to understand theorems and algorithms related to graph connectivity, coloring and planarity.
5) Students will be able to understand theorems and algorithms related to various forms of graph containment: minors, topological minors, etc…
6) Students will be able to understand theorems and algorithms related to Tree and Path decompositions, and the various graph metrics such as: treewidth, pathwidth, cutwidth, etc…
7) Students will be familiar with several NP-hard problems, such as Maximum Clique, Vertex Cover, Chromatic Number, Dominating Set, etc…

3.000 Credit hours
3.000 Lecture hours

Levels: Undergraduate
Schedule Types: Lecture, Tutorial

Computer Science & Mathematics Division
Mathematics Department

Restrictions:
May not be enrolled in one of the following Programs:     
      Freshman Science
      Freshman Arts
May not be enrolled in one of the following Degrees:     
      Executive MBA

Prerequisites:
Undergraduate level MTH 201 Minimum Grade of D

Return to Previous New Search
Transparent Image
Skip to top of page
Release: 8.5.4