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

Méthode probabiliste et ses applications

Description

Cette séance de cours introduit la méthode probabiliste, mettant l'accent sur l'utilisation d'espaces de probabilité appropriés pour prouver les résultats d'existence. Il couvre des applications telles que l'existence de grands sous-graphes bipartites et le théorème de Turán, fournissant des preuves détaillées et des exemples.

Source officielle

Proximité ontologique

Mathématiques

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

Concepts associés (26)

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.

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.

Graphe biparti

En théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans . Un graphe biparti permet notamment de représenter une relation binaire. Il existe plusieurs façons de caractériser un graphe biparti. Par le nombre chromatique Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2. Par la longueur des cycles Un graphe est biparti si et seulement s'il ne contient pas de cycle impair.

Graphe biparti complet

En théorie des graphes, un graphe est dit biparti complet (ou encore est appelé une biclique) s'il est biparti et chaque sommet du premier ensemble est relié à tous les sommets du second ensemble. Plus précisément, il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que chaque sommet de est relié à chaque sommet de . Si le premier ensemble est de cardinal m et le second ensemble est de cardinal n, le graphe biparti complet est noté . Si m = 1, le graphe complet biparti K1,n est une étoile et est noté .

Espace probabilisé

Un espace de probabilité(s) ou espace probabilisé est construit à partir d'un espace probabilisable en le complétant par une mesure de probabilité : il permet la modélisation quantitative de l'expérience aléatoire étudiée en associant une probabilité numérique à tout événement lié à l'expérience. Formellement, c'est un triplet formé d'un ensemble , d'une tribu sur et d'une mesure sur cette tribu tel que . L'ensemble est appelé l'univers et les éléments de sont appelés les événements.

Afficher plus

Séances de cours associées (35)

Modèles graphiques : Représentation des distributions probabilistes

Couvre les modèles graphiques pour les distributions probabilistes à l'aide de graphiques, de nœuds et de bords.

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.

Graphiques denses: De la théorie aux applications

Explore la transition des graphes clairsemés aux graphes denses et leurs applications réelles.

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.

Subgraphs vs Induced Subgraphs

Distingue entre les sous-graphes et les sous-graphes induits en théorie des graphes, illustrant la construction d'arbres couvrants minimes.

Afficher plus

Concepts associés (26)

Théorie des graphes

Lexique de la théorie des graphes

Graphe biparti

Graphe biparti complet

Espace probabilisé

Afficher plus