Matrice d’un graphe et nombre de chaînes de longueur 3 (réf 1654) 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 et nombre de chaînes de longueur 3 (réf 1654)

Ressource précédente: Matrice d’un graphe et nombre de chaînes de longueur 3 (réf 1653) Ressource suivante: Cours séquence 2 graphes pondérés et algorithme de Dijkstra (réf 1655)

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

Graphe complet

Nombre de chaînes de longueur 3

Ressources associées et exercices semblables

Matrice d’un graphe et d’un graphe orienté (réf 1651)
exercice

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

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

| | | |

On a schématisé ci-dessous une partie du plan du métro londonien par un graphe $\mathcal{G}$ dont les sommets sont les stations et les arêtes sont les lignes desservant ces stations.
Chaque station de métro est désignée par son initiale comme indiqué dans la légende.
graphe

Donner la matrice de ce graphe (en ordonnant les sommets dans l'ordre alphabétique).

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

Il y a 8 sommets donc la matrice est une matrice carrée d'ordre 8
Les coefficients de la première ligne correspondent aux arêtes partant du sommet B: Bond Street

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
Ce graphe est-il complet?

Rappel cours

Graphe complet
Un graphe est complet si chaque sommet est adjacents à tous les autres

Solution

Vous devez être abonné pour accéder à ce contenu...
Infos abonnements
Donner une chaîne de longueur 4 reliant les sommets B et G.

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.

Solution

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

Un touriste se trouve à la station Holborn et prévoit de se rendre à Green Park en utilisant exactement trois lignes de métro.
Quel est le nombre de trajets possibles?

Rappel cours

Nombre de chemins 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

Holborn correspond à la ligne 4 et Green Park à la colonne 3

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 nombre de chaînes de longueur 3 (réf 1653) Ressource suivante: Cours séquence 2 graphes pondérés et algorithme de Dijkstra (réf 1655)