OEF Graphes --- Introduction ---

Ce module regroupe pour l'instant 33 exercices sur les définitions relatives aux graphes.

Point d'articulation

Voici un graphe. Il a composantes connexes. Il y a au moins un sommet tel que le nombre de "morceaux" (composantes connexes) du graphe augmente si on l'enlève, sans qu'il n'y ait plus de points isolés... Lequel est-ce ?

Combien a-t-il alors de composantes connexes ?

Village en quarantaine

villages sont reliés par un réseau de routes. On peut les représenter par le graphe suivant :
Mais il y a un point sensible : si on met en quarantaine un des villages, il ne sera plus possible d'aller de certains villages à d'autres. Donner le nom d'un tel village.
Combien y a-t-il alors de groupes de villages non reliés entre eux sans compter le village en quarantaine ?

Chaînes dans un graphe

On considère le graphe représenté ci-dessous :
Donner une chaîne de ce graphe, contenant exactement arêtes distinctes (on donnera la liste de ses sommets numérotés comme sur le dessin).

Nombre de chaînes entre deux sommets

On considère le graphe représenté ci-dessous :
Combien de chaînes de longueur existe-t-il entre les sommets et ?

Nombre de chaînes entre deux sommets II

On considère le graphe représenté ci-dessous :
Il y exactement chaîne chaînes de longueur entre le sommet et un autre sommet. Trouver ce sommet (il peut y en avoir plusieurs, mais on n'en demande qu'un seul)

Chaînes fermées dans un graphe

On considère le graphe représenté ci-dessous :
Donner une chaîne fermée de ce graphe, contenant exactement arêtes distinctes
On donnera la liste de ses sommets numérotés comme sur le dessin : le dernier sommet doit donc être le même que le premier.

Nombres de chaînes fermées

On considère le graphe représenté ci-dessous :
Combien de cycles de longueur existe-t-il partant du sommet ?

Chaînes orientées fermées

On considère le graphe représenté ci-dessous :
Donner une chaîne fermée de ce graphe, contenant exactement arêtes distinctes
On donnera la liste de ses sommets numérotés comme sur le dessin : le dernier sommet doit donc être le même que le premier.

Nombre chromatique

Calculer le du graphe suivant

Colorier un graphe

le graphe avec le moins de couleurs possibles

Sous-ensemble stable

Voici un graphe . Le coloriage détermine des sous-ensembles maximaux. Donnez-en un.

Graphe complet

Voici un graphe. Donner un sous-graphe d'ordre maximal.
Vous avez donné comme sous-graphe complet d'ordre maximal le graphe de sommets . Mais ce n'est même pas un sous-graphe complet. Le sous-graphe ayant comme sommets est, lui, complet maximal. Il n'est pas maximal, le sous-graphe de sommets le contient et est complet lui aussi. Il est de plus d'ordre maximal. Le sous-graphe de sommets est lui complet et d'ordre maximal. C'est un sous-graphe complet maximal, mais n'est pas d'ordre maximal. Le sous-graphe ayant comme sommets est, lui, complet maximal.
Le est supérieur ou égal à . Le degré maximum des sommets est . Le nombre chromatique est donc inférieur ou égal à .
Le nombre chromatique est en effet compris entre et .
Chercher des et donner le nombre chromatique :

Matrice des distances

On considère le graphe représenté ci-dessous.
Consigne : Pour écrire la matrice, énumérer successivement les coefficients de chaque ligne en les séparant par des virgules, et passer à la ligne à la fin de chaque ligne de la matrice.

Distance maximale

On considère le graphe représenté ci-dessous.
Donner deux points qui sont à la plus grande distance (éventuellement infinie) sur ce graphe.

Distance de deux sommets

On considère le graphe représenté ci-dessous.
Trouver un point qui est à la plus grande distance du point .

Représentations de graphes

Voici deux représentations du même graphe, l'une dans le plan, l'autre dans l'espace. Compléter les noms des sommets dans la représentation dans le plan :

Chaînes eulériennes

On considère le graphe représenté ci-dessous :
Donner une chaîne eulérienne de ce graphe.
Donner la liste de ses sommets dans l'ordre, séparés par des virgules. Répondre 0 s'il n'y en a aucune.

Chaînes ou cycles eulériens

On considère le graphe représenté ci-dessous :
Donner le degré de chacun des sommets.
k
Le graphe est-il connexe ?

Existe-t-il

Chaînes ou cycles eulériens II

considère le graphe représenté ci-dessous :

Existe-t-il

Algorithme glouton de coloration

Voici un graphe. En utilisant l'algorithme , vous devez déterminer une du graphe en coloriant les sommets dans l'ordre suivant
Les couleurs ont été ordonnées dans l'ordre

Le sommet de la liste (sommet ) est de couleur

Algorithmes de coloration

Voici un graphe colorié :
Les sommets ont été coloriés dans l'ordre
Quel algorithme a-t-on utilisé ?

Graphes isomorphes

Les deux graphes représentés sont isomorphes : seul le nom de leurs sommets est différent ainsi que leur représentation dans le plan. A vous de retrouver la correspondance :
 
Pour cela, écrivez la liste des numéros correspondant aux sommets (dans l'ordre bien sûr).

Graphes isomorphes ou non ?

Les deux graphes représentés sont-ils isomorphes ?
 

Isthme

Voici un graphe. Il a composantes connexes. Il y a une arête telle que le nombre de "morceaux" (composantes connexes) du graphe augmente si on l'enlève, sans qu'il n'y ait plus de points isolés... Laquelle est-ce ? (donner les deux sommets qu'elle joint)

Combien a-t-il alors de composantes connexes ?

Route coupée

villages sont reliés par un réseau de routes. On peut les représenter par le graphe suivant :
Mais il y a un point sensible : si on enlève une route, il ne sera plus possible d'aller de certains villages à d'autres. On essaye par contre qu'aucun village supplémentaire ne soit coupé complétement de tous les autres. Donner le nom de la route à couper en donnant le numéro de ces extrémités :
Donner le nombre de groupes de villages obtenus :

Matrice d'un graphe

Calculer la matrice d'adjacence du graphe représenté
Consigne : on entrera la matrice ligne par ligne, en séparant les éléments d'une même ligne par des virgules.

Matrice d'un graphe non orienté ?

La matrice est-elle la matrice d'un graphe simple non orienté ?

Matrice d'un graphe orienté

Calculer la matrice d'adjacence du graphe représenté
Consigne : on entrera la matrice ligne par ligne, en séparant les éléments d'une même ligne par des virgules.

Longueur d'un chemin et matrice

Voici la matrice d'un graphe ayant sommets :
.
Le calcul de donne
Combien y a-t-il de chemins allant du sommet au sommet en coups ? En regardant les matrices, donner la liste des étapes intermédiaires possibles.

Sommets et arêtes d'un graphe simple

On considère le graphe représenté ci-dessous.

Combien y a-t-il de sommets dans ce graphe ?

Combien y a-t-il d'arêtes dans ce graphe ?

Quel est le degré du sommet ?

Sommets et arêtes d'un graphe

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

Combien y a-t-il de sommets dans ce graphe ?

Combien y a-t-il de boucles ?

Quel est le degré sortant du sommet ? Quel est le degré rentrant du sommet ?

Listes d'adjacence

On considère le graphe orienté représenté ci-dessous :
Pour chacun des sommets, donner la liste des sommets que l'on peut atteindre directement en suivant une arête orientée :
k
Consigne : Si une des listes des sommets, rentrer 0 à la place.

Algorithme de coloration Welsh et Powell

Voici un graphe. En utilisant l'algorithme de , vous devez déterminer une du graphe.

Donner la liste des degrés des sommets dans l'ordre de leur numéro :
La liste des degrés des sommets est
.
On choisit de classer les sommets dans l'ordre suivant (degré décroissant) :
Avec la couleur, on colorie successivement (et dans l'ordre) les sommets .
Les couleurs ont été mises dans l'ordre
Consigne : séparer les nombres par des virgules.
The most recent version
Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.