Notions clés des graphes et parcours

📋 Plan du Cours

1. Vocabulaire des graphes
2. Dictionnaire d'adjacence
3. Matrice d'adjacence
4. Degré, BFS et DFS
5. Pièges fréquents
6. Questions types au bac

📖 1. Vocabulaire des graphes

🔑 Notions clés & Définitions

• Sommet : Un sommet est un point du graphe représentant une entité (par exemple une ville ou une personne).
• Arête : Une arête est un lien entre deux sommets dans un graphe non orienté, sans notion de direction.
• Arc : Un arc est un lien orienté entre deux sommets, avec une direction dans un graphe orienté.
• Chemin : Un chemin est une suite de sommets reliés successivement par des arêtes (ou arcs, selon le type de graphe).
• Cycle : Un cycle est un chemin qui revient au sommet de départ.

📝 Points essentiels

• Dans un graphe non orienté, le lien A—B implique aussi B—A.
• Dans un graphe orienté, A→B n’entraîne pas B→A.
• Un graphe connexe permet d’aller de n’importe quel sommet à n’importe quel autre.

💡 Astuce mémo

Arête = sans sens, Arc = avec flèche.

📖 2. Dictionnaire d'adjacence

🔑 Notions clés & Définitions

• Dictionnaire d’adjacence : Le dictionnaire d’adjacence représente un graphe en associant à chaque sommet la liste de ses voisins.
• Voisins : Les voisins d’un sommet sont les sommets directement reliés à lui par un lien du graphe.

📝 Points essentiels