• ECTS

    4 credits

  • Component

    Faculty of Science

Description

In the first part, the basic concepts of enumeration seen in L1 and L2 are studied in greater depth.

The second part introduces the combinatorial study of graphs.

Read more

Objectives

This UE will cover the following points:

Count

    - 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 screen 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. Degrees. Paths, chains, cycles. Connectedness.

    - Eulerian and Hamiltonian graphs. Bipartite graphs.

    - Isomorphisms, automorphism groups.

    - Adjacency matrix, spectrum and properties.

    - Trees, Cayley formula. Covering trees, Kruskal algorithm.

    - Coloring, chromatic polynomial.

    - Planarity, Euler's formula. Six-color theorem.

Read more

Necessary prerequisites

L1 and L2 algebra courses, in particular :

- HAX203X Arithmetic and enumeration

 

Recommended prerequisites: L2 maths

Read more

Further information

Hourly volumes :

            CM: 18

            TD : 18

            TP: -

            Land: -

Read more