Fiche de révision : Introduction aux graphes et leurs propriétés

📋 Plan du Cours

1. Ponts de Königsberg et circuit eulérien
2. Définitions des graphes et arêtes
3. Types de graphes : planaire, simple, connexe
4. Degré des sommets et propriétés
5. Sous-graphes, sous-graphes induits et couvrants
6. Isomorphisme de graphes
7. Chaînes et cycles dans un graphe
8. Connexité et composantes connexes
9. Représentations non graphiques : matrices et listes

📖 1. Ponts de Königsberg et circuit eulérien

🔑 Notions clés & Définitions

• Euler : Personne à l’origine de la formalisation du problème des ponts de Königsberg en 1736.
• Circuit eulérien : Circuit qui parcourt chaque arête exactement une fois tout en revenant au point de départ.
• Graphe de Königsberg : Modélisation du problème où les ponts deviennent des arêtes et les zones terrestres deviennent des sommets.

📝 Points essentiels

• Le problème de 1736 demande de revenir au point de départ en empruntant chaque pont une seule fois.
• La modélisation transforme les ponts en arêtes et les zones en sommets.
• La question devient l’existence d’un circuit qui utilise chaque arête exactement une fois et revient au départ.
• Dans le cas présenté, la réponse à l’existence d’un tel circuit est non.

💡 Astuce mémo

Ponts → arêtes, zones → sommets, puis “une fois chaque arête” pour chercher un circuit.

📖 2. Définitions des graphes et arêtes

🔑 Notions clés & Définitions

• Graphe : Structure formée d’un ensemble de sommets et d’un ensemble d’arêtes reliant des sommets.
• Ensemble V des sommets : Ensemble des sommets du graphe, noté V, qui contient tous les sommets distincts.
• Ensemble E des arêtes : Ensemble des arêtes du graphe, noté E, qui contient toutes les liaisons entre sommets.
• Arête : Liaison entre deux sommets, définie comme une paire non ordonnée de sommets.
• Sommets adjacents : Relation entre deux sommets lorsqu’ils sont les extrémités d’une même arête.

📝 Points essentiels

• Un graphe est noté G=(V,E) avec V={v1,…,vn} et E={e1,…,em}.
• Une arête relie deux sommets et ses extrémités sont ces deux sommets.
• Si une arête relie a et b, alors a et b sont adjacents.
• Deux sommets sont dits incidents à une arête si cette arête a ces sommets pour extrémités.
• L’ordre des extrémités d’une arête n’est pas pris en compte car la paire est non ordonnée.

💡 Astuce mémo

G=(V,E) : V pour “Vertices”, E pour “Edges”, et une arête relie deux sommets sans ordre.

📖 3. Types de graphes : planaire, simple, connexe

🔑 Notions clés & Définitions

• Graphe planaire : Graphe admettant une représentation dans le plan où deux arêtes quelconques ne se coupent pas.
• Graphe simple : Graphe sans boucle sur un sommet et avec au plus une arête entre deux sommets.
• Multigraphe : Graphe autorisant des boucles et/ou plusieurs arêtes reliant la même paire de sommets.
• Graphe connexe : Graphe où tout sommet peut rejoindre tous les autres en suivant des arêtes.
• Composantes connexes : Sous-ensembles maximaux de sommets formant des sous-graphes connexes quand le graphe n’est pas connexe.

📝 Points essentiels

• Un graphe planaire peut être dessiné dans le plan sans croisements entre arêtes.
• Les arêtes d’une représentation planaire ne sont pas forcément rectilignes.
• Un graphe simple n’a pas de boucle et ne relie pas deux sommets par plusieurs arêtes.
• Les multigraphes sont ceux qui possèdent une boucle ou plusieurs arêtes entre deux sommets.
• Un graphe connexe permet, depuis n’importe quel sommet, d’atteindre tous les autres en suivant les arêtes.

💡 Astuce mémo

Planaire = pas de croisements ; Simple = pas de boucle ni de doublon ; Connexe = tout le monde est atteignable.

📖 4. Degré des sommets et propriétés

🔑 Notions clés & Définitions

• Degré d’un sommet : Nombre d’arêtes incidentes à un sommet donné, noté d(x).
• Degré d’un graphe : Valeur maximale des degrés de ses sommets.
• Graphe régulier : Graphe où tous les sommets ont le même degré.
• k-régulier : Graphe régulier dont le degré commun de tous les sommets vaut k.

📝 Points essentiels

• Le degré d’un sommet x, noté d(x), compte les arêtes incidentes à x.
• Le degré d’un graphe est le degré maximum parmi tous ses sommets.
• Un graphe régulier a tous ses sommets de même degré.
• Si le degré commun vaut k, le graphe est dit k-régulier.
• La somme des degrés des sommets d’un graphe vaut deux fois le nombre d’arêtes.

💡 Astuce mémo

Somme des degrés = 2×arêtes : chaque arête “compte” pour deux extrémités.

📖 5. Sous-graphes, sous-graphes induits et couvrants

🔑 Notions clés & Définitions

• Sous-graphe : Graphe H=(Y,F) obtenu en choisissant un sous-ensemble de sommets Y et un sous-ensemble d’arêtes F compatibles.
• Sous-graphe induit : Sous-graphe engendré par un ensemble Y de sommets, contenant toutes les arêtes dont les extrémités sont dans Y.
• Sous-graphe engendré : Autre nom du sous-graphe induit, défini par l’ensemble des arêtes ayant leurs extrémités dans Y.
• Sous-graphe couvrant : Sous-graphe dont l’ensemble des sommets Y est égal à l’ensemble des sommets X du graphe initial.
• Graphe partiel : Nom utilisé pour un sous-graphe couvrant, lorsque Y=X.

📝 Points essentiels

• Dans un sous-graphe H=(Y,F), on a Y ⊂ X et F ⊂ E.
• Toute arête de F doit avoir ses deux extrémités dans Y.
• Le sous-graphe induit H=(Y,F) prend F comme l’ensemble des arêtes de E dont les extrémités sont dans Y.
• Un sous-graphe couvrant vérifie Y=X.
• Dans ce cas, on dit aussi que H est un graphe partiel du graphe initial.

💡 Astuce mémo

Induit = “toutes les arêtes possibles entre Y” ; couvrant = “on garde tous les sommets” (Y=X).

📖 6. Isomorphisme de graphes

🔑 Notions clés & Définitions

• Isomorphisme de graphes : Correspondance bijective entre sommets qui préserve l’adjacence entre graphes.
• Fonction bijective f : Application qui associe chaque sommet de V1 à un sommet unique de V2 et réciproquement.
• Adjacence préservée : Propriété voulue par l’isomorphisme : deux sommets adjacents dans G1 restent adjacents dans G2 après application de f.

📝 Points essentiels

• Deux graphes G1=(V1,E1) et G2=(V2,E2) sont isomorphes s’il existe une fonction bijective f : V1 → V2.
• Pour tous a,b ∈ V1, a et b sont adjacents dans G1 si et seulement si f(a) et f(b) sont adjacents dans G2.
• L’isomorphisme ne change pas la structure d’adjacence, seulement le “nom” des sommets.
• La bijection garantit que chaque sommet de G2 correspond à exactement un sommet de G1.
• La condition “si et seulement si” impose une préservation dans les deux sens.

💡 Astuce mémo

Isomorphisme = même “plan d’adjacence”, juste renommage des sommets via une bijection.

📖 7. Chaînes et cycles dans un graphe

🔑 Notions clés & Définitions

• Chaîne : Suite alternant sommets et arêtes où chaque arête relie deux sommets consécutifs de la suite.
• Longueur d’une chaîne : Nombre k associé à une chaîne de la forme (x0,e1,x1,…,ek,xk).
• Chaîne simple : Chaîne où chaque arête est empruntée une seule fois.
• Chaîne élémentaire : Chaîne dont tous les sommets sont deux à deux distincts.
• Cycle : Chaîne fermée de longueur au moins 1, simple et fermée, revenant au sommet de départ.

📝 Points essentiels

• Une chaîne a la forme (x0,e1,x1,…,ek,xk) avec k ≥ 0.
• Pour i=0,…,k-1, les sommets xi et xi+1 sont les extrémités de l’arête e_{i+1}.
• La longueur d’une chaîne est l’entier k.
• Une chaîne est simple si chaque arête de la chaîne est utilisée une seule fois.
• Une chaîne est élémentaire si ses sommets xi sont tous deux à deux distincts, donc elle est simple.

💡 Astuce mémo

Chaîne = “marche” sommet→arête→sommet ; simple = pas de répétition d’arêtes ; élémentaire = pas de répétition de sommets.

📖 8. Connexité et composantes connexes

🔑 Notions clés & Définitions

• Graphe connexe : Graphe où il existe une chaîne entre chaque paire de sommets.
• Composante connexe : Sous-graphe connexe maximal obtenu quand on regroupe les sommets atteignables entre eux.
• Sous-graphe connexe maximal : Sous-graphe connexe qu’on ne peut pas agrandir en ajoutant de nouveaux sommets sans perdre la connexité.

📝 Points essentiels

• Un graphe est connexe si et seulement s’il existe une chaîne entre chaque paire de sommets.
• Si le graphe n’est pas connexe, il se décompose en composantes connexes.
• Une composante connexe est un sous-graphe connexe maximal.
• On ne peut pas ajouter de sommets à une composante connexe tout en conservant sa connexité.
• Un graphe ayant une seule composante connexe est simplement un graphe connexe.

💡 Astuce mémo

Connexe = “tout le monde se rejoint par une chaîne” ; composantes = “groupes maximaux atteignables”.

📖 9. Représentations non graphiques : matrices et listes

🔑 Notions clés & Définitions

• Matrice d’adjacences : Tableau représentant un graphe simple où l’entrée (i,j) indique si les sommets i et j sont adjacents.
• Matrice (n*m) : Tableau de n lignes et m colonnes utilisé pour définir une matrice d’adjacences.
• Entrée (i,j) : Intersection de la ligne i et de la colonne j dans une matrice.
• Liste d’adjacences : Représentation où, pour chaque sommet, on donne la liste des sommets adjacents.

📝 Points essentiels

• On peut représenter un graphe simple par une matrice d’adjacences.
• Dans une matrice d’adjacences, les lignes et colonnes représentent les sommets du graphe.
• Une valeur 1 à la position (i,j) signifie que le sommet i est adjacent au sommet j.
• Une liste d’adjacences donne, pour chaque sommet, les sommets auxquels il est adjacent.
• Les listes d’adjacences sont une autre manière de représenter un graphe simple sans dessin.

💡 Astuce mémo

Matrice = cases (i,j) ; Liste = “voisins” de chaque sommet.

📊 Tableaux de synthèse

Planaire vs non planaire

Simple vs multigraphe

⚠️ Pièges & confusions fréquents

1. Confondre graphe planaire et graphe simple : le premier concerne les croisements dans le dessin, le second concerne boucles et arêtes multiples.
2. Croire que “connexe” signifie “sans composantes connexes multiples” : un graphe non connexe se décompose en composantes connexes.
3. Mélanger sous-graphe induit et sous-graphe quelconque : l’induit contient toutes les arêtes entre sommets de Y.
4. Penser qu’une chaîne élémentaire peut répéter un sommet : par définition, tous les sommets xi sont deux à deux distincts.
5. Oublier que la matrice d’adjacences est donnée pour un graphe simple : la source ne traite pas explicitement les multigraphes ici.

✅ Checklist Examen

1. Savoir reformuler le problème des ponts de Königsberg en termes de circuit utilisant chaque arête exactement une fois et revenir au départ.
2. Définir un graphe G=(V,E) et préciser ce que sont sommets et arêtes.
3. Définir une arête comme paire non ordonnée de sommets et en déduire la notion d’adjacence/incidence.
4. Distinguer graphe planaire, graphe simple et multigraphe à partir de leurs critères de définition.
5. Définir un graphe connexe et expliquer ce que sont les composantes connexes en cas de non-connexité.
6. Définir le degré d’un sommet d(x) et le degré d’un graphe (maximum), puis reconnaître les graphes réguliers et k-réguliers.
7. Utiliser la propriété somme des degrés = 2×nombre d’arêtes et savoir que le nombre de sommets impairs est pair.
8. Définir sous-graphe, sous-graphe induit (engendré) et sous-graphe couvrant (Y=X).
9. Définir l’isomorphisme : existence d’une bijection f préservant l’adjacence dans les deux sens.
10. Définir chaîne, longueur, chaîne simple et chaîne élémentaire, puis relier élémentaire ⇒ simple.
11. Définir cycle (longueur ≥1, fermé, simple) et distinguer cycle pair/impair et graphe acyclique.
12. Définir connexité via l’existence d’une chaîne entre chaque paire de sommets et caractériser une composante connexe comme connexe maximal.
13. Décrire la matrice d’adjacences (rôle des lignes/colonnes, signification d’une entrée 1) et la liste d’adjacences (voisins de chaque sommet).