# Théorie des Graphes

## Introduction
La théorie des graphes étudie les structures composées de sommets (ou nœuds) et d'arêtes reliant ces sommets. Ce document synthétise les notions essentielles et fournit des exemples pratiques.

## Concepts Fondamentaux
| Élément   | Description                                             |
|-----------|---------------------------------------------------------|
| **Sommet**| Un point ou nœud dans le graphe.                         |
| **Arête** | Connexion entre deux sommets.                           |
| **Chemin**| Succession d'arêtes reliant une séquence de sommets.     |
| **Cycle** | Chemin fermé sans répéter d'arêtes.                     |

## Types de Graphes
- **Graphes Orientés** : Les arêtes ont une direction (ex. A → B).
- **Graphes Non Orientés** : Les arêtes n'ont pas de direction particulière.
- **Graphes Pondérés** : Chaque arête est associée à une valeur ou un coût.

## Représentation des Graphes
### Matrice d'Adjacence
Représente la connexion entre les sommets par une matrice.
|         | A | B | C |
|---------|---|---|---|
| **A**   | 0 | 1 | 0 |
| **B**   | 1 | 0 | 1 |
| **C**   | 0 | 1 | 0 |

### Liste d'Adjacence
Représente pour chaque sommet la liste de ses voisins.
| Sommet | Voisins   |
|--------|-----------|
| A      | B         |
| B      | A, C      |
| C      | B         |

## Algorithmes de Parcours
- **DFS (Depth-First Search)** : Parcours en profondeur.
- **BFS (Breadth-First Search)** : Parcours en largeur.

#### Exemple de Parcours BFS (Tableau d'Itération)
Pour le graphe précédent, en partant de A :
| Étape | Sommets visités | File d'attente       |
|-------|-----------------|----------------------|
| 1     | A               | [B]                  |
| 2     | A, B            | [C]                  |
| 3     | A, B, C         | []                   |

## Exemples Pratiques
**Graphe Simple Non Orienté :**
| Arête  | Description               |
|--------|---------------------------|
| A - B  | Arc reliant A à B         |
| B - C  | Arc reliant B à C         |
| C - D  | Arc reliant C à D         |
| D - A  | Arc reliant D à A (cycle)  |