Skip to content
Snippets Groups Projects

Master

Merged gabriel.marinoja requested to merge gabriel.marinoja/algo-cours:master into master
1 file
+ 2
2
Compare changes
  • Side-by-side
  • Inline
+ 3
3
@@ -404,7 +404,7 @@ avec $k$ la longueur de la chaîne (le nombre d'arêtes du chemin).
@@ -404,7 +404,7 @@ avec $k$ la longueur de la chaîne (le nombre d'arêtes du chemin).
## Définition
## Définition
* Un **cycle** dans un graphe *non-orienté* est une chaîne de longueur $\leq 3$ telle que le 1er sommet de la chaîne est le même que le dernier, et dont les arêtes sont distinctes.
* Un **cycle** dans un graphe *non-orienté* est une chaîne de longueur $\geq 3$ telle que le 1er sommet de la chaîne est le même que le dernier, et dont les arêtes sont distinctes.
* Pour un graphe *orienté* on parle de **circuit**.
* Pour un graphe *orienté* on parle de **circuit**.
* Un graphe sans cycles est dit **acyclique**.
* Un graphe sans cycles est dit **acyclique**.
@@ -712,8 +712,8 @@ $$
@@ -712,8 +712,8 @@ $$
\mathcal{O}(|E|)
\mathcal{O}(|E|)
$$
$$
* Pour les graphes *non-orientés*: $\mathcal{O}2|E|$.
* Pour les graphes *non-orientés*: $\mathcal{O}(2|E|)$.
* Pour les graphes *orientés*: $\mathcal{O}|E|$.
* Pour les graphes *orientés*: $\mathcal{O}(|E|)$.
## Définition
## Définition
Loading