17_10_2023

Définitions

Un graphe, ensemble de sommets reliés par des arrêtes

Notations

$G=(V,E)$ tq:

• $G$ le graphe
• $V$ (vertex) l’ensemble des sommets de taille $n$
• $E$ (edge), l’ensemble de d’arrêtes constitué de paires d’elt de $V$ de taille $m$

ex : $V=\{a,b,c,d\}$ $E=\{ab,bc,bd\}$

Un chemin correspond aux arrêtes continues, avec une longueur nommée $P_n$ (P pour path, n car on parle des sommets)

Les types de graphe

Un graphe complet est un graphe dans lequel toutes les arrêtes possibles sont présentes noté $K_n$ so

Un graphe sans arrêtes est un stable $I_n$ (donc $E=\varnothing$)

Les graphes bipartis sont des graphes dans lequel on peut partitionner les sommets en 2 groupes tel que les arrêtes ne connectent jamais 2 arêtes du même groupe, il peut être complet. On le note $K_{a,b}$, tel que $a$ et $b$ la taille des partitions

Important

Sauf si indiqué la théorie des graphe interdit les boucles et arrête multiples

En code

Avec des matrices

Il est possible de représenter un graphe avec une matrice ou les colonnes et lignes représentent les sommet et les chiffres le nombre d’arrêtes entre 2 sommets

Dans le cas d’un graphe non dirigé et sans boucle la diagonale est nulle et est donc symétrique, ex: $\left[\begin{array}{c}0,1,1\\ 1,0,0\\ 1,0,0\end{array}\right]$

Ici on a $V=\{a,b,c\};E=\{ab,ca\}$