Graphe - Notions générales

Exerice 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

Impossible car $\sum deg(u) \neq 2 m$

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,...,u_n\}$, prenons $u_i=u$. Les arêtes incidentes à $u$ candidates sont $(u_1,u_i),...,(u_n,u_i)$. On a donc $n-1$ arêtes possibles incidentes à $u$. Donc $deg(u)\leq n-1$.

Supposons que $deg(u_j)=0$ avec $u_j \neq u_i$ donc l'arête $(u_j,u_i)$ n'existe pas donc $deg(u_i) \leq n-2$ pour tout $u_i \neq u_j$.

Distinguons deux cas, soit il existe un sommet de degré 0 alors les degrés possibles sont $0,1,2,...,n-2$ soit $n-1$ possibilités de degrés or on a $n$ sommets. D'après le principe des tiroirs et des chaussettes il existe une valeur de degrés pour laquelle il y a 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 dessin du graphe de Petersen répond à toutes les questions

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 ?

1. Soit $V=\{1,...,n\}$ les arrètes possibles sont de la forme $(i,j)$ avec $i \in \{1,...,n\}$ et $j \in \{1,...,n\}$ arrètes potentielles et donc $2^{n^2}$ graphes simples orientés à $n$ sommets.
2. Soit $V=\{1,...,n\}$, les arrètes possibles sont de la forme $(i,j)$ avec $i \in \{1,...,n\}$ et $j \in \{1,...,n\}$ avec $i \leq j$. Ainsi $\#arrètes potentielles = n + (n-1) + ... + 1 = \dfrac{n(n+1)}{2}$ et donc $2^{\frac{n(n+1)}{2}}$ graphes simples non orientés à $n$ sommets

Exercice 9 : On considère ici des graphes simples orientés ou non. Ecrire un algorithme décidant si deux graphes fournis en entrée sont isomorphes ou non. Evaluer 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 si 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(E_1,V_1):graphe,g_2(E_2,V_2):graphe)
    n=card(V_1)
    si n != card(V_2)
        retourner Faux
    r = initialisation
    tant que r != 0
        c=0
            pour i allant de 1 à card(E_1)
                si Appartient((r(E[i][o]),r(E[i][1]),E_2))
                    c++
            si c=card(E_2)
                retourner Vrai
            r=renommage_suivant(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)$.