Dans le cours, un graphe est défini comme un triple :

• N : un ensemble fini de nœuds ;
• R : un ensemble fini d'arêtes ;
• I : une relation d'incidence I ⊂ N × R, telle que toute arête est incidente à 1 ou 2 nœuds.

Dans cet exercice, ces trois ensembles sont représentés par trois ensembles Python (set) :

• N : l'ensemble des nœuds ;
• R : l'ensemble des arêtes ;
• I : l'ensemble des couples (n, r) qui signifient « le nœud n est incident à l'arête r ».

Le triple (N, R, I) représente un graphe si et seulement si :

1. chaque élément de I est un couple (n, r) avec n dans N et r dans R ;
2. chaque arête de R apparaît dans un ou deux couples de I (une arête incidente à un seul nœud est une boucle).

Remarques :

• deux arêtes différentes peuvent être incidentes aux deux mêmes nœuds (arêtes parallèles) ;
• un nœud peut n'être incident à aucune arête ;
• les ensembles peuvent être vides.

Exemple d'un triple qui est un graphe ("c" est une boucle sur le nœud 3) :

N = {1, 2, 3}
R = {"a", "b", "c"}
I = {(1, "a"), (2, "a"), (2, "b"), (3, "b"), (3, "c")}

Exemple d'un triple qui n'est pas un graphe (l'arête "b" n'est incidente à aucun nœud) :

N = {1, 2, 3}
R = {"a", "b"}
I = {(1, "a"), (2, "a")}