Matrice d’un graphe, chaînes de longueur n sur un graphe (réf 1652) Chapitre 5 graphes et chaînes de Markov, Option maths expertes, Séquence 1 Graphes, chaînes, cycles et matrice d'un graphe

Home Option maths expertes Chapitre 5 graphes et chaînes de Markov Séquence 1 Graphes, chaînes, cycles et matrice d'un graphe

Matrice d’un graphe, chaînes de longueur n sur un graphe (réf 1652)

Ressource précédente: Matrice d’un graphe et d’un graphe orienté (réf 1651) Ressource suivante: Matrice d’un graphe et nombre de chaînes de longueur 3 (réf 1653)

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

Matrice d’un graphe

Matrices et calculatrice

Nombre de chaînes de longueur n sur un graphe

Chaînes fermées

Ressources associées et exercices semblables

Matrice d’un graphe et nombre de chaînes de longueur 3 (réf 1653)
exercice

Matrice d’un graphe et nombre de chaînes de longueur 3 (réf 1654)
exercice

| | | |

La matrice $M$ est la matrice d'un graphe dont les sommets sont numérotés de 1 à 6 dans l'ordre croissant.
$\begin{pmatrix} 0&1&1&0&1&0\\ 1&0&1&1&1&1\\ 1&1&0&0&0&1\\ 0&1&0&0&0&0\\ 1&1&0&0&0&1\\ 0&1&1&0&1&0 \end{pmatrix}$

Construire 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 i^ième ligne et de la j^ième colonne est nombre d'arêtes reliant i et j.
Cette matrice est appelée matrice d'adjacence du graphe.

Aide

Le sommet numéro 1 est adjacent aux sommets 2, 3 et 5 (coefficients de la première ligne de la matrice)

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
Avec la calculatrice, calculer $M^4$.
En déduire le nombre de chaînes de longueur 4 allant du sommet 2 au sommet 4.

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

avec la calculatrice, saisir les coefficients de $M$ puis calculer $M^4$ (sur casio OPTN puis MAT puis MAT A$^4$, sur NumWorks, bo^te à outils puis matrices)

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
A l'aide de la matrice, dire s'il existe une chaîne de longueur 3 reliant le sommet 1 au sommet 5.
Contrôler sur le graphe.

Aide

Il faut calculer $M^3$

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
Existe-il des chaînes fermées de longueur $3$ partant du sommet 4? du sommet 5?

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

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

Infos abonnements

Ressource précédente: Matrice d’un graphe et d’un graphe orienté (réf 1651) Ressource suivante: Matrice d’un graphe et nombre de chaînes de longueur 3 (réf 1653)