Nous examinerons les composantes connectées d'un graphe et la manière dont elles peuvent être utilisées pour mettre en œuvre un programme simple permettant de résoudre l'énigme de Guarini et de prouver l'optimalité d'un certain protocole. Nous verrons comment trouver un ordre valide dans une liste de tâches ou un graphe de dépendance de projet. Enfin, nous découvrirons la différence spectaculaire entre les cycles eulériens et les cycles hamiltoniens, apparemment similaires, et nous verrons comment ils sont utilisés dans l'assemblage du génome !

Cette semaine, nous étudierons trois grandes classes de graphes : les arbres, les graphes bipartis et les graphes planaires. Nous définirons les arbres à portée minimale, puis nous développerons un algorithme qui trouve le moyen le moins coûteux de relier des villes arbitraires. Nous étudierons les correspondances dans les graphes bipartites et verrons quand un ensemble d'emplois peut être pourvu par des candidats. Nous apprendrons également ce que sont les graphes planaires et verrons quand les stations de métro peuvent être reliées sans intersection. Restez à l'écoute pour d'autres énigmes interactives !

Nous nous concentrerons sur les paramètres des graphes et les problèmes qui y sont liés. Tout d'abord, nous définirons la coloration des graphes et nous verrons pourquoi les cartes politiques peuvent être colorées en seulement quatre couleurs. Ensuite, nous verrons comment les cliques et les ensembles indépendants sont liés dans les graphes. En utilisant ces notions, nous prouverons le théorème de Ramsey qui stipule que dans un grand système, le désordre complet est impossible ! Enfin, nous étudierons les couvertures de sommets et apprendrons à trouver le nombre minimum d'ordinateurs qui contrôlent toutes les connexions du réseau.

Cette semaine, nous allons développer un algorithme qui détermine la quantité maximale d'eau qui peut être acheminée dans un réseau d'approvisionnement en eau donné. Cet algorithme est également utilisé dans la pratique pour l'optimisation du trafic routier et la planification des vols des compagnies aériennes. Nous verrons comment les flux dans les réseaux sont liés aux correspondances dans les graphes bipartis. Nous développerons ensuite un algorithme qui trouve des correspondances stables dans les graphes bipartis. Cet algorithme résout le problème de l'appariement des étudiants avec les écoles, des médecins avec les hôpitaux et des donneurs d'organes avec les patients. À la fin de cette semaine, nous mettrons en œuvre un algorithme qui a remporté le prix Nobel d'économie !