Aller au contenu

Feuille d'exercices sur les Graphes

Graphes non-orientés

Exercice 1

On considère le graphe ci-contre :

  1. Quel est l'ordre du graphe ?

  2. Ce graphe est-il simple ?

  3. Compléter le tableau ci-dessous :

Sommet A B C D E
Degré
  1. Combien vaut la somme des degrés des sommets de ce graphe ?

En déduire le nombre d'arêtes du graphe.

  1. Les sommets B et D sont-ils adjacents ?

  2. Dessiner le sous-graphe ADC.

  3. Quel est son ordre ?

  4. Combien possède-t-il d'arêtes ?

Exercice 2

On considère le graphe ci-contre :

  1. Quel est l'ordre du graphe ?

  2. Ce graphe est-il simple ?

  3. Ce graphe est-il complet ?

  4. Déterminer un sous-graphe complet d'ordre 4.

  5. Déterminer un sous-graphe complet d'ordre 3.

Quel est le degré de chacun de ses sommets ?

Exercice 3 : Fête d'anniversaire

Alexandre aimerait inviter 5 amis (notés A, B, C, D et E) pour son anniversaire, mais certains ne s'entendent pas.

Tableau des relations :

  • Amis : A, B, C, D, E
  • Ne s'entendent pas :
  • A ↔ ?
  • B ↔ D, E
  • C ↔ D
  • D ↔ C, E
  • E ↔ B, D

Remarque : Le document liste les incompatibilités sous la forme « D C D E B A B E B D ».

Question :

Combien Alexandre peut-il inviter d'amis à son anniversaire pour que la fête soit réussie ?

Exercice 4 : Rencontres sportives

Lors de rencontres sportives, il y a 7 équipes de basketball représentant 7 établissements différents.

Les professeurs d'EPS aimeraient organiser des rencontres de telle sorte que chaque équipe en rencontre trois autres.

Question :

Est-ce possible ?

Exercice 5 : Graphe connexe ?

On considère le graphe ci-contre :

  1. Quel est l'ordre du graphe ?

  2. Ce graphe est-il simple ?

  3. Ce graphe est-il connexe ?

  4. Quelle est la distance entre B et C ?

  5. Quel est le diamètre du graphe ?

  6. On considère la chaîne : B − A − C − a1 − E − A − B

a) Déterminer sa longueur.

b) Est-ce une chaîne fermée ?

c) Est-ce un cycle ?

Exercice 6 : Sommets de même degré

  1. a) Essayer de construire un graphe simple (non orienté) ayant au moins deux sommets et tel que tous les sommets ont des degrés distincts ?

b) Que peut-on conjecturer ?

c) En faisant un raisonnement par l'absurde, démontrer la conjecture précédente.

  1. Montrer que dans un groupe de personnes, il y a toujours deux personnes ayant le même nombre d'amis présents.

Exercice 7 : Parcourir un graphe non-orienté

Peut-on dessiner en ne passant qu'une seule fois par chaque arête les graphes ci-dessous ?

Exercice 8 : Tracer une figure sans lever le crayon

Est-il possible de tracer les graphes suivants sans lever le crayon et sans passer deux fois sur le même trait ?

  • fig1 fig2

  • fig3 fig4

Exercice 9 : Extrémités d'une chaîne eulérienne

Dans un parc, il y a cinq bancs reliés entre eux par des allées.

On modélise les bancs par les sommets A, B, C, D, E et les allées par les arêtes du graphe ci-dessous.

  1. Est-il possible de parcourir toutes les allées de ce parc sans passer deux fois par la même allée ?

  2. Amine est assis sur le banc A. Peut-il parcourir toutes les allées de ce parc sans passer deux fois par la même allée ?

Exercice 10 : Problème des sept ponts de Königsberg

La ville de Königsberg (aujourd'hui Kaliningrad) est construite autour de deux îles situées sur le Pregel et reliées entre elles par un pont.

Six autres ponts relient les rives de la rivière à l'une ou l'autre des deux îles, comme représenté sur le plan ci-dessus.

Le problème consiste à déterminer s'il existe ou non une promenade dans les rues de Königsberg permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu'on ne peut traverser le Pregel qu'en passant sur les ponts.

  1. Dessiner un graphe représentant la situation.

  2. Est-il possible de se promener dans les rues de Königsberg en passant une et une seule fois par chaque pont ?

Exercice 11 : Traverser une seule fois la frontière

Un voyageur visite ces six pays d'Asie.

Il aimerait traverser une fois et une seule chaque frontière.

  1. Dessiner un graphe représentant la situation.

  2. Est-il possible de traverser une fois et une seule chaque frontière ?

Exercice 12 : Couper 16 segments

Est-il possible de tracer une courbe, sans lever le crayon, qui coupe chacun des 16 segments de la figure suivante ?

CHINE

Pregolia
Kaliningrad
Problème des sept ponts de Königsberg

Exercice 13 : Signature de Mahomet et cycle eulérien

La signature de Mahomet est formée de deux croissants opposés comme sur le dessin ci-dessous.

On raconte qu'il la traçait sans lever la pointe de son cimeterre.

Question :

Est-ce possible ? Si oui, proposer une manière de faire.

Exercice 14 : Ajouter un sommet et des arêtes pour trouver un cycle eulérien

Soit G un graphe connexe ne possédant pas de cycle eulérien.

Question :

Est-il toujours possible, en rajoutant un sommet et quelques arêtes, de transformer G en un graphe possédant un cycle eulérien ?

Graphe orienté

Exercice 15

On considère le graphe orienté ci-dessous :

  1. Quel est l'ordre du graphe ?
  2. Quel est le degré entrant du sommet C et le degré sortant du sommet A ?
  3. Déterminer une chaîne de longueur 3 reliant les sommets A et B.

Exercice 16 : Relation « être diviseur de »

Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation « être diviseur de ».

Matrice d'adjacence

Exercice 17

Dans chacun des cas, déterminer la matrice d'adjacence associée aux graphes donnés (en considérant les sommets dans l'ordre alphabétique) :

  1. (premier cas)

  2. (deuxième cas)

  3. (troisième cas)

Exercice 18

On considère la matrice d'adjacence d'un graphe G :

\[M = \begin{pmatrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ \end{pmatrix}\]

  1. Déterminer l'ordre du graphe.

  2. Le graphe G est-il orienté ?

  3. Dessiner un graphe possible.

Exercice 19

  1. Déterminer les sommets A, B, C, D, E et F du graphe ci-dessous, sachant que la matrice d'adjacence associée, en prenant les sommets par ordre alphabétique, est :
\[M = \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ \end{pmatrix}\]

  1. Déterminer à l'aide de la calculatrice les matrices \(M^3\) et \(M^5\).

  2. En déduire le nombre de chaînes de longueur 3 reliant A à C et le nombre de chaînes de longueur 5 reliant C à E.

Exercice 20 : Nombres élégants

Un nombre est dit élégant si la différence entre deux chiffres consécutifs est d'au plus 1.

Le but du problème est de déterminer le nombre de nombres élégants à 8 chiffres, dont les chiffres sont tous compris entre 0 et 4 (inclus) :

  1. On construit un nombre élégant en concaténant les chiffres un à un. Compléter les pointillés ci-dessous :

  2. 0 est suivi de ...

  3. 1 est suivi de ...
  4. 2 est suivi de ...
  5. 3 est suivi de ...

  6. 4 est suivi de ...

  7. Construire le graphe dont les sommets sont les chiffres de 0 à 4, et tel qu'il y ait une arête entre deux sommets si la différence entre eux vaut au plus 1.

  8. Déterminer la matrice d'adjacence du graphe.

  9. Un nombre élégant à 8 chiffres correspond à une suite de 8 sommets reliés par des arêtes, soit 8 sommets qui forment une chaîne. Mais, comme il y a 8 sommets, il n'y a besoin que de 7 arêtes pour parcourir la chaîne.

a) Déterminer le nombre de nombres élégants commençant par 2 et finissant par 4.

b) Comment obtenir le nombre de nombres élégants à 8 chiffres, dont les chiffres sont tous compris entre 0 et 4 (inclus) ?

Exercice 20 : Niveaux d'un jeu vidéo

Un jeu vidéo est composé de cinq niveaux A, B, C, D et E.
Le graphe ci-dessous représente les différentes possibilités pour passer d'un niveau à l'autre (éventuellement le même).

  1. En considérant les sommets dans l'ordre alphabétique, déterminer la matrice d'adjacence du graphe.

  2. Combien existe-t-il de chaînes de longueur 4 allant de C à E ?

Déterminer ces chaînes.

  1. Un joueur passe quatre niveaux et se retrouve… sur le même niveau !

De combien de façons différentes cette situation peut-elle arriver ?

Exercice 21 : Code de messagerie

Pour accéder à sa messagerie, Camille a choisi un code qui doit être reconnu par le graphe étiqueté ci-dessous de sommets 1, 2, 3 et 4.

Une succession de lettres constitue un code possible si les lettres se succèdent sur un chemin du graphe orienté en partant du sommet 1 et en sortant au sommet 4.

Le code SENS est un code possible, alors que SUN ne l'est pas.

  1. Parmi les trois codes ci-dessous, lequel est reconnu par le graphe ?
  2. SCENES
  3. SUCCES

  4. SUSPENS

  5. Déterminer la matrice d'adjacence associée au graphe.

  6. Déterminer le nombre de codes de 4 lettres reconnus par le graphe.
    Quels sont ces codes ?