Graphe (mathématiques discrètes)

Ê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 GraphSearch.

Découvrez-en plus sur les applications Graph.

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 .

À 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.

Publications associées (3)

Personnes associées (2)

Concepts associés (205)

Cours associés (101)

Séances de cours associées (909)

MOOCs associés (11)

Some coloring and walking problems in graphs

Benjamin Leroy-Beaulieu

Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the fo

EPFL2008

Embedded deformation for shape manipulation

Mark Pauly, Johannes Schmid

We present an algorithm that generates natural and intuitive deformations via direct manipulation for a wide range of shape representations and editing scenarios. Our method builds a space deformation

2007

Graph orientations with edge-connection and parity constraints

Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt to understand better their interrelation, we study a problem where both par

2001

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications.

MATH-260(a): Discrete mathematics

Study of structures and concepts that do not require the notion of continuity. Graph theory, or study of general countable sets are some of the areas that are covered by discrete mathematics. Emphasis

MATH-467: Probabilistic methods in combinatorics

We develop a sophisticated framework for solving problems in discrete mathematics through the use of randomness (i.e., coin flipping). This includes constructing mathematical structures with unexpecte

Analyse I

Le contenu de ce cours correspond à celui du cours d'Analyse I, comme il est enseigné pour les étudiantes et les étudiants de l'EPFL pendant leur premier semestre. Chaque chapitre du cours correspond

Analyse I (partie 1) : Prélude, notions de base, les nombres réels

Concepts de base de l'analyse réelle et introduction aux nombres réels.

Analyse I (partie 2) : Introduction aux nombres complexes

Introduction aux nombres complexes

Algèbre linéaire: matrices et applications linéaires

Couvre les matrices, les applications linéaires, les espaces vectoriels et les fonctions bijectives.

Algèbre linéaire : représentation matricielle

Explore les applications linéaires dans la représentation R2 et matricielle, y compris la base, les opérations et l'interprétation géométrique des transformations.

Algèbre vectorielle: produit scalaire

Explore le produit scalaire des vecteurs, y compris les propriétés et les méthodes de calcul.

Graphe orienté

thumb|Un graphe orienté .(Figure 1) Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble, appelé ensemble de nœuds et un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche. Étant donné un arc , on dit que est l'origine (ou la source ou le départ ou le début) de et que est la cible (ou l'arrivée ou la fin) de . Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine.

Graphe (mathématiques discrètes)

Graphe complet

En théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens). Un graphe complet est un graphe dont tous les sommets sont adjacents. À isomorphisme près, il n'existe qu'un seul graphe complet non orienté d'ordre n, que l'on note .