Point d'articulation
Voici un graphe.
Il a $val17 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 y ait plus de points isolés... Lequel est-ce ?
$val20
Combien a-t-il alors de composantes connexes ?
Village en quarantaine
$val6 villages sont reliés par un réseau de routes. On peut les représenter par le graphe suivant :
$val20
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 :
$val13
Donner une chaîne de ce graphe, contenant exactement $val14 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 :
$val14
Combien de chaînes de longueur $val7 existe-t-il entre les sommets $val16 et $val17 ?
Nombre de chaînes entre deux sommets II
On considère le graphe représenté ci-dessous :
$val14
Il y exactement $val19
chaîne
chaînes
de longueur $val7 entre le sommet $val16 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 :
$val13
Donner une chaîne $val10 fermée de ce graphe, contenant exactement $val9 arêtes $m_ors 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 :
$val14
Combien de cycles de longueur $val6 existe-t-il partant du sommet $val16 ?
Chaînes orientées fermées
On considère le graphe représenté ci-dessous :
$val14
Donner une chaîne $val10 fermée de ce graphe, contenant exactement $val9 arêtes $val11 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
$val6 Voici un graphe
. Le coloriage détermine des sous-ensembles
maximaux. Donnez-en un. 
Graphe complet
$val6 Voici un graphe. Donner un sous-graphe
d'ordre maximal. 
Vous avez donné comme sous-graphe complet d'ordre maximal le graphe de sommets
$val40.
Mais ce n'est même pas un sous-graphe complet. Le sous-graphe ayant comme sommets
$val37 est, lui, complet maximal.
Il n'est pas maximal, le sous-graphe de sommets
$val41 le contient et est complet lui aussi.
Il est de plus d'ordre maximal.
Le sous-graphe de sommets
$val37 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
$val37 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 $val24 et $val17.
Chercher des
et donner le nombre chromatique :
Matrice des distances
On considère le graphe représenté ci-dessous.
$val11
- Donner la matrice des distances de ce graphe, c'est-à-dire la matrice dont le terme situé à l'intersection des
-ième ligne et
-ième colonne est égal à la distance du sommet
au sommet
. (les distances infinies sont notées -1.)
- En déduire le diamètre du graphe (répondre "inf" si ce diamètre est infini).
- Dire enfin si ce graphe est connexe.
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.
$val11
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.
$val11
Trouver un point qui est à la plus grande distance du point $val17 .
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 : $val24
Chaînes eulériennes
On considère le graphe représenté ci-dessous :
$val20
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 :
$val23
Donner le degré de chacun des sommets. Le graphe est-il connexe
? Existe-t-il
- une chaîne eulérienne :
?
- un cycle eulérien
?
Chaînes ou cycles eulériens II
$m_On considère le graphe représenté ci-dessous :
$val23
Existe-t-il
- une chaîne eulérienne :
?
- un cycle eulérien
?
Algorithme glouton de coloration
$val6 Voici un graphe. En utilisant l'algorithme
, vous devez déterminer une
du graphe en coloriant les sommets dans l'ordre suivant $val31 Les couleurs ont été ordonnées dans l'ordre $val28 | |
Le $(val35[$m_step]) sommet de la liste (sommet $(val31[$m_step])) est de couleur
Algorithmes de coloration
Voici un graphe colorié : 
Les sommets ont été coloriés dans l'ordre $val45
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 :
$val18
$val17
Pour cela, écrivez la liste des numéros correspondant aux sommets $(val16[1..$val6]) (dans l'ordre bien sûr).
Graphes isomorphes ou non ?
Les deux graphes représentés sont-ils isomorphes ?
$val18
$val17
Isthme
Voici un graphe.
Il a $val16 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 y ait plus de points isolés... Laquelle est-ce ? (donner les deux sommets qu'elle joint)
$val19
Combien a-t-il alors de composantes connexes ?
Route coupée
$val6 villages sont reliés par un réseau de routes. On peut les représenter par le graphe suivant :
$val19
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'incidence du graphe représenté
$val11
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'incidence du graphe représenté
$val11
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 $val6 sommets :
.
Le calcul de
donne
Combien y a-t-il de chemins allant du sommet $val16 au sommet $val15 en $val25 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.
$val17
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 $val7 ?
Sommets et arêtes d'un graphe
On considère le graphe orienté représenté ci-dessous :
$val17
Combien y a-t-il de sommets dans ce graphe ?
Combien y a-t-il de boucles ?
Quel est le degré sortant du sommet $val7 ? Quel est le degré rentrant du sommet $val7 ?
Listes d'adjacence
On considère le graphe orienté représenté ci-dessous :
$val16
Pour chacun des sommets, donner la liste des sommets que l'on peut atteindre directement en suivant une arête orientée :
Consigne : Si une des listes des sommets, rentrer 0 à la place.
Algorithme de coloration Welsh et Powell
$val6 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 $val14. On choisit de classer les sommets dans l'ordre suivant (degré décroissant) : $val31 Avec la $(val39[$m_step-1]) couleur, on colorie successivement (et dans l'ordre) les sommets
. Les couleurs ont été mises dans l'ordre $val28
| |
Consigne : séparer les nombres par des virgules.