Coloration de graphe | EPFL Graph Search

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

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 par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l'allocation de registres en compilation. Théorème des quatre couleurs Les premiers résultats de coloration de graphe concernent presque exclusivement les graphes planaires : il s'agissait alors de colorier des cartes. En cherchant à mettre en couleurs une carte des comtés d'Angleterre, Francis Guthrie postula la conjecture des quatre couleurs. Il remarqua en effet qu'il n'y avait besoin que de quatre couleurs pour que deux comtés ayant une frontière commune soient de couleurs différentes. Le frère de Guthrie transmit la question à son professeur de mathématiques, Auguste de Morgan de l'University College de Londres. De Morgan mentionna ce problème dans une lettre adressée à William Rowan Hamilton en 1852. Arthur Cayley évoqua cette question lors d'un colloque de la London Mathematical Society en 1879. La même année, Alfred Kempe publia ce qu'il prétendit en être une démonstration et pendant une décennie, on crut que le problème des quatre couleurs était résolu. Kempe fut élu membre de la Royal Society et devint ensuite président de la London Mathematical Society. En 1890, Percy John Heawood fit remarquer que la démonstration de Kempe était fausse. Il montra quant à lui le théorème des cinq couleurs en reprenant des idées de Kempe. De nombreux travaux ont été publiés lors du siècle suivant pour réduire le nombre de couleurs à quatre, jusqu'à la démonstration finale de Kenneth Appel et Wolfgang Haken.

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

Personnes associées (5)

Unités associées (1)

Concepts associés (151)

Cours associés (72)

Séances de cours associées (599)

MOOCs associés (2)

Coloration de graphe

Clique (théorie des graphes)

thumb|Exemple de graphe possédant une 3-clique (en rouge) : les trois sommets de ce sous-graphe sont tous adjacents deux-à-deux. thumb|Exemple de « biclique » : le graphe biparti complet K3,3. Une clique d'un graphe non orienté est, en théorie des graphes, un sous-ensemble des sommets de ce graphe dont le sous-graphe induit est complet, c'est-à-dire que deux sommets quelconques de la clique sont toujours adjacents. Une clique maximum d'un graphe est une clique dont le cardinal est le plus grand (c'est-à-dire qu'elle possède le plus grand nombre de sommets).

Lexique de la théorie des graphes

NOTOC 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 -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

Sublinear Algorithms for Spectral Graph Clustering

Aidasadat Mousavifar

This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become pr

EPFL2021

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.First, we consider two stochastic models calle

EPFL2021

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O)

ASSOC COMPUTING MACHINERY2020

This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and

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

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

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

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

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.

Fonctions Trigonométriques, Logarithmiques et Exponentielles

Ce cours donne les connaissances fondamentales liées aux fonctions trigonométriques, logarithmiques et exponentielles. La présentation des concepts et des propositions est soutenue par une grande gamm

Fonctions Trigonométriques, Logarithmiques et Exponentielles