Graph Theory

Modeling problems with graphs. Connected components, Eulerian and Hamiltonian cycles - applications in network communications. Scheduling problems, critical paths. The chinese postman problem. Matching problems. Flows in networks, max flow-min cut theorem. Networks with upper and lower bounds on edge capacities. Maximum flow-minimum cost: applications on network design. Transportation networks. Special graph classes and graph isomorphism. Stability of a graph, chromatic number and chromatic index: applications. Maximum clique and densest sub-graph problems: polynomial cases on special graph classes (chordal, interval, perfect graphs).