Graphes (UGA)

Notions plus avancées sur les graphes

• Compétences

  • 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 
  • Connaitre et démontrer la caractérisation des graphes bipartis avec les cycles impairs 
  • Donner un certificat qu'un graphe est biparti ou non 

  
  Vocabulaire : sous-graphe, sous-graphe engendré ou induit, graphe couvrant, complet, stable, clique, graphe biparti, graphe biparti complet

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

  ---

• Transparents graphes bipartis File
• ---

• Test notions plus avancées Quiz
• Test et certificat de bipartition Virtual programming lab