Ê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.
Concept
Coloration fractionnaire
Résumé
droite|vignette| 5: 2-coloration du graphe dodécaédrique. Il n'existe pas de 4: 2-coloration de ce graphe.
En théorie des graphes, la coloration fractionnaire est une généralisation de la coloration des graphes ordinaire.
Dans une coloration de graphe traditionnelle, une couleur est affectée à chaque sommet d'un graphe, et deux sommets adjacents ne doivent pas avoir la même couleur. Dans une coloration fractionnaire, un ensemble de couleurs est affecté à chaque sommet du graphe. L'exigence relative aux sommets adjacents est toujours valable. Par conséquent, si deux sommets sont reliés par une arête, ils ne doivent pas avoir de couleurs communes.
La coloration fractionnaire de graphes peut être vue comme la relaxation linéaire de la coloration de graphes traditionnelle. En effet, les problèmes de coloration fractionnaire se prêtent beaucoup mieux à une approche de programmation linéaire que les problèmes de coloration traditionnels.
On se donne un ensemble C de a couleurs ;
une a:b-coloration d'un graphe G est l'affectation, à chaque sommet, d'un ensemble de b couleurs parmi les a couleurs de C de telle manière que les ensembles de couleurs de deux sommets adjacents sont disjoints. Si b=1, il s'agit d'une coloration au sens usuel du terme. Le b-nombre chromatique noté est le plus petit a tel qu'une a:b-coloration existe. De mainière équivalente, elle peut être définie comme un homomorphisme sur le graphe de Kneser KGa,b.
Le nombre chromatique fractionnaire est le nombre défini par
La limite existe parce que est sous-additive, autrement dit .
nombre chromatique fractionnaire
Le nombre chromatique fractionnaire peut être défini de manière équivalente en termes probabilistes : est le plus petit k pour lequel il existe une distribution de probabilité sur les ensembles indépendants de G telle que pour chaque sommet v, et pour chaque ensemble indépendant S tiré de la distribution, on a :
On a
et ,
où n(G) est le nombre de sommets du graphe, est la taille maximale d'un ensemble indépendant, is the nombre de clique, et est le nombre chromatique.
Source officielle
À 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.