En théorie des graphes et en statistique, un graphon (aussi connu sous le terme limite de graphes) est une fonction symétrique mesurable , qui joue un rôle important dans l'étude des graphes denses. Les graphons sont à la fois une notion naturelle de limite d'une suite de graphes denses, et sont aussi les objets fondamentaux dans la définition des modèles de graphes aléatoires échangeables
Les graphons sont liés aux graphes denses : d'une part, les modèles de graphes aléatoires définis par les graphons donnent lieu à des graphes denses presque sûrement. D'autre part, par le lemme de régularité de Szemerédi, les graphons capturent de nombreux aspects de la structure des graphes denses de grande taille.
Un graphon est une fonction symétrique mesurable . Habituellement, un graphon est un modèle de graphes aléatoires échangeables selon le schéma suivant :
À chaque sommet du graphe est attribué une valeur aléatoire indépendante
Une arête figure dans le graphe avec probabilité .
Un modèle de graphes aléatoires est un modèle de graphes aléatoires échangeable si et seulement s'il peut être défini en termes d'un graphon (éventuellement aléatoire) de cette manière.
Le modèle basé sur un graphon fixe est parfois noté ,
par analogie avec le de graphes aléatoires.
Un graphe généré à partir d'un graphon de cette manière est appelé un graphe -aléatoire.
Il résulte de cette définition et de la loi des grands nombres que, si , les modèles de graphes aléatoires échangeables sont denses presque sûrement.
L'exemple le plus simple d'un graphon est pour une constante . Dans ce cas, le modèle de graphes aléatoires échangeables associé est le qui contient chaque arête indépendamment avec probabilité .
Plus généralement, on peut utiliser un graphon qui est constant par morceaux, en divisant le carré unité en blocs, et en posant sur le bloc d'indices . Le modèle de graphes aléatoires échangeables qui en résulte est le , une généralisation du modèle Erdős-Rényi.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc
En théorie des graphes et en statistique, un graphon (aussi connu sous le terme limite de graphes) est une fonction symétrique mesurable , qui joue un rôle important dans l'étude des graphes denses. Les graphons sont à la fois une notion naturelle de limite d'une suite de graphes denses, et sont aussi les objets fondamentaux dans la définition des modèles de graphes aléatoires échangeables Les graphons sont liés aux graphes denses : d'une part, les modèles de graphes aléatoires définis par les graphons donnent lieu à des graphes denses presque sûrement.
En théorie des graphes, un graphe extrémal (anglais : extremal graph) par rapport à une propriété est un graphe tel que l'ajout de n'importe quelle arête amène le graphe à vérifier la propriété . L'étude des graphes extrémaux se décompose en deux sujets : la recherche de bornes inférieures sur le nombre d'arêtes nécessaires à assurer la propriété (voire sur d'autres paramètres comme le degré minimum) et la caractérisation des graphes extrémaux proprement dits. L'étude des graphes extrémaux est une branche de l'étude combinatoire des graphes.
En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements. La combinatoire est en fait présente dans toute l'antiquité en Inde et en Chine. Donald Knuth, dans le volume 4A « Combinatorial Algorithms » de The Art of Computer Programming parle de la génération de n-uplets ; il dit que la génération de motifs combinatoires «a commencé alors que la civilisation elle-même prenait forme» (« began as civilization itself was taking shape»).
Explore le lemme de régularité Szemerédi, la régularité électronique dans les graphes bipartites, la structure des supergraphes et les techniques d'induction.
Explore l'échangeabilité, les résumés statistiques pour les réseaux, les questions d'invariance et le théorème Poisson Limit dans les statistiques des réseaux.
Explore les statistiques graphiques, la génération aléatoire de graphiques, l'analyse de réseaux, les mesures de centralité et les coefficients de regroupement.