Définitions des graphes

1. Graphe (Non orienté)

Un graphe est constitué de deux ensembles :

• Un ensemble de sommets (ou nœuds, ou vertices), noté \( S \).

• Un ensemble de d'arêtes \( A \), où chaque arête est une paire \( \{x, y\} \) avec \( x \in S \) et \( y \in S \).

Les arêtes sont des connexions entre deux sommets. Un graphe est généralement noté \( G = (S, A) \) ou \( G(V, E) \), où :

• \( S \) représente l'ensemble des sommets.

• \( A \) (ou \( E \)) représente l'ensemble des arêtes.

Adjacence

On dit que deux sommets \( x \) et \( y \) sont adjacents ou voisins s'ils sont reliés par une arête.

Degré d'un sommet

Le degré d'un sommet \( s \in S \), noté \( d(s) \), est le nombre de voisins de \( s \), c'est-à-dire le nombre d'arêtes incidentes à ce sommet.

Chaîne

Un chaîne d'un sommet \( s_0 \) à un sommet \( s_n \) est une séquence de sommets où chaque paire consécutive de sommets est reliée par une arête.

Le chemin peut être défini comme \( s_0, s_1, \ldots, s_n \), où chaque \( s_i \) est adjacent à \( s_{i+1} \).

Graphe connexe

Un graphe non orienté \( G(V, E) \) est dit connexe si quels que soient le couple sommets \( \{x, y\} \), il existe une chaîne reliant \( x \) à \( y \)

---

2. Graphe orienté

Un graphe orienté est similaire à un graphe non orienté, mais dans ce cas, les arêtes sont orientées.

Cela signifie qu'une arête est représentée par un couple ordonné de sommets \( (x, y) \) qui sera appelé arc, plutôt qu'une paire non ordonnée \( \{x, y\} \).

Dans un graphe orienté, une arc \( (x, y) \) va du sommet \( x \) vers le sommet \( y \).

Il est donc possible que \( (x, y) \) soit une arc présent, mais que \( (y, x) \) ne le soit pas. Cela introduit une direction dans les relations entre les sommets.

Dans le cas d'un graphe orienté, la notion de degré d'un sommet x se décline en degré entrant et degré sortant.

La connexité est déclinée en connexité faible, et connexité forte : pour tout couple \( (x, y) \) il existe un chemin de \( x \) à \( y \) ce qui implique que ela soit aussi le cas de \( y \) à \( x \).

---

3. Circuits/ cycles

Dans un graphe orienté, on appelle circuit une suite d'arcs consécutifs (chemin) dont les deux sommets extrémités sont identiques.

La notion correspondante dans les graphes non orientés est celle de cycle. On parle parfois de cycle orienté.

Un circuit constitué d'un seul arc est une boucle.

4. Exemples d'implémentation en Python

4.1. Implémentation par matrice d'adjacence

La matrice d'adjacence est une représentation du graphe sous forme de matrice carrée.

Chaque sommet est associé à un entier de \(0 \) à \( n-1 \). Par exemple à l'aide d'une liste Python.

Et chaque élément \( M[i][j] \) indique si un sommet \( i \) est adjacent à un sommet \( j \). Si \( M[i][j] = 1 \), cela signifie qu'il y a une arête entre les sommets \( i \) et \( j \), sinon il n'y en a pas.

Voici un exemple d'implémentation en Python :

sommets = ['a', 'b', 'c', 'd', 'e']

graphe =    [[0,1,1,0,1], # a est voisin de b,c et e
            [1,0,1,0,0], # b est voisin de a et c
            [1,1,0,1,1], # c est voisin de a,b,d et e
            [0,0,1,0,0], # d est voisin de c
            [1,0,1,0,0]] # e est voisin de a et c

Degré maximal d'un graphe

Ecrire un code d'une fonction degre qui prend une entré un graphe et un sommet et renvoie le degré de ce sommet

def degre(g: list, s: int)-> int:
    ...
    # code à compléter
    return deg

Ecrire ensuite un fonction degre_max qui prend en entrée un graphe et renvoie la valeurs maximal du degré de tous ses sommets.

def degre_max(g: list)-> int:
    ...

4.2. Implémentation par liste d'adjacence

Une deuxième façon de représenter le graphe est la liste d'adjacence.

Il est possible d'associer dans un dictionnaire, chaque sommet (clé) à la liste de ses voisins (valeur).

Le graphe de notre exemple sera représenté par :

graphe = {
    'a': ['b', 'c', 'e'],  # a est voisin de b, c et e
    'b': ['a', 'c'],       # b est voisin de a et c
    'c': ['a', 'b', 'd', 'e'],  # c est voisin de a, b, d et e
    'd': ['c'],            # d est voisin de c
    'e': ['a', 'c']        # e est voisin de a et c
}