Graphe connexe
- Graphe connexe
-
Définition
En théorie des graphes, un graphe non orienté G = (S,A) est dit connexe si quels que soient les sommets u et v de S, il existe une chaine de u vers v. C'est-à-dire, s'il existe une suite d'arêtes permettant d'atteindre v à partir de u.
Un sous-graphe connexe maximal d'un graphe non orienté quelconque est une composante connexe de ce graphe.
Propriétés
Un graphe connexe à n sommets possède au moins n-1 arêtes. S'il en a exactement n-1, c'est un arbre.
Plus généralement, un graphe à n sommets avec k composantes connexes possède au moins n-k arêtes.
Algorithmes
L’algorithme de parcours en profondeur permet de déterminer si un graphe est connexe ou non. Dans le cas d'un graphe construit de façon incrémentale, on peut utiliser des algorithmes de connexité basés sur des pointeurs pour déterminer si deux sommets sont dans la même composante connexe.
Exemples
-
-
Graphe non connexe, avec trois composantes connexes
Voir aussi
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 — 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
Graphe connexe — ● Graphe connexe graphe n admettant qu une seule composante connexe … Encyclopédie Universelle
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
