Connectez-vous:

Connexion auto
Oubli mot de passe


Nouveau compte
2 millions de comptes créés

100% gratuit !
[Avantages]

  • Accueil
  • Accès rapides
  • Aide/Contact
  • Livre d'or
  • Plan du site
  • Recommander
  • Signaler un bug
  • Faire un lien




  • Publicités :




    Recommandés :
    - Traducteurs gratuits
    - Jeux gratuits
    - Nos autres sites
       

    Apprendre les mathématiques > Cours & exercices de mathématiques > test de maths n°45761 : Graphes (2)- coloration d'un graphe (Niveau Terminale ES) - cours

    > Plus de cours & d'exercices de maths (mathématiques) sur le même thème : Problèmes [Autres thèmes]
    > Tests similaires : - Heure et durées (CE1/CE2) - Heures et durées (7)- Bilan + Grand Test - Test de niveau(8)- Situations Problèmes 2 (CM2/6ème) - Test de niveau(9)- Situations Problèmes 3 (CM2/6ème) - Heures et durées(2)- Les unités de temps, Cours et Grand Test - Test de niveau (4)- Logique (Fin de cycle 2 des apprentissages fondamentaux) - Problèmes : Vitesse /Durée/ Distance parcourue - Heures et durées(4)- Soustraction des nombres sexagésimaux
    > Double-cliquez sur n'importe quel terme pour obtenir une explication...


    Graphes (2)- coloration d'un graphe (Niveau Terminale ES) - cours


    Ce test poursuit l'étude des graphes abordée dans les tests n°45326 test, n°45970 test et n°45842 test

    Graphes en TES

    Coloration d'un graphe

    Nombre chromatique


    I. Coloration d'un graphe: exemple et algorithme

    a) Exemple:

    Ci-dessous la carte de six pays imaginaires; on a colorié cette carte à l'aide de 6 couleurs différentes...

    Problème :

    Est-il possible de colorier la carte en respectant les contraintes suivantes ?

    - utiliser le minimum de couleurs ;

    - faire en sorte que deux pays ayant une frontière commune soient coloriés de deux couleurs différentes...

    Solution :

    Pour chercher un tel coloriage, on n'utilise pas de carte; on travaille sur le graphe associé.

    'On commence par colorer le pays qui a le plus de pays frontaliers'

    graphe et graphe coloré: 3 en gris ; 1 et 5 en rouge ; 2 et 4 en bleu

    b) Algorithme :

    Colorer un graphe c'est colorer les sommets de telle façon que deux sommets distincts et adjacents aient toujours des couleurs différentes.

    Méthode : Algorithme de Welch-Powell ou algorithme glouton

    1. Ranger les sommets par ordre décroissant de leurs degrés ;
    2. Choisir une couleur ;
    3. Affecter cette couleur au premier sommet de la liste non encore coloré ;
    4. Suivre la liste en attribuant cette même couleur à tout sommet
    • qui n'est  pas encore coloré ;
    •  et qui n'est pas adjacent à un sommet coloré avec cette couleur.

    Continuer jusqu'à ce que la liste soit finie.

    Si tous les sommets ne sont pas colorés, choisir une couleur qui n'est pas encore utilisée et recommencer les étapes 3 et 4 ;

    Continuer tant que chaque sommet n'est pas coloré.

    II. Graphes complets

    • Lorsque chaque sommet est relié à chaque autre par une arête, le graphe est complet.

    Exemples :


    • Un graphe planaire est un graphe qui peut être représenté sur un plan, sans qu'aucune arête n'en croise une autre.

    Les premiers circuits imprimés étaient moins fragiles quand le graphe du circuit était planaire.


    • Soit G un graphe complet d'ordre p .

    Si p est inférieur ou égal à 4, alors G est planaire ;
    Si p est supérieur ou égal à 5, alors G n'est pas planaire
    .

    • A l 'origine des graphes planaires, on trouve le théorème des 4 couleurs :

    'Il est possible, en n'utilisant que quatre couleurs différentes, de colorer n'importe quelle carte de sorte que deux régions limitrophes reçoivent toujours deux couleurs distinctes.'

    III. Nombre chromatique


    Le nombre chromatique est le plus petit nombre de couleurs nécessaires pour colorer le graphe; notons le .

    • Deux sommets distincts et reliés par une arête doivent avoir des couleurs différentes; lorsque le graphe est complet d'ordre n, son nombre chromatique    est n.
    • On peut donner des couleurs différentes aux sommets. Donc si le graphe a n sommets, alors    n .
    • Si le plus grand degré d'un sommet est r, alors   r+1.
    • Si on peut extraire d'un graphe, un sous-graphe complet d'ordre p, alors p  .
    Dans notre exemple:
    Du graphe associé à la carte, on peut extraire un sous-graphe complet d'ordre 3 (les sommets 3, 5 et 6 et leurs arêtes)
    donc 3  
    D'autre part, on a coloré le graphe à l'aide de 3 couleurs; donc   3.
    On peut conclure : = 3

    Pour trouver le nombre chromatique d'un graphe, on cherche

    - un encadrement de

    - une coloration du graphe en p couleurs: on en déduit   p.

    Le plus souvent, on peut en déduire la valeur de ...

    Il peut arriver que l'on trouve 3     4 ; dans ce cas, on ne peut pas donner !


    A vous de jouer!





    Avancé Tweeter Partager
    Exercice de maths (mathématiques) "Graphes (2)- coloration d'un graphe (Niveau Terminale ES) - cours" créé par iza51 avec le générateur de tests - créez votre propre test ! [Plus de cours et d'exercices de iza51]
    Voir les statistiques de réussite de ce test de maths (mathématiques) [Sauvegarder] [Charger] [?]


    1. Un examen comporte 6 options au choix. Chaque option se déroule sur une demi-journée; un candidat donné ne peut pas passer plus d'une option la même demi-journée. On cherche une organisation qui utilise le moins de demi-journées possibles, sachant qu'il y a des candidats inscrits en Sport (1), en Équitation (2) et Informatique (3); d'autres en Musique(4), Informatique (3) et Piscine (5) ; d'autres enfin en Danse (6) et Piscine (5).

    Le graphe associé est

    a) On peut extraire un sous-graphe complet d'ordre p = , et p est inférieur ou égal au nombre chromatique.

    b) En étudiant les degrés des sommets, on peut affirmer que le nombre chromatique est inférieur ou égal à .

    c) Pour que chaque élève puisse passer toutes ses options, il est impératif d'organiser cet examen sur demi-journées au minimum


    2. Un musée est constitué de six salles numérotées de 1 à 6; le plan de ce musée est associé au graphe suivant dans lequel une arête représente une porte de communication entre deux salles .

    a) Peut-on visiter chacune des salles du musée en passant une fois et une seule par chacune des portes ?

    b) Peut-on visiter chacune des salles du musée en passant une fois et une seule par chacune des portes et en revenant au point de départ ?

    c) Le conservateur du musée souhaite différencier chaque salle des salles voisines (c'est-à-dire accessibles par une porte) par la moquette posée sur le sol. Combien faut -il de moquettes au minimum pour réaliser ce souhait ?









    Fin de l'exercice de maths (mathématiques) "Graphes (2)- coloration d'un graphe (Niveau Terminale ES) - cours"
    Un exercice de maths gratuit pour apprendre les maths (mathématiques). (tags: probleme )
    Tous les exercices | Plus de cours et d'exercices de maths (mathématiques) sur le même thème : Problèmes



    Partager : Facebook / Google+ / Twitter / ... 


    > INDISPENSABLES : TESTEZ VOTRE NIVEAU | NOS MEILLEURES FICHES | Fiches les plus populaires | Aide/Contact

    > COURS ET TESTS : Arithmétique | Avec cours | Calculs | Calculs littéraux | Conversions | Enfants | Equations | Fonctions | Fractions | Géométrie | Jeux | Nombres | Nombres relatifs | Opérations | Plusieurs thèmes | Problèmes | Statistiques | Tests de niveaux

    > INFORMATIONS : - En savoir plus, Aide, Contactez-nous [Conditions d'utilisation] [Conseils de sécurité] Reproductions et traductions interdites sur tout support (voir conditions) | Contenu des sites déposé chaque semaine chez un huissier de justice. | Mentions légales / Vie privée / Cookies .
    | Cours et exercices de mathématiques 100% gratuits, hors abonnement internet auprès d'un fournisseur d'accès.