Concept

Stable (théorie des graphes)

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. A maximal independent set is an independent set that is not a proper subset of any other independent set. A maximum independent set is an independent set of largest possible size for a given graph . This size is called the independence number of and is usually denoted by . The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph. Every maximum independent set also is maximal, but the converse implication does not necessarily hold. A set is independent if and only if it is a clique in the graph’s complement, so the two concepts are complementary. In fact, sufficiently large graphs with no large cliques have large independent sets, a theme that is explored in Ramsey theory. A set is independent if and only if its complement is a vertex cover. Therefore, the sum of the size of the largest independent set and the size of a minimum vertex cover is equal to the number of vertices in the graph. A vertex coloring of a graph corresponds to a partition of its vertex set into independent subsets. Hence the minimal number of colors needed in a vertex coloring, the chromatic number , is at least the quotient of the number of vertices in and the independent number . In a bipartite graph with no isolated vertices, the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering; this is Kőnig's theorem.

Source officielle

https://fr.wikipedia.org/wiki/Stable_(théorie_des_graphes)

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

Cours associés (32)

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

COM-417: Advanced probability and applications

In this course, various aspects of probability theory are considered. The first part covers the main theorems in the field (law of large numbers, central limit theorem), while the second part focuses on the theory of martingales and concentration inequalit ...

MATH-261: Discrete optimization

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems. ...

Afficher plus

Séances de cours associées (32)

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.

Gardiens minimaux dans les graphiques

Explore le concept de minimisation des gardiens dans les graphiques grâce à la sélection stratégique des bords.

Analyse statistique des données réseau: Hypergraphies

Introduit des hypergraphes, généralisant des graphiques en permettant à des sous-ensembles de nœuds de former des bords et d'explorer leurs applications dans différents domaines.

Afficher plus

Unités associées (7)

Laboratoire transport et mobilité

Chaire d'optimisation discrète

Laboratoire de théorie du calcul 2

Afficher plus

Notebooks associés (1)

Adaptive Echo Cancellation using LMS Filter

Adaptive Echo Cancellation[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will use the adaptive LMS filter to estimate the impulse response of a reverberating room. A typical use case is handsfree telephony: since the received signal, amplified and played by the speaker, is picked up by the microphone, we need to eliminate it from the signal that is transmitted back in order to avoid a feedback loop. The signal picked up by the microph

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Source officielle

https://fr.wikipedia.org/wiki/Stable_(théorie_des_graphes)

À propos de ce résultat

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Cours associés (32)

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

COM-417: Advanced probability and applications

MATH-261: Discrete optimization

Afficher plus

Séances de cours associées (32)

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.

Gardiens minimaux dans les graphiques

Explore le concept de minimisation des gardiens dans les graphiques grâce à la sélection stratégique des bords.

Analyse statistique des données réseau: Hypergraphies

Introduit des hypergraphes, généralisant des graphiques en permettant à des sous-ensembles de nœuds de former des bords et d'explorer leurs applications dans différents domaines.

Afficher plus

Publications associées (19)

Kronecker Classes and Cliques in Derangement Graphs

Given a permutation group G , the derangement graph of G is defined with vertex set G , where two elements x and y are adjacent if and only if

xy^{-1}

is a derangement. We establish that if G is transitive with degree exceeding 30, then the derangement graph of G contains a complete subgraph with four vertices. In the process, we determine all transitive groups whose derangement graph does not contain a complete subgraph on four vertices. As a consequence, if G is a normal subgroup of A such that $|A : G|

Cambridge University Press (CUP)2026

An Optimal Algorithm for Stochastic Vertex Cover

The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph G⋆ that is realized by sampling each edge independently with some probability p∈ (0, 1] in a base graph G = (V, E). The algorithm is given the base graph G and the probability p as inputs, but its only access to the realized graph G⋆ is through queries on individual edges in G that reveal the existence (or not) of the queried edge in G⋆. In this paper, we resolve the central open question for this

ACM2026

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment

The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of JRP with different cost functions for servicing requests. Most prior works on JRP and its generalizations have focused on the clairvoyant setting. Recently, Touitou [Tou23a] developed a non-clairvoyant framework that provided an O(√ n log n) upper bound for a wide class of generalized JRP, where n is the number of request types.

Springer Science and Business Media LLC2026

Afficher plus

Personnes associées (32)

Pierre Vandergheynst

Pierre Vandergheynst received the M.S. degree in physics and the Ph.D. degree in mathematical physics from the Université catholique de Louvain, Louvain-la-Neuve, Belgium, in 1995 and 1998, respectively. From 1998 to 2001, he was a Postdoctoral Researcher with the Signal Processing Laboratory, Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland. He was Assistant Professor at EPFL (2002-2007), where he is now a Full Professor of Electrical Engineering and, by courtesy, of Computer and Communication Sciences. As of 2015, Prof. Vandergheynst serves as EPFL’s Vice-Provost for Education. His research focuses on harmonic analysis, sparse approximations and mathematical data processing in general with applications covering signal, image and high dimensional data processing, computer vision, machine learning, data science and graph-based data processing. He was co-Editor-in-Chief of Signal Processing (2002-2006), Associate Editor of the IEEE Transactions on Signal Processing (2007-2011), the flagship journal of the signal processing community and currently serves as Associate Editor of Computer Vision and Image Understanding and SIAM Imaging Sciences. He has been on the Technical Committee of various conferences, serves on the steering committee of the SPARS workshop and was co-General Chairman of the EUSIPCO 2008 conference. Pierre Vandergheynst is the author or co-author of more than 70 journal papers, one monograph and several book chapters. He has received two IEEE best paper awards. Professor Vandergheynst is a laureate of the Apple 2007 ARTS award and of the 2009-2010 De Boelpaepe prize of the Royal Academy of Sciences of Belgium.

Jerome Damet

Enseignement et PhD Cours Radiation biology, protection and applications PHYS-450 Cours d'introduction à la physique des rayonnements qui vise à fournir aux étudiants les bases de la radioprotection et des informations sur les principales applications des sources/substances radioactives dans l'industrie.

Veljko Grilj

Oskari Ville Pakari

Enseignement et PhD Doctorant·es actuel·les Michel Saliba Cours Radiation and reactor experiments PHYS-451 Le cours a pour but principal de familiariser les étudiant-e-s aux différentes techniques expérimentales de détection des radiations ionisantes et aux mesures expérimentales sur un réacteur nucléaire. Les mesures sont effectuées sur CROCUS, le réacteur de l'EPFL. Radiation biology, protection and applications PHYS-450 Cours d'introduction à la physique des rayonnements

Neta Singer

Martin Vetterli

Martin Vetterli a été nommé Président de l'École polytechnique fédérale de Lausanne (EPFL) par le Conseil fédéral à l’issue d’un processus de sélection mené par le Conseil des EPF - qui l'a désigné à l'unanimité. Né à Soleure le 4 octobre 1957, Martin Vetterli a suivi sa scolarité et effectué sa maturité dans le canton de Neuchâtel. Ingénieur en génie électrique de l’ETHZ (1981), diplômé de l’Université de Stanford (1982) et docteur en sciences de l’EPFL (1986), Martin Vetterli a enseigné à Columbia University comme professeur assistant puis associé. Il a ensuite été nommé professeur ordinaire au département du génie électrique et des sciences de l’informatique de l’Université de Berkeley, avant de revenir à l’EPFL en tant que professeur ordinaire à l’âge de 38 ans. Il a également enseigné à l’ETHZ et à l’Université de Stanford. Ses activités de recherche centrées sur le génie électrique, les sciences de l’informatique et les mathématiques appliquées lui ont valu de nombreuses récompenses nationales et internationales, parmi lesquelles le Prix Latsis National, en 1996. Il est Fellow de l’Association for Computing Machinery et de l'Institute of Electrical and Electronics Engineers et membre de la National Academy of Engineering (NAE) notamment. Martin Vetterli a publié plus de 170 articles et trois ouvrages de référence. Ses travaux sur la théorie des ondelettes, utilisées dans le traitement du signal, sont reconnus par ses pairs comme étant d’une portée majeure, et ses domaines de prédilection, comme la compression des images et vidéos ou les systèmes de communication auto-organisés, sont au cœur du développement des nouvelles technologies de l’information. En tant que directeur fondateur du Pôle de Recherche National Systèmes mobiles d’information et de communication, le professeur Vetterli est un fervent défenseur de la recherche transdisciplinaire. Martin Vetterli connaît l’EPFL de l’intérieur. Alumnus de l’Ecole, il y enseigne depuis 1995, a été le vice-président chargé des relations internationales puis des affaires institutionnelles de l’Ecole entre 2004 à 2011, et doyen de la Faculté Informatique et Communication en 2011 et 2012. En parallèle à sa fonction de président du Conseil national de la recherche du Fonds national suisse qu’il a occupé de 2013 à 2016, il dirige le Laboratoire de Communications Audiovisuelles (LCAV) de l’EPFL depuis 1995. Martin Vetterli a accompagné plus de 60 doctorants en Suisse et aux Etats-Unis pendant leur thèse et se fait un point d’honneur de suivre l’évolution de leur parcours au plus haut niveau, académique ou dans le monde entrepreneurial. L’ingénieur est l’auteur d’une cinquantaine de brevets qui ont conduit à la création de plusieurs startups issues de son laboratoire, comme Dartfish ou Illusonic, ainsi qu’à des transferts de technologie par le biais de vente de brevets (Qualcomm). Il encourage activement les jeunes chercheurs à poursuivre ces efforts et commercialiser les résultats de leurs travaux.

Volkan Cevher

Volkan Cevher received the B.Sc. (valedictorian) in electrical engineering from Bilkent University in Ankara, Turkey, in 1999 and the Ph.D. in electrical and computer engineering from the Georgia Institute of Technology in Atlanta, GA in 2005. He was a Research Scientist with the University of Maryland, College Park from 2006-2007 and also with Rice University in Houston, TX, from 2008-2009. Currently, he is an Associate Professor at the Swiss Federal Institute of Technology Lausanne and a Faculty Fellow in the Electrical and Computer Engineering Department at Rice University. His research interests include machine learning, signal processing theory, optimization theory and methods, and information theory. Dr. Cevher is an ELLIS fellow and was the recipient of the Google Faculty Research award in 2018, the IEEE Signal Processing Society Best Paper Award in 2016, a Best Paper Award at CAMSAP in 2015, a Best Paper Award at SPARS in 2009, and an ERC CG in 2016 as well as an ERC StG in 2011.

Henry Markram

Enseignement et PhD Doctorant·es actuel·les Davide Bella A dirigé les thèses EPFL de Tania Rinaldi, Jean-Vincent Le Bé, Michele Pignatelli, Thomas Berger, Luca Gambazzi, Rodrigo de Campos Perin, Imad Riachi, Muhammad Asif Jan, Rajnish Ranjan, Srikanth Ramaswamy, Georges Khazen, Vincent Delattre, Mônica Favre, Shruti Muralidhar, Michael Reimann, Jean Pierre Ghobril, Renaud Luc Richardet, Marwan Abdellah, Willem Wybo, Csaba Erö, Lida Kanari, Giuseppe Chindemi, Berat Denizdurduran, Max Nolte, Taylor Howard N

Lenka Zdeborová

Lenka Zdeborová is a Professor of Physics and of Computer Science in École Polytechnique Fédérale de Lausanne where she leads the Statistical Physics of Computation Laboratory. She received a PhD in physics from University Paris-Sud and from Charles University in Prague in 2008. She spent two years in the Los Alamos National Laboratory as the Director's Postdoctoral Fellow. Between 2010 and 2020 she was a researcher at CNRS working in the Institute of Theoretical Physics in CEA Saclay, France. In 2014, she was awarded the CNRS bronze medal, in 2016 Philippe Meyer prize in theoretical physics and an ERC Starting Grant, in 2018 the Irène Joliot-Curie prize, in 2021 the Gibbs lectureship of AMS. She is an editorial board member for Journal of Physics A, Physical Review E, Physical Review X, SIMODS, Machine Learning: Science and Technology, and Information and Inference. Lenka's expertise is in applications of concepts from statistical physics, such as advanced mean field methods, replica method and related message-passing algorithms, to problems in machine learning, signal processing, inference and optimization. She enjoys erasing the boundaries between theoretical physics, mathematics and computer science.

Rayan Harfouche

Afficher plus

Unités associées (7)

Laboratoire transport et mobilité

Chaire d'optimisation discrète

Laboratoire de théorie du calcul 2

Afficher plus

Concepts associés (31)

Induced subgraph

In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges (from the original graph) connecting pairs of vertices in that subset. Formally, let be any graph, and let be any subset of vertices of G. Then the induced subgraph is the graph whose vertex set is and whose edge set consists of all of the edges in that have both endpoints in . That is, for any two vertices , and are adjacent in if and only if they are adjacent in .

Graphe parfait

En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égal à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait.

Problème de la clique

thumb|upright=1.5|Recherche exhaustive d'une 4-clique dans ce graphe à 7 sommets en testant la complétude des C(7,4)= 35 sous-graphes à 4 sommets. En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets tous adjacents deux à deux, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées.

Afficher plus

Exercices associés (3)

Modèle de choc élastique

A chariot considered as a material point of mass m moves without friction on an horizontal plane; a spring of constant k is mounted at one end of the chariot. Through this spring, the chariot that has a speed v₀, collides with a fixed wall (considered as having an infinite mass); the spring first contracts, then expands, and the chariot moves in the opposite direction. We assume that the collision is perfectly elastic, i.e. the mechanical energy is conserved.

Determine the time interval Δt during which

Boite suspendue

A material point of mass m is located on the bottom of a box of mass M, where Mu2004≫u2004m. The box is suspended to a spring of constant k. The box is pulled downwards over a distance x₀ with respect to the rest position (i.e. without load) and released with zero initial velocity.

Neglecting the mass m of the material point, determine first the position equation of the centre of mass G of the box.
Determine then the condition for the material point not to take off in terms of x₀. Frames:

Saut à l élastique

A student with mass m, attached to an elastic cord with spring constant k, jumps without any initial speed from a bridge at height h above the river. The elastic cord barely stops the student from touching the river. We neglect friction. We suggest defining a y-axis pointing upwards and with its origin at river height.

Using the conservation of total mechanical energy, show that the cord’s rest length l₀ is $l_0=h-\sqrt{\frac{2mgh}{k}}$ .
Show that, while jumping, the student reached maximal sp

Notebooks associés (1)

Adaptive Echo Cancellation using LMS Filter

Adaptive Echo Cancellation[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

Publications associées (19)

Kronecker Classes and Cliques in Derangement Graphs

Given a permutation group G , the derangement graph of G is defined with vertex set G , where two elements x and y are adjacent if and only if

xy^{-1}

Cambridge University Press (CUP)2026

An Optimal Algorithm for Stochastic Vertex Cover

ACM2026

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment

Springer Science and Business Media LLC2026

Afficher plus

Personnes associées (32)

Exercices associés (3)

Modèle de choc élastique

Determine the time interval Δt during which

Boite suspendue

Neglecting the mass m of the material point, determine first the position equation of the centre of mass G of the box.
Determine then the condition for the material point not to take off in terms of x₀. Frames:

Saut à l élastique

Using the conservation of total mechanical energy, show that the cord’s rest length l₀ is $l_0=h-\sqrt{\frac{2mgh}{k}}$ .
Show that, while jumping, the student reached maximal sp