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

Exercices de modèle de spin

Description

Cette séance de cours couvre les exercices liés au modèle de spin, y compris les corrections pour les exercices de la semaine 3, les problèmes de set indépendants, les problèmes d'appariement et les fonctions croissantes, en mettant l'accent sur les formulations mathématiques et les solutions.

Source officielle

Concepts associés (17)

Stable (théorie des graphes)

thumb|280px|L'ensemble des sommets en bleu dans ce graphe est un stable maximal du graphe. En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. La taille maximum d'un stable d'un graphe, noté I(G), est un invariant du graphe. Il peut être relié à d'autres invariants, par exemple à la taille de l'ensemble dominant maximum, noté dom(G).

Maximal independent set

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property. For example, in the graph P_3, a path with three vertices a, b, and c, and two edges and , the sets {b} and {a, c} are both maximally independent. The set {a} is independent, but is not maximal independent, because it is a subset of the larger independent set {a, c}.

Couplage (théorie des graphes)

En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. Soit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes.

Ensemble dominant

En théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donné G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.

Problème des mariages stables

vignette|Algorithme de Gale Shapley. En mathématiques, informatique et économie, le problème des mariages stables consiste à trouver, étant donné n hommes et n femmes, et leurs listes de préférences, une façon stable de les mettre en couple. Une situation est dite instable s'il y a au moins un homme et une femme qui préféreraient se mettre en couple plutôt que de rester avec leurs partenaires actuels (Dupont préfère à , et préfère Dupont à Durand). Ce problème a des applications en économie, en théorie des jeux et en physique statistique.

Afficher plus

Séances de cours associées (18)

Programmation linéaire : correspondance bipartite pondérée

Couvre la programmation linéaire, la correspondance bipartite pondérée et les problèmes de couverture de sommet en optimisation.

Algorithme de changement cupide : Optimisation et stabilité

Explore l'optimalité de l'algorithme de changement gourmand et la stabilité de la correspondance maximale.

Méthode Ford-Fulkerson : Structures de données disjointes

Explore la méthode Ford-Fulkerson pour le flux maximal et les structures de données disjointes.

Algorithmes et croissance des fonctions

Couvre les algorithmes d'optimisation, l'appariement stable et la notation Big-O pour l'efficacité de l'algorithme.

Algorithmes: Stable Matchings

Couvre le concept d'appariement stable et l'algorithme de Gale-Shapley.

Afficher plus

Concepts associés (17)

Stable (théorie des graphes)

Maximal independent set

Couplage (théorie des graphes)

Ensemble dominant

Problème des mariages stables

Afficher plus