---
lang: fr
tags: theorie des graphs, S6, ING1
title: Theorie des graphs 8
date: 29/03/2019
---

# Theorie des graphs 8

==Chemin eulérien==: Visite toutes les arrêtes du graphe exactement 1 fois
==Cycle eulérien==: Chemi eulérien qui à son point de départ

Condition necessaire et suffidante pour avoir un cycle eulérien:
- Aucun sommet de degré impair
- Toutes les arêtes sont dans la même composante connexe (= le graphe privé de ses sommets isollés est connexe)

Condition necessaire et suffidante pour avoir un chemin eulérien:
- Il y a 0 ou 2 sommets de degré impair
- Toutes les arêtes dans la même composante connexe.

:::info
voir photo 29/03/2019
:::

==graph eulérien==: il existe un cycle eulérien dans le graph

:::info
Tout ce qui a été fait en cours:
https://www.lrde.epita.fr/~adl/ens/theg/theg-2019.txt
:::

1. Survol des propriété de graphe avec quelques def, propriétés (arbre couvrant, théorème de kizchoff, formule de cayley)
2. Notation mathématiques (G=(V,E, $\omega$), DFS, appliqué au trie topologique (Comme Make pour les dépendances), calcul de complexité en fonction de |V|, et |E|, 3 formules: { $\sum deg(x)=\theta(|E|)$ , Graph simple (entre 2 sommets il y a qu'une arête): |E| = O(|V|²), |V| = O(|E|)})
3. BFS calcul du plus court chemin:
- BFS graphe non pondéré: O(|V| + |E|)
- Djikstra (poids >= 0) : O(|E| + |V|log(V))
- Bellman ford (:warning: pas de cycle négatif)

:::info
voir photo 29/03/2019
:::