Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe (mathématiques discrètes)
Résumé
Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique.
Les graphes sont couramment représentés graphiquement à l'aide de cercles pour les sommets et de lignes (éventuellement courbées) pour les arêtes, ces dernières étant munies de flèches s'il y a une orientation. Lorsque les graphes sont très grands, la taille des sommets est souvent fonction du nombre de leurs relations (le degré).
Fichier:6n-graf.svg|Un graphe avec six sommets et sept arêtes.
Fichier:6n-graph3.svg|Le même graphe, pivoté et avec les arêtes étiquetées.
Fichier:Dominance drawing.svg|Un graphe orienté à sept sommets.
Fichier:Social Network Analysis Visualization.png|Graphe contenant des milliers de sommets.
Le mot a été utilisé pour la première fois dans ce sens par James Joseph Sylvester en 1878.
vignette|Un graphe avec trois sommets et trois arêtes.|150x150px
vignette|Un graphe orienté avec trois sommets et quatre arêtes.|150x150px
Un graphe est un couple comprenant deux ensembles :
sommets ;
arêtes, chacune étant associée à un couple ou une paire de sommets (u, v ∈ V).
Des définitions plus restreintes pour sont souvent employées :
chaque arête est une paire de sommets distincte des autres. est alors un graphe simple non orienté.
chaque arête est associée par la fonction d'incidence à une paire de sommets (ou à un singleton si ). est alors un multigraphe non orienté. Ce n'est plus un couple mais un triplet .
chaque arête est un couple distinct des autres, de deux sommets distincts l'un de l'autre. est alors un graphe simple orienté. Les arêtes sont plus souvent appelées arcs, et leur ensemble plutôt que .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.