Graph Theory
Résumé de section
-
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.
-
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
-
-
As noted in the Introduction, graph theory is a branch of mathematics that deals with problems using specific types of diagrams called graphs. Graph theory has many applications across a wide range of fields, including operations research, physics, chemistry, computer science, and other scientific disciplines. In this chapter, we introduce some fundamental concepts of graph theory and provide a variety of examples. We also present several elementary results.
-
In this chapter, we explore important concepts related to cycles and their fundamental role in graph theory. We begin by studying the decomposition of cycles and cocycles, the Arc Colouring Lemma proposed by Minty (1960), and the notions of cycle and cocycle bases. We then introduce the cyclomatic and cocyclomatic numbers, which measure the structure and connectivity of a graph. Next, we address the concept of planarity, where we learn how to determine whether a graph can be drawn on a plane without edge intersections. This section includes Euler’s formula, Kuratowski’s theorem (1930), and the idea of a dual graph. Finally, we study trees, forests, and arborescences, focusing on their definitions, main properties, and the construction of maximum (or spanning) trees, which are key structures in many applications of graph theory.
-
In this chapter, we study flow problems in transport networks.
First, we introduce the basic definitions related to networks, capacities, and flows.Then, we focus on the problem of finding a maximum flow in a transport network. We define the concept of maximum flow and present the Ford–Fulkerson theorem, which gives the theoretical foundation of the method. After that, we explain the Ford–Fulkerson algorithm used to compute the maximum flow.
Finally, we study the problem of finding a compatible flow, that is, a flow that satisfies given constraints in the network.
-
This chapter is devoted to the study of pathway problems in graph theory, which consist of determining specific structures or properties within a graph by following its vertices and edges according to well-defined rules. These problems are fundamental in various applications such as network design, communication systems, transportation, and optimization.
In the first section, we focus on the search for connected components, which aims to identify all subsets of vertices where each pair of vertices is connected by a path. The Trémeaux–Tarjan algorithm is introduced as an efficient method for detecting both connected and strongly connected components in undirected and directed graphs, respectively.
The second section deals with the problem of finding the shortest path between vertices in a weighted graph. After presenting the main conditions of the problem, we describe the Moore–Dijkstra algorithm, which provides an optimal and systematic way to compute the minimum distance from a given source vertex to all others.
Finally, the third section addresses the construction of a spanning tree of maximum weight in a connected graph. The objective is to select a subset of edges that connects all vertices while maximizing the total weight. For this purpose, the Kruskal algorithm (1956) is presented as a classical and effective approach.
Through these three parts, the chapter offers a unified understanding of fundamental graph traversal and optimization techniques that form the basis of many modern computational applications.
-
In graph theory, two fundamental types of traversal problems are the Hamiltonian and Eulerian problems. Both deal with finding specific paths or cycles that visit the vertices or edges of a graph under certain conditions.
A Hamiltonian cycle is a closed path that visits each vertex of the graph exactly once before returning to the starting vertex. Determining whether such a cycle exists is a central and challenging question in graph theory, often associated with complex combinatorial structures.In this chapter, we present the main definitions and discuss both necessary and sufficient conditions for the existence of Hamiltonian paths and cycles.
On the other hand, an Eulerian cycle is a closed path that traverses every edge of the graph exactly once. The study of Eulerian graphs dates back to the 18th century with Euler’s solution to the famous Königsberg bridge problem. We will recall the definitions, establish the necessary and sufficient conditions for the existence of an Eulerian cycle, and describe a simple local algorithm for its
construction.Finally, the chapter concludes with a discussion of the relations between Hamiltonian and Eulerian problems, highlighting the similarities and fundamental differences between these two classic graph-theoretic concepts.
-
Graph colouring is one of the fundamental topics in graph theory. It consists of assigning colours to certain elements of a graph (its vertices or its edges) subject to specific constraints. The main objective is to perform this colouring using the smallest possible number of colours while ensuring that adjacent elements do not share the same colour.
This chapter presents the essential concepts and results related to graph colouring.
In the first section, we introduce the basic definitions of vertex and edge colouring and the associated notions such as chromatic number and chromatic index.
The second section focuses on vertex colouring, which consists of partitioning the set of vertices into stable subsets.
The third section deals with arc (edge) colouring, where colours are assigned to the edges of the graph so that adjacent edges receive different colours.
The fourth section recalls some important propositions and theorems, including bounds on the chromatic number.
The fifth section presents the famous Four Colour Theorem, which applies to planar graphs and states that any planar map can be coloured with at most four colours.
Finally, the sixth section introduces the notion of perfect graphs, an important class of graphs in which the chromatic number equals the size of the largest clique for every induced subgraph.