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

Ce document provient de « Graphe connexe ».

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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”