Informations

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

Vocabulaire des graphes

Graphe orienté

Graphe non orienté

Matrice d’adjacence

Nombre de chaînes de longueur p

 

Devoir d'entraînement | temps recommandé 20mn ou plus | Niveau 1 application directe du cours | exercices complémentaires et devoirs d’entraînement |
Exercice 1 (10 points)
  1. Représenter un graphe complet d'ordre 4.
    Rappel cours

    Graphe complet
    On appelle graphe complet un graphe dont tous les sommets sont adjacents entre eux.

    Aide

    L'ordre 4 signifie 4 sommets

    Solution

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

  2. On donne la matrice d'un graphe $G$: $\begin{pmatrix} 0&1&1&1&0\\ 0&0&0&1&0\\ 0&0&0&0&0\\ 0&0&0&0&1\\ 0&1&0&0&0\\ \end{pmatrix}$
    Quel est l'ordre de ce graphe?
    S'agit-il d'un graphe non orienté ou orienté? pourquoi?
    Représenter le graphe associé à cette matrice.
    Rappel cours

    Matrice associée à un graphe
    La matrice associée à un graphe d'ordre $n$ dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension $n$, où le terme à l'intersection de la iième ligne et de la jième colonne est nombre d'arêtes reliant i et j.
    Cette matrice est appelée matrice d'adjacence du graphe.

    Solution

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

  3. On donne le graphe ci-dessous:
    1. Quel est l'ordre de ce graphe?
      Solution

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

    2. Est-il complet? (justifier)
      Rappel cours

      Graphe complet
      On appelle graphe complet un graphe dont tous les sommets sont adjacents entre eux.

      Solution

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

    3. Donner le degré de chaque sommet.
      En déduire le nombre d'arêtes(calcul) et contrôler avec le graphe.
      Rappel cours

      Degré d'un sommet
      Deux sommets reliés par une arête sont adjacents.
      Le degré d'un sommet est le nombre d'arêtes rejoignant ce sommet.

      Solution

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

    4. Donner la matrice d'adjacence de ce graphe.
      Rappel cours

      Matrice associée à un graphe
      La matrice associée à un graphe d'ordre $n$ dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension $n$, où le terme à l'intersection de la iième ligne et de la jième colonne est nombre d'arêtes reliant i et j.
      Cette matrice est appelée matrice d'adjacence du graphe.

      Solution

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

    5. Citer une chaîne de longueur 5 reliant le sommet $A$ au sommet $C$
      Rappel cours

      Chaîne
      Une chaîne est un liste ordonnée de sommets telle que chaque sommet de la liste soit adjacent au suivant.
      La longueur d'une chaîne est le nombre d'arêtes qui la composent.
      Si l'origine et l'extrémité de la chaîne sont identiques alors il s'agit d'une chaîne fermée

      Solution

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

    6. Combien y-a-t'il de chaînes de longueur 3 allant du sommet $B$ au sommet $E$?
      Rappel cours

      Nombre de chemins de longueur $p$
      Nombre de chaînes de longueur $p$}{Soit $G$ un graphe d'ordre $n$ et de matrice d'adjacence $M$.
      Le coefficient $m_{ij}$ de la matrice $M^p$ ($p$ entier naturel non nul) est le nombre de chaînes de longueur $p$ reliant les sommets $i$ et $j$.}

      Aide

      Il faut calculer $M^3$

      Solution

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

    7. Combien y-a-t'il de allant du sommet $A$ au sommet $F$ passant par 3 sommets(pas nécessairement distincts)?
      Solution

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


Bonus Existe-t-il une chaîne passant par une seule fois par toutes les arêtes reliant deux sommets du graphe?(justifier)
Si ce n'est pas possible, combien faut-il ajouter d'arêtes au minimum pour que ce soit possible? la(les) représenter sur le graphe?
Rappel cours

Graphe connexe
Un graphe connexe est un graphe non orienté dans lequel il existe un chemin entre chaque paire de sommets.
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.
Cycle eulérienne
Un cycle eulérienne 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 chercher s'il existe une chaîne ou un cycle eulérien

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é