Section outline

  • Graph theory has become fundamental in computer science as it provides numerous techniques and algorithms for solving complex problems represented by graphs.

    In this module, we present step by step this mathematical theory, giving priority to both modeling the solution of certain problems using graphs and providing a set of techniques for students to solve these problems through algorithms.

    The goal is not, of course, to turn students in this option into specialists in graph theory, but to demonstrate how the judicious use of graph properties can make certain concrete problems accessible to mathematical reasoning.

    We propose exercises adapted to each chapter and detailed corrections for some of them.

    This course is intended for second-year students in the Computer Science program.

    The course covers the official program prescribed in the latest CANVAS for the academic year 2018 - 2019.

    Basic knowledge of Mathematics and algorithmic are prerequisites to make the most out of this work. The weekly workload required to master the content is 1.5 hours for lectures and 1.5 hours for tutorials. Two types of assessment are considered: continuous evaluation and a final exam. The graph theory module has a coefficient of 2 and 4 credits.

    • Course Content منتدى

      Chapter I. Basic definitions                                 

       1. "Intuitive" definition of a graph

      2. Mathematical definition of a graph

      3. Order, orientation and multiplicity

                  3.1. Order

                  3.2. Orientation

                  3.3. Multiplicity

      4. Relations between the elements of a graph

                  4.1 Relations between vertices

                  4.2 Relations between arcs and vertices

                  4.3 Graph qualifiers

      5. Matrices associated with a graph

                 5.1 Vertex-arc incidence matrix

                 5.2 Adjacency matrix or vertex-vertex incidence matrix

                 5.3 Condensed form of sparse matrices

      6. Vocabulary related to connected graph

                 6.1 Chain, path, length

                 6.2 Connected graph

                 6.3 Cycle and circuit

                 6.4 Cocycle and Cocircuit.

      Chapter II. Cycles

      1. Cyclomatic and cocyclomatic numbers

                   1.1 Decomposition of cycles and cocycles into elementary sums

                   1.2 Arc Colouring Lemma (Minty 1960)

                   1.3 Cycle basis and  cocycle basis

      2. Planarity

                    2.1 Planar Graph

                    2.2 Euler's formula

                    2.3 Kuratowski's theorem (1930)

                    2.4 Dual graph

      3. Tree, forest and arborescence

                    3.1 Definitions

                    3.2 Properties

                    3.3 Maximum (or spanning) tree

      Chapter III. Flow problems

      1. Definitions

      2. Search for a maximum flow in a transport network

                    2.1 Definition

                    2.2 Ford-Fulkerson theorem

                    2.3 Ford-Fulkerson algorithm

      3. Search for a compatible flow

      Chapter IV. Pathway problems

      1. Search for connected components

                    1.1 Presentation of objectives

                    1.2 Trémeaux-Tarjan algorithm

      2. Finding the shortest path

                    2.1 Presentation of the conditions

                    2.2 Moore-Dijkstra algorithm

      3. Search for a spanning tree of maximum weight in a graph

                    3.1 Presentation of objectives

                    3.2 Kruskal Algorithm (1956)

      Chapter V. Hamiltonian and Eulerian Problems

      1. Hamiltonian Problem

                    1.1 Definitions

                    1.2 Necessary condition for the existence of a Hamiltonian cycle

                    1.3 Sufficient condition for the existence of a Hamiltonian circuit

                    1.4 Sufficient condition for the existence of a Hamiltonian cycle

      2. Eulerian Problem

                    2.1 Definitions

                    2.2 Necessary and sufficient condition for the existence of an Eulerian chain

                    2.3 Local algorithm to construct an Eulerian cycle

                    2.4. Relation between Eulerian and Hamiltonian problem

      Chapter VI. Colouring

       1. Definitions

      2. Vertex colouring

      3. Arc colouring

      4. Proposals

      5. The "4 colours" theorem

      6. Perfect graph