Envoyez votre messageInformations
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
Vocabulaire des graphes
Graphe orienté
Graphe non orienté
Matrice d’adjacence
Nombre de chaînes de longueur p
Ressources associées et exercices semblables
graphe et algorithme de dijkstra (réf 1677)
exercice
graphe exercice bac 2013 (réf 1678)
exercice
- 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 - 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 - On donne le graphe ci-dessous:
- Quel est l'ordre de ce graphe?
Solution
Vous devez être abonné pour accéder à ce contenu...
Infos abonnements - 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 - 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 - 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 - 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éeSolution
Vous devez être abonné pour accéder à ce contenu...
Infos abonnements - 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 - 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
- Quel est l'ordre de ce graphe?
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
Infos abonnements