# Algos

## Décompisition de graph en niveaux

1) Calculer \\( d^- \\)
2) incrémenter *layer*
3) pour chaques sommets, si \\( d^-(s) = 0 \\) alors définir sommets à layer
4) retirer sommets
5) recommencer jusqu'a ce qu'il n'y ai plus de sommets à explorer.

Il est possible d'incrémenter layer à chaque fois qu'un sommet est trouvé pour optenir une nouvelle
numérotation du graph qui respecterait l'ordre.

Cet algo ne fonctionnerais pas pour des graph cycliques.

## Exploration de graph

- Exploration en **Largeur** avec une **file** (BFS)
- Exploration en **Profondeur** avec une **pile** (DFS)

## Composantes connexes

On parle de composantes connexe comme un sous-graph tel qu'il existe une chaine entre chaques paire
de sommets.

Un sommet qui augmente les composants connexe si enlevé est appelé un **point d'articulation**

pour un graph non-dirigé: pour chaque sommets, faire une exploration et regrouper les sommets
visités en composants puis le supprimer pour continuer l'exploration.

Pour un graph dirigé, faire une detection de composantes fortements connexes.

## Détection d'un graph bi-partie

\\( G = (X_1, X_2, U) \\) sans arc entre deux sommets de \\( X_1 \\) ou deux sommets de \\( X_2 \\) 

- propriete 1: un graph bi partie est 2colorable
- propriete 2: ssi aucuns cycles impaires (nombres impaire d'arretes)

Pour la detection d'un graph bi-partie, il faut pour chaques sommets passer d'une couleur à l'autre.
si ça n'est pas possible, le graph n'est pas bi-partie.

