Graphe Connexe
- Graphe Connexe
-
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 graphe orienté) permettant d'atteindre v à partir de u.
Algorithme
L’algorithme de parcours en profondeur permet de déterminer si un graphe est connexe ou non.
Voir aussi
Catégorie : Concept en théorie des graphes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe Connexe de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe connexe — ● Graphe connexe graphe n admettant qu une seule composante connexe … Encyclopédie Universelle
Graphe connexe — Sommaire 1 Définition 2 Propriétés 3 Algorithmes 4 Exemples 5 Voir aussi … Wikipédia en Français
Graphe Planaire — Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu aucune arête (ou arc pour un graphe orienté) n en croise une autre. Autrement dit, ces graphes sont précisément… … 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
connexe — [ kɔnɛks ] adj. • 1290; lat. connexus, de connectere « lier ensemble » ♦ Qui a des rapports étroits avec autre chose. ⇒ analogue, dépendant, 1. joint, lié, uni, voisin. Affaires, matières, idées, sciences connexes. Domaine connexe à une science.… … Encyclopédie Universelle
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 Partitionable — Sommaire 1 Définitions 1.1 Graphe partitionable 1.2 S Partition 1.3 Partition d un entier 2 … Wikipédia en Français
Graphe chemin — à 6 sommets Nombre de sommets n Nombre d arêtes n − 1 Rayon … Wikipédia en Français
Graphe aléatoire — En mathématiques, un graphe aléatoire est un graphe qui est généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdös et Alfréd Rényi dans une série d articles publiés entre 1959 et 1968[1].… … Wikipédia en Français