graphes en général
DownloadTélécharger
Actions
Vote :
ScreenshotAperçu
Informations
Catégorie :Category: nCreator TI-Nspire
Auteur Author: row lee
Type : Classeur 3.0.1
Page(s) : 1
Taille Size: 2.46 Ko KB
Mis en ligne Uploaded: 02/06/2012 - 00:19:18
Uploadeur Uploader: row lee (Profil)
Téléchargements Downloads: 344
Visibilité Visibility: Archive publique
Shortlink : http://ti-pla.net/a5206
Type : Classeur 3.0.1
Page(s) : 1
Taille Size: 2.46 Ko KB
Mis en ligne Uploaded: 02/06/2012 - 00:19:18
Uploadeur Uploader: row lee (Profil)
Téléchargements Downloads: 344
Visibilité Visibility: Archive publique
Shortlink : http://ti-pla.net/a5206
Description
Fichier Nspire généré sur TI-Planet.org.
Compatible OS 3.0 et ultérieurs.
<<
1. Vocabulaire Définition Un graphe est composé de sommets et d'arêtes (ou arcs) reliant certains de ces sommets. Définitions L'ordre d'un graphe est le nombre de sommets de ce graphe. Le degré d'un sommet est le nombre d'arêtes dont ce sommet est une extrémité. Deux sommets reliés par une arête sont adjacents. Définitions Une chaîne (ou un chemin) est une suite de sommets telle que chaque sommet est relié au suivant par une arête. La longueur d'une chaîne est le nombre d'arêtes composant cette chaîne. Définition Un cycle est une chaîne fermée (c'est à dire dont l'origine et l'extrémité sont identiques) dont toutes les arêtes sont distinctes. Définition On dit qu'un graphe est connexe si deux sommets quelconques peuvent être reliés par une chaîne. Remarque Intuitivement, cela signifie que le graphe comporte un seul "morceau" 2. Chaînes et cycles eulériens Définition Une chaîne eulérienne est une chaîne qui contient une fois et une seule chacune des arêtes du graphe. Si cette chaîne est un cycle, on parle de cycle eulérien. Remarque Un graphe connexe contient une chaîne eulérienne si et seulement si on peut le tracer "sans lever le crayon". Le théorème d'Euler (ci-dessous) permet de déterminer facilement ce type de graphe. On ne peut jamais tracer un graphe non connexe sans lever le crayon ! Théorème Théorème d'Euler. Un graphe connexe contient une chaîne eulérienne si et seulement si il possède 0 ou 2 sommets de degré impair. Un graphe connexe contient un cycle eulérien si et seulement si il ne possède aucun sommet de degré impair (autrement dit tous ses sommets sont de degré pair) 3. Coloration d'un graphe Définition Colorier un graphe c'est associer à tout sommet une couleur telle que deux sommets adjacents n'aient pas la même couleur. Le plus petit nombre de couleurs nécessaire pour colorier un graphe s'appelle le nombre chromatique du graphe. Exemple Nombre chromatique Coloration d'un graphe Le graphe ci-dessus a été colorié a l'aide de 3 couleurs différentes. Il n'est pas possible de le colorier avec seulement 2 couleurs. Le nombre chromatique du graphe est donc 3. Théorème Le nombre chromatique d'un graphe est inférieur ou égal à d_(max)+1 où d_(max) est le plus grand degré des sommets. Exemple Dans l'exemple précédent le plus grand degré est 4. Le nombre chromatique du graphe est donc inférieur ou égal à 5 (On a vu que c'était 3). M+1 >ou= X >ou= à m M: le plus grand degré des somets, et m le plus grand sous-graphe complet
>>
Compatible OS 3.0 et ultérieurs.
<<
1. Vocabulaire Définition Un graphe est composé de sommets et d'arêtes (ou arcs) reliant certains de ces sommets. Définitions L'ordre d'un graphe est le nombre de sommets de ce graphe. Le degré d'un sommet est le nombre d'arêtes dont ce sommet est une extrémité. Deux sommets reliés par une arête sont adjacents. Définitions Une chaîne (ou un chemin) est une suite de sommets telle que chaque sommet est relié au suivant par une arête. La longueur d'une chaîne est le nombre d'arêtes composant cette chaîne. Définition Un cycle est une chaîne fermée (c'est à dire dont l'origine et l'extrémité sont identiques) dont toutes les arêtes sont distinctes. Définition On dit qu'un graphe est connexe si deux sommets quelconques peuvent être reliés par une chaîne. Remarque Intuitivement, cela signifie que le graphe comporte un seul "morceau" 2. Chaînes et cycles eulériens Définition Une chaîne eulérienne est une chaîne qui contient une fois et une seule chacune des arêtes du graphe. Si cette chaîne est un cycle, on parle de cycle eulérien. Remarque Un graphe connexe contient une chaîne eulérienne si et seulement si on peut le tracer "sans lever le crayon". Le théorème d'Euler (ci-dessous) permet de déterminer facilement ce type de graphe. On ne peut jamais tracer un graphe non connexe sans lever le crayon ! Théorème Théorème d'Euler. Un graphe connexe contient une chaîne eulérienne si et seulement si il possède 0 ou 2 sommets de degré impair. Un graphe connexe contient un cycle eulérien si et seulement si il ne possède aucun sommet de degré impair (autrement dit tous ses sommets sont de degré pair) 3. Coloration d'un graphe Définition Colorier un graphe c'est associer à tout sommet une couleur telle que deux sommets adjacents n'aient pas la même couleur. Le plus petit nombre de couleurs nécessaire pour colorier un graphe s'appelle le nombre chromatique du graphe. Exemple Nombre chromatique Coloration d'un graphe Le graphe ci-dessus a été colorié a l'aide de 3 couleurs différentes. Il n'est pas possible de le colorier avec seulement 2 couleurs. Le nombre chromatique du graphe est donc 3. Théorème Le nombre chromatique d'un graphe est inférieur ou égal à d_(max)+1 où d_(max) est le plus grand degré des sommets. Exemple Dans l'exemple précédent le plus grand degré est 4. Le nombre chromatique du graphe est donc inférieur ou égal à 5 (On a vu que c'était 3). M+1 >ou= X >ou= à m M: le plus grand degré des somets, et m le plus grand sous-graphe complet
>>
