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

Coloriage graphique: bases et applications

Dans cours

MATH-467: Probabilistic methods in combinatorics

The 'probabilistic method' is a fundamental tool in combinatorics. The basic idea is as follows: to prove that an object (for example, graph) with certain properties exists, it suffices to prove that if the object is chosen at random, then it has the desir ...

Description

Cette séance de cours introduit le concept de coloration graphique, en se concentrant sur les bases et les applications. Il couvre des sujets tels que l'équilibrage des vecteurs, la coloration en deux couleurs de graphiques complets et la proximité des vecteurs. L'instructeur explique comment attribuer des couleurs aux bords, diviser les équipes et obtenir une équité parfaite dans divers scénarios.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Source officielle

Proximité ontologique

Mathématiques

Mathématiques discrètes: Théorie des graphes

Concepts associés (32)

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

Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs.

Coloration des arêtes d'un graphe

thumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.

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.

Dégénérescence (théorie des graphes)

En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté. Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k, et la dégénérescence d'un graphe est le plus petit k tel qu'il est k-dégénéré. On peut de façon équivalente définir le paramètre en utilisant un ordre sur les sommets (appelé ordre de dégénérescence) tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k. On parle alors parfois de nombre de marquage.

Afficher plus

Séances de cours associées (33)

Propagation de la croyance

Explore la propagation de la croyance dans les modèles graphiques, les graphiques de facteurs, les exemples de verre de spin, les distributions de Boltzmann et les propriétés de coloration des graphiques.

Algorithmes graphiques II: Traversée et chemins

Explore les méthodes de traversée des graphes, les arbres couvrants et les chemins les plus courts en utilisant BFS et DFS.

Arbres d'éclaboussure minimum: Algorithme de Prim

Explore l'algorithme de Prim pour les arbres à portée minimale et introduit le problème Traveling Salesman.

Algorithmes graphiques : Modélisation et transversalité

Couvre les algorithmes graphiques, la modélisation des relations entre les objets et les techniques de traversée telles que BFS et DFS.

Points fixes dans la théorie des graphiques

Se concentre sur les points fixes dans la théorie des graphiques et leurs implications dans les algorithmes et l'analyse.

Afficher plus

Concepts associés (32)

Coloration de graphe

Théorie des graphes

Coloration des arêtes d'un graphe

Lexique de la théorie des graphes

Dégénérescence (théorie des graphes)

Afficher plus