Envoyez votre messageInfos
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.
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
Chaque station de métro est désignée par son initiale comme indiqué dans la légende.
- 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 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.
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 StreetSolution
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 autresSolution
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 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
Pour la suite, on donne la matrice $M^3$:
- 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
