ECTS
4 credits
Component
Faculty of Science
Description
In a first part, deepen the basic notions of enumeration seen in L1 and L2.
In a second part, introduce the combinatorial study of graphs.
Objectives
This EU will address the following:
Enumeration
- Notion of cardinal. Number of applications between two finite sets, number of parts of a finite set. Number of arrangements, number of permutations. Binomial coefficients.
- General sieve formula and applications.
- Stirling numbers of the first and second kind.
- Partially ordered sets and Möbius function. Application to arithmetic.
Graph theory
- Notion of graph. Degree. Paths, chains, cycles. Connectedness.
- Eulerian and Hamiltonian graphs. Bipartite graphs.
- Isomorphisms, groups of automorphisms.
- Adjacency matrix, spectrum and properties.
- Trees, Cayley's formula. Covering trees, Kruskal's algorithm.
- Coloring, chromatic polynomial.
- Planarity, Euler's formula. Six-color theorem.
Necessary pre-requisites
The algebra courses of L1 and L2, in particular :
- HAX203X Arithmetic and enumeration
Recommended prerequisites: L2 math
Additional information
Hourly volumes:
CM : 18
TD : 18
TP: -
Land: -