Formes de graphes

Donner un exemple de graphe (sous forme de dessin ou de liste d’arcs) pour chacun des cas suivants :

  • graphe réflexif ;
  • graphe asymétrique ;
  • graphe transitif ;
  • graphe complet et réflexif.

Pour chaque exemple, préciser les sommets et les arcs, et expliquer brièvement pourquoi il vérifie la propriété demandée.

Lecture matricielle et cliques

On considère les matrices suivantes.

Matrice d’incidence (sommet–arc)

$$ M = \begin{bmatrix} +1 & +1 & 0 & 0 & 0 \\ -1 & 0 & +1 & +1 & 0 \\ 0 & -1 & -1 & 0 & +1 \\ 0 & 0 & 0 & -1 & -1 \end{bmatrix} $$

  1. Interpréter cette matrice comme matrice d’incidence d’un graphe orienté :

    • associer un sommet à chaque ligne ;
    • associer un arc à chaque colonne ;
    • reconstruire le graphe correspondant.

  2. Donner un exemple de clique (sous-graphe complet) dans ce graphe, s’il en existe une.

Matrice d’adjacence

$$ M = \begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix} $$

  1. Interpréter cette matrice comme matrice d’adjacence d’un graphe (préciser s’il est orienté ou non).
  2. Représenter le graphe.
  3. Donner un exemple de clique dans ce graphe, s’il en existe une.

Problème du passeur

Un passeur doit faire traverser une rivière à un loup, une chèvre et un chou, dans une barque qui ne peut emporter que lui-même et un seul des trois à la fois.
Les contraintes sont les suivantes :

  • il est interdit de laisser le loup seul avec la chèvre sans le passeur ;
  • il est interdit de laisser la chèvre seule avec le chou sans le passeur.
  1. Modéliser ce problème par un graphe d’états :
    • chaque sommet représente une configuration (répartition des quatre personnages sur les deux rives) ;
    • chaque arc représente un passage autorisé du passeur (avec ou sans passager).
  2. Utiliser ce graphe pour trouver une solution (un chemin de l’état initial à l’état final).

Listes d’adjacence

On considère les graphes suivants, donnés par leurs listes d’adjacence.

Graphe G1

G1 :

  • 1 : 1, 3, 4
  • 2 : 2, 4, 1
  • 3 : 1, 3, 4
  • 4 : 1, 2, 4
  • : (aucun successeur)

Graphe G2

G2 :

  • 1 : 2, 3, 4
  • 2 : 1, 3, 4
  • 3 : 1, 2, 4
  • 4 : 1, 2, 3
  • : (aucun successeur)

Questions

  1. Tracer chacun des deux graphes.
  2. Donner la matrice d’adjacence de G1 puis de G2.
  3. Quelles sont les principales propriétés de ces graphes ?
  4. Calculer les demi-degrés sortants de chaque sommet pour G1 et pour G2.
  5. En supposant une représentation par liste d’adjacence compacte (tableaux LP/LS) :
    • détailler le calcul de $LP(3)$ pour G1 ;
    • détailler le calcul de $LP(4)$ pour G2.

Fermeture transitive et circuits

On donne ci-dessous des graphes par leurs matrices d’adjacence.

Pour chaque matrice :

  1. tracer le graphe associé ;
  2. décrire ses propriétés (connexité, présence de circuits, etc.) ;
  3. déterminer sa fermeture transitive (matrice d’atteignabilité) ;
  4. décrire les propriétés de cette fermeture transitive (graphe acyclique ou non, composantes, etc.) ;
  5. dire s’il existe des circuits dans le graphe de la fermeture transitive.

Matrice M1

$$ M_1 = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \end{bmatrix} $$

Matrice M2

$$ M_2 = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} $$

Matrice M3

$$ M_3 = \begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \end{bmatrix} $$

Graphes et composantes fortement connexes

On considère maintenant les matrices d’adjacence suivantes.

Matrice M1

$$ M_1 = \begin{bmatrix} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \end{bmatrix} $$

Matrice M2

$$ M_2 = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \end{bmatrix} $$

Pour chacune :

  1. tracer le graphe correspondant ;
  2. donner ses propriétés principales (fortement connexe ou non, présence de cycles, etc.) ;
  3. donner sa représentation sous forme de listes d’adjacence ;
  4. déterminer ses composantes fortement connexes maximales.

Connexitées et circuits

Considérer le graphe orienté suivant :

graph LR x1((x1)) x2((x2)) x3((x3)) x4((x4)) x5((x5)) x6((x6)) x7((x7)) x1 --> x3 x1 --> x2 x2 --> x5 x2 --> x6 x2 --> x7 x3 --> x7 x4 --> x3 x4 --> x5 x6 --> x5
  1. Déterminer ses composantes fortement connexes maximales.
  2. Lister tous les circuits / cycles que ce graphe contient.

Connexitées et circuits

Considérer le graphe suivant :

graph LR x1((x1)) x2((x2)) x3((x3)) x4((x4)) x5((x5)) x6((x6)) x7((x7)) x8((x8)) x9((x9)) x10((x10)) x11((x11)) x12((x12)) x13((x13)) x14((x14)) x15((x15)) x1 --> x2 x2 --> x3 x2 --> x4 x2 --> x5 x3 --> x1 x4 --> x3 x4 --> x5 x5 --> x1 x1 --> x6 x6 --> x7 x6 --> x11 x6 --> x10 x7 --> x5 x7 --> x8 x7 --> x9 x8 --> x5 x9 --> x8 x10 --> x11 x12 --> x10 x12 --> x11 x13 --> x11 x13 --> x9 x13 --> x15 x14 --> x13 x15 --> x14
  1. Déterminer les composantes fortement connexes de ce graphe.
  2. En partant successivement des sommets 7, 4 puis 15, déterminer les circuits / cycles accessibles depuis chacun de ces sommets.