Couplage (théorie des graphes)

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

En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. Soit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes. Un graphe peut posséder plusieurs couplages maximum. Les images suivantes montrent (en rouge) des couplages maximums. Un couplage maximal est un couplage M du graphe tel que toute arête du graphe possède au moins une extrémité commune avec une arête de M. Ceci équivaut à dire dans l'ensemble des couplages du graphe, M est maximal au sens de l'inclusion, i.e. que pour toute arête a de A qui n'est pas dans M, n'est plus un couplage de G. Les images suivantes montrent des couplages maximaux. Un couplage parfait ou couplage complet est un couplage M du graphe tel que tout sommet du graphe est incident à exactement une arête de M. Un graphe, même fini, ne possède pas toujours de couplage parfait (en particulier, un graphe ayant un nombre impair de sommets ne peut avoir un couplage parfait). Tout couplage parfait est maximum et tout couplage maximum est maximal (mais les réciproques sont fausses). Le théorème de Hall ou lemme des mariages donne une condition nécessaire et suffisante pour l'existence d'un couplage parfait dans un graphe biparti. Le théorème de König énonce l'égalité, dans un graphe biparti, de la taille du transversal minimum (i. e. de la couverture par sommets minimum) et de la taille du couplage maximum. Le théorème de Petersen énonce que tout graphe cubique sans isthme possède un couplage parfait. Il est possible de trouver un couplage de cardinal maximum en temps polynomial dans un graphe quelconque grâce à l'algorithme d'Edmonds.

À 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 (14)

Personnes associées (5)

Concepts associés (47)

Cours associés (20)

Séances de cours associées (120)

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

MATH-434: Lattice models

Lattice models consist of (typically random) objects living on a periodic graph. We will study some models that are mathematically interesting and representative of physical phenomena seen in the real

COM-308: Internet analytics

Internet analytics is the collection, modeling, and analysis of user data in large-scale online services, such as social networking, e-commerce, search, and advertisement. This class explores a number

Problème d'affectation

En informatique, plus précisément en recherche opérationnelle et d'optimisation combinatoire, le problème d'affectation consiste à attribuer au mieux des tâches à des agents. Chaque agent peut réaliser une unique tâche pour un coût donné et chaque tâche doit être réalisée par un unique agent. Les affectations (c'est-à-dire les couples agent-tâche) ont toutes un coût défini. Le but est de minimiser le coût total des affectations afin de réaliser toutes les tâches.

Maximum cardinality matching

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

Couplage (théorie des graphes)

Exercices de modèle de spin

Couvre les exercices sur le modèle de spin, l'ensemble indépendant, l'appariement et les fonctions croissantes.

Calcul du champ moyen

Explore le calcul du champ moyen et du champ efficace dans les algorithmes de transmission de messages.

Matching bipartite non pondéré

Introduit l'appariement bipartite non pondéré et sa solution en utilisant la programmation linéaire et la méthode simplex.

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimizat

EPFL2022

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a sin

EPFL2022

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have

IEEE COMPUTER SOC2022