TD 1 : notions générales

Exercice 1 : Dessiner si c'est possible un graphe qui a 3 sommets de degré 3 et 4 sommets de degré 2. Le cas échéant, expliquer pourquoi ce n'est pas possible.

C'est impossible : la somme des degrés vaut $3 \times 3 + 4 \times 2 = 17$, qui est impaire, alors que dans tout graphe $\sum_{u} deg(u) = 2m$ (lemme des poignées de main).

Exercice 2 : Soit $G$ un graphe simple sans boucle non orienté ayant $n$ sommets. Montrer que le degré de tout sommet $s$ de $G$ est inférieur ou égal à $n-1$, et que $G$ ne peut contenir à la fois un sommet de degré $0$ et un sommet de degré $n-1$, en déduire que $G$ admet au moins deux sommets de même degré.

Soit $V=\{u_1,\ldots,u_n\}$, prenons $u_i=u$. Les arêtes incidentes à $u$ candidates sont les $(u_j,u_i)$ avec $j \neq i$ (pas de boucle). On a donc $n-1$ arêtes possibles incidentes à $u$. Donc $deg(u)\leq n-1$.

Supposons que $deg(u_j)=0$ : pour tout $u_i \neq u_j$, l'arête $(u_j,u_i)$ n'existe pas, donc $deg(u_i) \leq n-2$. Un sommet de degré $0$ et un sommet de degré $n-1$ ne peuvent donc pas coexister.

Distinguons deux cas. S'il existe un sommet de degré 0, les degrés possibles sont $0,1,2,\ldots,n-2$, soit $n-1$ valeurs possibles. Sinon, les degrés possibles sont $1,2,\ldots,n-1$, soit encore $n-1$ valeurs. Dans les deux cas, on a $n$ sommets pour $n-1$ valeurs : d'après le principe des tiroirs, il existe une valeur de degré prise par au moins 2 sommets.

Exercice 3 : Soit $X=\{0,1,2,3,4\}$. Le graphe de Petersen est le graphe non orienté défini de la façon suivante : ses sommets sont les paires d'éléments de $X$, et deux sommets sont joints par une arête si et seulement si ce sont deux paires disjointes d'éléments de $X$. Déterminer le nombre de sommets du graphe, le degré de chaque sommet, le nombre d'arêtes du graphe, dessiner le graphe.

Le graphe possède $\binom{5}{2} = 10$ sommets. Une paire est disjointe de $\binom{3}{2} = 3$ paires : chaque sommet est de degré 3. Le nombre d'arêtes vaut donc $\frac{10 \times 3}{2} = 15$.

Exercice 7 : Nous considérons ici les graphes ayant pour ensemble de sommets des intervalles d'entiers de la forme $[1,n]$ avec $n \geq 1$.

1. Quel est le nombre de graphes simples orientés ayant $n$ sommets ?
2. Quel est le nombre de graphes simples non orientés ayant $n$ sommets ?

Ici, un graphe simple peut contenir des boucles mais pas d'arcs multiples.

1. Soit $V=\{1,\ldots,n\}$ : les arcs possibles sont de la forme $(i,j)$ avec $i \in \{1,\ldots,n\}$ et $j \in \{1,\ldots,n\}$, soit $n^2$ arcs potentiels, et donc $2^{n^2}$ graphes simples orientés à $n$ sommets ($2^{n(n-1)}$ si l'on interdit les boucles).
2. Soit $V=\{1,\ldots,n\}$ : les arêtes possibles sont de la forme $\{i,j\}$ avec $i, j \in \{1,\ldots,n\}$ et $i \leq j$. Ainsi le nombre d'arêtes potentielles vaut $n + (n-1) + \ldots + 1 = \dfrac{n(n+1)}{2}$, et donc il y a $2^{\frac{n(n+1)}{2}}$ graphes simples non orientés à $n$ sommets ($2^{\frac{n(n-1)}{2}}$ sans boucle).

Exercice 9 : On considère ici des graphes simples orientés ou non. Écrire un algorithme décidant si deux graphes fournis en entrée sont isomorphes ou non. Évaluer sa complexité. Vous utiliserez un type renommage contenant notamment les primitives suivantes dont on supposera la complexité en temps constante :

• fonction renommageSuivant(r:renommage):booléen qui retourne le booléen vrai s'il existe une bijection suivante et retourne celle-ci par effet de bord sur $r$ ;
• procédure initialisation(n:entier) qui retourne la première bijection.

fonction isomorphisme(g_1(V_1,E_1):graphe, g_2(V_2,E_2):graphe)
    n = card(V_1)
    si n != card(V_2) ou card(E_1) != card(E_2)
        retourner Faux
    r = initialisation(n)
    répéter
        c = 0
        pour i allant de 1 à card(E_1)
            si Appartient((r(E_1[i][0]), r(E_1[i][1])), E_2)
                c++
        si c == card(E_2)
            retourner Vrai
    tant que renommageSuivant(r)
    retourner Faux

fonction Appartient(element e, ensemble E)
    pour i allant de 1 à |E|
        si e==E[i]
            retourner Vrai
    retourner Faux

La complexité de cet algorithme est $O(n! \, m^2)$ : $n!$ bijections, et pour chacune $m$ arêtes dont l'appartenance à $E_2$ est testée en $O(m)$.