Infos

Vous devez être inscrit pour accéder à ces informations.

Ceci vous permet de visualiser les ressources déjà vues et marquer à revoir celles qui nécessitent d'être retravaillées.

Inscrivez vous gratuitement ici....

Contenu

Graphe connexe

Existence d’une chaîne ou d’un cycle eulérien

Exercice | temps recommandé inférieur à 5mn | Niveau 1 application directe du cours | séquence 4 du chapitre |
Les six halls d'un parc des expositions sont reliés selon le plan ci-dessous:
  1. Illustrer cette situation par un graphe, les arêtes représentant les passages possibles d'un hall vers un autre.
    Aide

    Il y a six sommets et deux sommets sont adjacents si on peut passer de l'un à l'autre directement

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  2. Par lecture du graphe, déterminer un parcours permettant de passer du hall 1 au hall 4.
    Aide

    Il faut trouver une chaîne sur la graphe d'extrémités 1 et 4.

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  3. On souhaite parcourir le Parc des expositions en partant et en revenant dans le hall 1 en utilisant tous les passages une seule fois.
    Est-ce-possible?
    Rappel cours

    Graphe connexe
    Un graphe connexe est un graphe non orienté dans lequel il existe un chemin entre chaque paire de sommets.
    Cycle eulérien
    Un cycle eulérien est une chaîne fermée sur le graphe utilisant toutes es arêtes une et une seule fois.
    existence d'un cycle eulérien
    Un graphe connexe admet un cycle eulérien si et seulement si ses sommets sont tous de degré pair.

    Aide

    Il faut déterminer s'il existe des cycles eulériens

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements

  4. Est-ce possible si on ne souhaite pas revenir au point de départ?(on ne veut pas nécessairement partir du hall 1).
    Si oui, donner les halls de départ et d'arrivée.
    Rappel cours

    Chaîne eulérienne
    Une chaîne eulérienne est une chaîne sur le graphe utilisant toutes les arêtes une et une seule fois.
    existence d'une chaîne eulérienne
    Un graphe connexe admet une chaîne eulérienne si et seulement si ses sommets sont tous de degré pair sauf deux d'entre eux.

    Solution

    Vous devez être abonné pour accéder à ce contenu...
    Infos abonnements


Vous devez être abonné pour accéder à ce contenu...

Infos abonnements

error: Ce contenu est protégé