Graphes (UGA L3 MI)

Compétences

1. Modélisation à l'aide de graphe

• Reconnaitre un problème pratique qui peut être modélisé à l'aide de graphe
• Modéliser un problème pratique à l'aide d'un graphe

2. Notions de base sur les graphes

• Identifier et décrire un isomorphisme 
• Reconnaitre les principales variantes aux graphes simples : boucle, graphe orienté, mutigraphe, étiquetage 
• Ecrire des preuves simples sur des propriétés des degrés 

3. Représentation des graphes

• Présenter un graphe dans différentes représentation : graphique, matrice d'adjacence, matrice d'incidence, liste d'adjacence 
• Décrire un algorithme pour passer d'une représentation machine (matrice ou liste) à l'autre 
• Choisir la représentation la plus adaptée (coût temps et espace) à un problème 

Vocabulaire :  graphe, sommets, arêtes, ordre, complémentaire, auto-complémentaire, extrémité d'une arête, arête incidente à un sommet, sommets voisins, sommet isolé, voisinage d'un sommet, degré d'un sommet, graphe $k$-régulier, graphe complet, arc

Notations : $G, V, E, n, m, d(v), N(v), K_n$