Parcours (graphe)
- Parcours (graphe)
-
Parcours (graphe)
En théorie des graphes, un parcours de sommets (resp. d'arêtes, d'arcs) dans un graphe G est une liste ordonnée de sommets (resp. d'arêtes, d'arcs) de G telle que tout sommet sauf le premier (resp. arêtes, arcs) est adjacent (resp. incident) dans le graphe avec un autre sommet placé avant lui dans la liste. Un parcours est fermé si le premier élément de la liste est aussi le dernier. On parle souvent de parcours sans en préciser le type lorsque le contexte ne laisse pas d'ambiguïté. Le plus souvent il s'agit de parcours de sommet.
Algorithmes de parcours
Il existe de nombreux algorithmes de parcours. Les plus couramment décrits sont:
|
Informatique théorique |
| Théorie du calcul |
|
| Logique, syntaxe et sémantique |
|
| Algorithmique, complexité et mathématiques discrètes |
|
Portail des mathématiques
Catégorie : Concept en théorie des graphes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Parcours (graphe) de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe Eulérien — En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété suivante : On… … Wikipédia en Français
Graphe eulerien — Graphe eulérien En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété… … Wikipédia en Français
Graphe tétraédrique — Représentation du graphe tétraédrique. Nombre de sommets 4 Nombre d arêtes 6 Distribution des degrés 3 régulier Rayon 1 … Wikipédia en Français
Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier … Wikipédia en Français
graphe — [ graf ] n. m. • 1926; du gr. graphein « écrire » ♦ Math., log. Ensemble des couples d éléments vérifiant une relation donnée. Diagramme représentant le graphe d une relation. Théorie des graphes. Représentation graphique d une fonction. ● graphe … Encyclopédie Universelle
Graphe Connexe — Définition En théorie des graphes, un graphe G = (S,A) est dit connexe si quels que soient les sommets u et v de S, il existe un chemin de u vers v. C est à dire, s il existe une suite d arêtes (ou d arcs correctement orientés dans le cas d un… … Wikipédia en Français
Parcours — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
Parcours (homonymie) — Parcours Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom … Wikipédia en Français
Graphe eulérien — En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété suivante : On… … Wikipédia en Français
Graphe partiel — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A … Wikipédia en Français
Pour les articles homonymes, voir Parcours (homonymie).
