Coloration dun graphe - Meilleur en Maths
Coloration d'un graphe 1 Activité Pour une coupe du monde de football, les équipes qualifiées sont réparties en « poule » de quatre équipes Chaque équipe rencontre une et une seule fois les trois autres Toutes les équipes de la même poule, jouent le même jour un match et un seul
Algorithmique des graphes quelques notes de cours
9 Coloration Stable de cardinal maximum 33 Si le graphe est donné par tableau de listes de successeurs, la complexité du parcours en 2 1 3 Exercices 1
Coloriage et planarite´ - Institut de Mathématiques de Toulouse
Exercice 8 (Theor´ eme` de Konig)¨ Soit G un graphe de n sommets Prouver que G admet une bicoloration si et seulement s’il ne possede pas de cycle de longueur impaire ` Exercice 9 Dans un pays, 11 villes sont reli´ees deux a deux directement soit par une autoroute soit par une` ligne de chemin de fer (qui fonctionnent dans les deux sens)
ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES EXERCICES D
Éléments de théorie des graphes - Quelques exercices d’application (avec solutions) page 3 0,0 5,0 0,3 5,3 2,3 3,0 3,3 2,0 0,2 5,2 4,3 4,0 Etc Exercice 5 (Jeu de Fan Tan) Deux joueurs disposent de 2 ou plusieurs tas d’allumettes A tour de rôle, chaque joueur peut enlever un certain nombre d’allumettes de l’un des tas (selon la
1 VOCABULAIRE DE BASE a Graphe
COLORATION D’UN GRAPHE ET NOMBRE CHROMATIQUE a Coloration d’un graphe Définition: Colorer un graphe consiste à affecter une couleur à chacun de ses sommets de telle sorte que deux sommets adjacents ne portent pas la même couleur Remarque: La coloration d’un graphe est toujours possible
ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES EXERCICES D APPLICATION
Bon nombre de ces exercices peuvent être à l’origine de toute une « famille » d’exercices que l’enseignant n’aura aucun mal à « générer » 1 NOTIONS DE BASE 1 1 Modélisation Exercice 1 Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et
Compilation réalisée à partir d’exercices de BAC TES
GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir d’exercices de BAC TES Exercice n° 1 Un groupe d’amis organise une randonnée dans les Alpes On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer Une arête entre deux sommets coïncide avec l’existence d’un
[PDF] algorithme de coloration de welsh et powell
[PDF] algorithme de coloration de graphe en java
[PDF] coloration des graphes pdf
[PDF] coloration graphe terminale es
[PDF] algorithme de coloration de graphe en c
[PDF] algorithme de coloration de graphe en python
[PDF] coloriage magique avec les puissances correction
[PDF] coloriage numérique isabelle guillot
[PDF] écrire une fraction sous la forme d'un entier et d'une fraction cm2
[PDF] les fractions supérieures ? 1
[PDF] fractions inférieures supérieures ou égales ? 1
[PDF] cours cap coiffure la permanente
[PDF] cours coloration cap coiffure
[PDF] règles des couleurs en coiffure
Coloration d'un graphe
1. Activitép24. Algorithme de coloriagep3
2. Définitionsp35. Exercicep4
3. Propriétésp3
Remarque :
Cette leçon n'est plus au progamme de TES.
Coloration d'un graphe
1. Activité
Pour une coupe du monde de football, les équipes qualifiées sont réparties en " poule » de quatre équipes.
Chaque équipe rencontre une et une seule fois les trois autres. Toutes les équipes de la même poule, jouent le même jour un match et un seul. On suppose que dans l'une des poules les équipes qualifiées sont : A : Angleterre E : Espagne F : France I : ItalieOn notera les six matchs de la poule :
AE (Angleterre;Espagne) ; AI ; AF;EF ; EI; FI .
On considère le graphe suivant, les six sommets sont les six matchs, il ya une arête entre deux sommets si et
seulement si les deux matchs ne peuvent pas être joués le même jour.L'ordre du graphe est 6.
Le degré de chaque sommet est 4.
On se propose de colorier les sommets de ce graphe de façon que deux sommets adjacents soient de couleurs
différentes. On commence par le sommet AE que l'on colorie en rouge (par exemple). Les sommets : AF;AI;EF et EI sont adjacents donc on ne peut pas les colorier en rouge. Par contre le sommet FI peut être colorier en rouge. Puis on choisit le sommet AF que l'on colorie en vert (par exemple). Les sommets AI et EF sont non coloriés et adjacrnts donc on ne peut pas les colorier en vert.Par contre le sommet EI n'est pas colorié et n'est pas adjacent donc peut être colorié en vert.
Puis on choisit le sommet AI que l'on colorie en jaune ( par exemple). Le seul sommet non encore colorié EF n'est pas adjacent à AI donc on le colorie en jaune.Remarques
Coloration d'un graphe
. Nous avons utilisé trois couleurs.Par exemple
En rouge les deux matchs de la première journée : AE et FI. En vert les deux matchs de la deuxième journée : AF et EI. En jaune les deux matchs de la troisième journée : AI et EF.. Lorsqu'on regarde le graphe, il existe des sous graphes d'ordre trois ( tout simplement des triangles) donc
il est nécessaire d'utiliser au moins trois couleurs distinctes pour le graphe donc 3 est le nombre minimal
de couleurs que l'on puisse utiliser pour colorier le graphe. On dit que 3 est le nombre chromatique du graphe.2. Définitions
. Colorier un graphe consiste à affecter une couleur à chaque sommet de sorte que deux sommets
adjacents ne portent pas la même couleur. . Le nombre chromatique est le plus petit nombre ce couleurs nécessaires à son coloriage.3. Propriétés
. Si le graphe G admet un sous graphe complet d'odre 3 ou 4 . . . alors le nombre chromatique est supérieur
ou égal à 3 ou 4 . . .donc si m est l'ordre le plus grand des sous graphes complets du graphe G, alors le nombre
chromatique de G est supérieur ou égal à m.. Si Δ est le plus grand degré des sommets de G alors le nombre chromatique de ce graphe est inférieur ou
égal à Δ+1 (propriété admise).
4. Algorithme de coloriage
( Agorithme deWelch - Powell)Coloration d'un graphe
Remarques
. Pour la la première consigneOn établit une liste ordonnéede sommets par ordre des degrés décroissants en cas d'égalité de degré le choix est
arbitraire ( donc il n'y a pas unicité de la liste). . Pour la deuxième consigne On peut aussi établir une liste ordonnée de couleurs.. Avec cet algorithme on n'obtient pas nécessairement le nombre minimal de couleurs donc le nombre chroma-
tique est inférieur ou égal au nombre de couleurs obtenues avec l'algorithme.5. Exercice
(D'après sujet de bac. Liban 2007)On considère le graphe ci-dessus.
1.a. Ce graphe est-il connexe ?
b. Déterminer le degré de chacun des sommets. On pourra donner le résultat sous forme de tableau. c. Justifier l'existence d'une chaîne eulérienne.2.a. Déterminer un encadrement du nombre chromatique de ce graphe.
b. Montrer que ce nombre chromatique est égal à 3.CORRECTION
1.a. Pour toutes les paires de sommets il existe une chaîne reliant les deux points donc le graphe est connexe.
b.c. Pour le graphe ilya deux (et deux seulement) sommets qui ont un degré impair donc le théorème d'Euler
nous permet d'affirmer qu'il existe une au moins une chaîne eulérienne ( on ne demande pas de donner un
exemple).2.a. Δ est le plus grand degré des sommets du graphe.
Δ=4 et Δ+1=5.
Il existe des sous graphes complets d'ordre 3 et il n'existe pas de sous graphes complets d'ordre 4 contenus
Coloration d'un graphe
dans ce graphe. Donc m=3 ;Conséquence
Le nombre chromatique est donc compris entre 3 et 5 . b. Pour colorier le grphe on utilise l'algorithme précédent. Liste des sommets : A ; B ; C ; D ; E ; G ; Y ; F ; H ; Z Liste des couleurs : Rouge ; Vert ; Jaune ; BleuNous avons utilisé quatre couleurs, donc nous pouvons affirmer que le nombre chromatique est compris entre 3
et 4 mais nous ne pouvons pas affirmer que le nombre chromatique est 4.