Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Problème de satisfaction des contraintes

Concepts associés (22)

Coloration fractionnaire

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.

Random cluster model

In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, electrical networks, etc. It is also referred to as the RC model or sometimes the FK representation after its founders Cees Fortuin and Piet Kasteleyn. Let be a graph, and be a bond configuration on the graph that maps each edge to a value of either 0 or 1.