• ECTS

    4 crédits

  • Composante

    Faculté des Sciences

  • Volume horaire

    36h

Description

Dans une première partie, approfondir les notion de base du dénombrement vues en L1 et L2.

Dans une seconde partie, introduire l’étude combinatoire des graphes.

Lire plus

Objectifs

Cette UE abordera les points suivants :

Dénombrement

    - Notion de cardinal. Nombre d’applications entre deux ensembles finis, nombre de parties d’un ensemble fini. Nombre d’arrangements, nombre de permutations. Coefficients binomiaux.

    - Formule du crible générale et applications.

    - Nombres de Stirling de première et seconde espèce.

    - Ensembles partiellement ordonnés et fonction de Möbius. Application à l’arithmétique.

Théorie des graphes

    - Notion de graphe. Degré. Chemins, chaînes, cycles. Connexité.

    - Graphes eulériens et hamiltoniens. Graphes bipartites.

    - Isomorphismes, groupes d’automorphismes.

    - Matrice d’adjacence, spectre et propriétés.

    - Arbres, formule de Cayley. Arbres couvrants, algorithme de Kruskal.

    - Coloriage, polynôme chromatique.

    - Planarité, formule d’Euler. Théorème des six couleurs.

Lire plus

Pré-requis nécessaires

Les UE d’algèbre de L1 et L2, en particulier :

- HAX203X Arithmétique et dénombrement

 

Pré-requis recommandés : L2 maths

Lire plus

Informations complémentaires

Volumes horaires :

            CM : 18

            TD : 18

            TP : -

            Terrain : -

Lire plus