Graphe biparti

En théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints U et V tels que chaque arête ait une extrémité dans U et l'autre dans V. Un graphe biparti permet notamment de représenter une relation binaire. Caractérisation Il existe plusieurs façons de caractériser un graphe biparti. ; Par le nombre chromatique :Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2. ; Par la longueur des cycles :Un graphe est biparti si et seulement s'il ne contient pas de cycle impair. ; Par le spectre :Si un graphe est biparti, alors son spectre vérifie la propriété suivante : :Si \lambda est une valeur propre de la matrice d'adjacence du graphe, alors -\lambda en est aussi une, avec la même multiplicité que celle de \lambda. ; Par les polyèdres :Un graphe est biparti si et seulement si

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

Publications associées

Chargement

Personnes associées (8)

Personnes associées

Chargement

Unités associées (5)

Unités associées

Chargement

Concepts associés (55)

Concepts associés

Chargement

Cours associés (8)

Cours associés

Chargement

Séances de cours associées (23)

Séances de cours associées

Chargement

Lexique de la théorie des graphes

NOTOC A ; Acyclique : graphe ne contenant pas de cycle. ; Adjacence : une liste d'adjacence est une structure de données constituée d'un tableau dont le i-ème élément co

Graphe biparti complet

En théorie des graphes, un graphe est dit biparti complet (ou encore est appelé une biclique) s'il est biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble.

Coloration de graphe

thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés

CS-450: Advanced algorithms

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many domains.

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 unexpected (and sometimes paradoxical) properties for which no other methods of construction are known.

CS-401: Applied data analysis

This course teaches the basic techniques, methodologies, and practical skills required to draw meaningful insights from a variety of data, with the help of the most acclaimed software tools in the data science world (pandas, scikit-learn, Spark, etc.)

The weighted stable matching problem

Linda Farczadi

We study the stable matching problem in non-bipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NP-hard in general. Our contribution is two fold: a polyhedral characterization and an approximation algorithm. Previously Chen et al. have shown that the stable matching polytope is integral if and only if the subgraph obtained after running phase one of Irving's algorithm is bipartite. We improve upon this result by showing that there are instances where this subgraph might not be bipartite but one can further eliminate some edges and arrive at a bipartite subgraph. Our elimination procedure ensures that the set of stable matchings remains the same, and thus the stable matching polytope of the final subgraph contains the incidence vectors of all stable matchings of our original graph. This allows us to characterize a larger class of instances for which the weighted stable matching problem is polynomial-time solvable. We also show that our edge elimination procedure is best possible, meaning that if the subgraph we arrive at is not bipartite, then there is no bipartite subgraph that has the same set of stable matchings as the original graph. We complement these results with a 2-approximation algorithm for the minimum weight stable matching problem for instances where each agent has at most two possible partners in any stable matching. This is the first approximation result for any class of instances with general weights.

2017

Chargement

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delta - 1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with Delta = O(log n), and they conjectured the existence of online algorithms using Delta (1+o(1)) colors for Delta = omega(log n). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS'03 and Bahmani et al., SODA'10). We resolve the above conjecture for adversarial vertex arrivals in bipartite graphs, for which we present a (1+o(1))Delta-edge-coloring algorithm for Delta = omega(log n) known a priori. Surprisingly, if Delta is not known ahead of time, we show that no (e/e-1 - Omega(1)) Delta-edge-coloring algorithm exists. We then provide an optimal, (e/e-1 + o(1))Delta-edge-coloring algorithm for unknown Delta = omega(log n). To obtain our results, we study a nonstandard fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.

IEEE COMPUTER SOC2019

Chargement

Matching fields and lattice points of simplices

Georg Peter Loho

We show that the Chow covectors of a linkage matching field define a bijection of lattice points and we demonstrate how one can recover the linkage matching field from this bijection. This resolves two open questions from Sturmfels & Zelevinsky (1993) on linkage matching fields. For this, we give an explicit construction that associates a bipartite incidence graph of an ordered partition of a common set to all lattice points in a dilated simplex. Given a triangulation of a product of two simplices encoded by a set of bipartite trees, we similarly prove that the bijection from left to right degree vectors of the trees is enough to recover the triangulation. As additional results, we show a cryptomorphic description of linkage matching fields and characterise the flip graph of a linkage matching field in terms of its prodsimplicial flag complex. Finally, we relate our findings to transversal matroids through the tropical Stiefel map.

2018

Chargement