# Théorie des graphes/Propriétés
## Arêtes et arcs

* Une arête/un arc a deux extrémités. On dit qu’il est incident à ces extrémités
* Un arc a un nœud d’origine (ou départ) et un nœud d'arrivée. On dit qu’il est issu de son origine et qu’il aboutit à son arrivée
** Vis-à-vis du nœud d’origine, un arc est sortant
** Vis-à-vis du nœud d’arrivée, un arc est entrant
* On parle d'arêtes/arcs multiples lorsque plusieurs arêtes/arcs portent entre les mêmes sommets/nœuds
* Une boucle est une arête/un arc dont les deux extrémités sont identiques
* Une séquence d’arêtes/arcs consécutifs est appelée une chaîne / un chemin ; on note $<u,u_{1},...,u_{n},v>$ le chemin/chaîne de u à v passant par $u_{1},...,u_{n}$
On note $<a_{1},a_{2},...,a_{n}>$ le chemin/chaîne utilisant les arêtes/arcs consécutifs $<a_{1},a_{2},...,a_{n}>$

## Sommets et nœuds

* Le degré d'un sommet/nœud est le nombre d'arêtes/arcs qui lui sont incidents. Le degré entrant d'un nœud est le nombre d'arcs entrants, son degré sortant le nombre d'arcs sortants. Un sommet/nœud de degré nul est dit isolé.
* Un sommet/nœud est adjacent aux sommets/nœuds auxquels il est relié par une arête/un arc. L'ensemble des sommets/nœuds adjacents à un sommet/nœud u est appelé le voisinage de u.
* Le nœud u est un prédécesseur du nœud v s'il existe un arc (u,v). Le nœud u est un successeur du nœud v s’il existe un arc (v,u)
* Un sommet/nœud u est accessible depuis un sommet/nœud v si et seulement s'il existe un chemin de v à u. Un sommet/nœud u est coaccessible depuis un sommet/nœud v si et seulement s'il existe un chemin de u à v
* La distance δ(u,v) entre deux sommets/nœuds u et v est la longueur du plus petit chemin/chaîne depuis u à v
Note : δ(u,v)=∞ si aucun chemin/chaîne ne relie u à v.

## Chaînes et chemins

* La longueur d'un chemin/chaîne c (notée $|c|$) est le nombre d'arêtes/arcs qui le constitue
* Un chemin/chaîne $c_{1}=<a_{1},...,a_{n}>$ est un sous-chemin/chaîne du chemin/chaîne $c_{2}$ si et seulement si $c_{2}=<a_{1'},...,a_{1},...,a_{n},...,a_{n'}>$
* Un circuit/cycle est un chemin/chaîne $<u_{1},...,u_{n}>$ tel que $u_{1}=u_{n}$
* Un chemin/chaîne $<a_{1},...,a_{n}>$ est simple si et seulement si $a_{i}$ ≠ $a_{j}$ ∀ i ≠ j
* Un chemin/chaîne $<u_{1},...,u_{n}>$ est élémentaire si et seulement si $u_{i}$ ≠ $u_{j}$ ∀ i ≠ j
* Un chemin/chaîne eulérien est un chemin/chaîne simple passant par toutes les arcs/arêtes
* Un chemin/chaîne hamiltonien est un chemin/chaîne élémentaire passant par tous les nœuds/sommets

## Graphes
### Généralités

* Un graphe G=(S,A) est complet si et seulement si ∀u≠v∈S (u,v)∈A (ou u→v ∈A)
Note : on note $K_{i}$ le graphe complet à i sommets
* Un graphe est simple s'il ne contient ni boucles ni arêtes/arcs multiples
* Un graphe est eulérien/hamiltonien s’il contient un circuit/chaîne eulérien/hamiltonien
* Un graphe est pondéré si on lui associe une fonction w qui à chaque sommet/nœud et/ou arête/arc associe un réel
* G=(S,A) est biparti si et seulement s'il existe une partition S1∪S2 de S tel que ∀(u,v)∈A, u∈S1⇔v∈S2
Un graphe G=(S,A) est un sous-graphe du graphe G'=(S', A') si et seulement si S⊆S’ et A⊆A’
Note : G est le sous-graphe de G’ engendré par S si et seulement si ∀(u,v)∈A’\A, u∈S⇒v∉S
La densité d'un graphe G=(S, A) est le rapport $|A|/|S|^{2}$
* Un graphe peu dense contient peu d’arêtes/arcs
* Un graphe dense contient beaucoup d’arêtes/arcs

### Connexité

Un graphe non orienté G=(S, A) est connexe si et seulement si ∀u,v∈S il existe une chaîne reliant u à v
* Les composantes connexes d’un graphe G sont les sous-graphes maximaux connexes de G
* Un graphe est k-connexe (1 ≤ k ≤ $|S|-1$) si le retrait de k-1 sommets quelconques préserve sa connexité
Un graphe orienté G=(N,A) est fortement connexe si et seulement si ∀u,v∈S il existe un chemin de u à v
* Les composantes fortement connexes d'un graphe G sont les sous-graphes maximaux fortement connexes de G
* Le graphe réduit de G est le graphe G où chaque composantes fortement connexes a été condensée en un seul sommet
| Fondements | Parcours |