1. Sous-graphes, cliques et stables
    2. Graphes bipartis
    3. Coloration : bornes et algorithme glouton
    4. Graphes d'intervalles

     

    Compétences

    1. Sous-graphes, cliques et stables

    • Reconnaitre un sous-graphe, un sous-graphe engendré (ou induit), un graphe couvrant d'un graphe
    • Calculer  \omega(G) et \alpha(G)  à la main sur de petits graphes 

    2. Graphes bipartis

    • Connaitre et démontrer la caractérisation des graphes bipartis avec les cycles impairs 
    • Donner un certificat qu'un graphe est biparti ou non 

    3. Bornes et algorithmes 

    • Connaitre les preuve sur les bornes de coloration avec la clique max et le degré max
    • Décrire l'algorithme glouton de coloration 
    • Utiliser l'algorithme glouton pour prouver la borne sur le degré max 
    • Modéliser des problèmes pratiques commme des problèmes de coloration de graphe 

    4. Graphes d'intervalles 

    • Construire le graphe d'intersection associé à une famille d'ensembles 
    • Utiliser l'algorithme glouton pour résoudre optimalement la coloration de graphes d'intervalles 
    • Montrer l'optimalité de l'algorithme 

    Coloring book (spikedmath.com)

    Vocabulaire : sous-graphe, sous-graphe engendré ou induit, graphe couvrant, complet, stable, clique, graphe biparti, graphe biparti complet, k-coloration, nombre chromatique, graphe d'intersection, graphe d'intervalles

    Notation : G[W] , \omega(G) , \alpha(G) , K_{a,b} , \chi(G),   \Delta(G)