16 relations: Algorithme de Bron-Kerbosch, Arboricité, Coloration de liste, Coloration gloutonne, Conjecture d'Erdős-Burr, Dégénérescence, Densité d'un graphe, George Szekeres, Graphe planaire extérieur, Herbert Wilf, Invariant de graphe, Largeur arborescente, Nombre de Hadwiger, Problème de la clique, Réseau complexe, Théorie des réseaux.
Algorithme de Bron-Kerbosch
L'ensemble 1, 2, 5 est une clique maximale. En informatique, l'algorithme de Bron–Kerbosch est un algorithme d'énumération pour trouver toutes les cliques maximales d'un graphe non orienté.
Nouveau!!: Dégénérescence (théorie des graphes) et Algorithme de Bron-Kerbosch · Voir plus »
Arboricité
En théorie des graphes, l'arboricité (arboricity en anglais) d'un graphe non orienté est le nombre minimum de forêts nécessaires pour couvrir toutes les arêtes.
Nouveau!!: Dégénérescence (théorie des graphes) et Arboricité · Voir plus »
Coloration de liste
Une instance de coloration de liste du graphe biparti complet ''K'' 3,27 avec trois couleurs par sommet. Pour tout choix de couleurs des trois sommets centraux, l'un des 27 sommets extérieurs ne peut être coloré, ce qui montre que le nombre chromatique de liste de ''K'' 3,27 est au moins quatre. En théorie des graphes, la coloration de liste est une coloration des sommets d'un graphe où la couleur de chaque sommet est restreinte à une liste de couleurs autorisées.
Nouveau!!: Dégénérescence (théorie des graphes) et Coloration de liste · Voir plus »
Coloration gloutonne
''n''/2 couleurs. Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible.
Nouveau!!: Dégénérescence (théorie des graphes) et Coloration gloutonne · Voir plus »
Conjecture d'Erdős-Burr
En théorie des graphes, la conjecture d'Erdős-Burr, proposée en 1973 par Paul Erdős et, concerne la croissance du nombre de Ramsey d'un graphe non orienté de degré de dégénérescence donné, en fonction de son nombre de sommets.
Nouveau!!: Dégénérescence (théorie des graphes) et Conjecture d'Erdős-Burr · Voir plus »
Dégénérescence
*En mathématiques.
Nouveau!!: Dégénérescence (théorie des graphes) et Dégénérescence · Voir plus »
Densité d'un graphe
En mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe.
Nouveau!!: Dégénérescence (théorie des graphes) et Densité d'un graphe · Voir plus »
George Szekeres
George Szekeres (prononciation hongroise) est un mathématicien hongrois et australien, né en 1911 à Budapest et mort en 2005 à Adélaïde.
Nouveau!!: Dégénérescence (théorie des graphes) et George Szekeres · Voir plus »
Graphe planaire extérieur
Un graphe planaire extérieur maximal, muni d'une 3-coloration. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes.
Nouveau!!: Dégénérescence (théorie des graphes) et Graphe planaire extérieur · Voir plus »
Herbert Wilf
Herbert Saul Wilf (–) est un mathématicien américain, spécialisé en combinatoire et en théorie des graphes.
Nouveau!!: Dégénérescence (théorie des graphes) et Herbert Wilf · Voir plus »
Invariant de graphe
En théorie des graphes, un invariant de graphe est une quantité qui n'est pas modifiée par isomorphisme de graphes.
Nouveau!!: Dégénérescence (théorie des graphes) et Invariant de graphe · Voir plus »
Largeur arborescente
En théorie des graphes et en informatique théorique, la largeur arborescente ou largeur d'arbre d'un graphe (en anglais) est un nombre qui, intuitivement, mesure s'il est proche d'un arbre.
Nouveau!!: Dégénérescence (théorie des graphes) et Largeur arborescente · Voir plus »
Nombre de Hadwiger
Un graphe avec quatre sous-graphes connectés qui, lorsqu'ils sont contractés, forment un graphe complet. Il ne possède pas de mineur complet à cinq sommets par le théorème de Wagner, donc son nombre de Hadwiger est exactement quatre. En théorie des graphes, le nombre de Hadwiger d'un graphe non orienté G est la taille du plus grand graphe complet qui peut être obtenu en contractant des arêtes de G. De manière équivalente, le nombre de Hadwiger h(G) est le plus grand entier k pour lequel le graphe complet K k est un mineur de G. Le nombre de Hadwiger est également connu comme le nombre de clique de contraction de G ou le degré d'homomorphisme de G. Il est nommé d'après Hugo Hadwiger, qui l'a introduit en 1943 en conjonction avec la conjecture de Hadwiger qui stipule que le nombre de Hadwiger est toujours au moins aussi grand que le nombre chromatique de G. Les graphes qui ont un nombre de Hadwiger au plus égal à quatre ont été caractérisés par Wagner en 1937.
Nouveau!!: Dégénérescence (théorie des graphes) et Nombre de Hadwiger · Voir plus »
Problème de la clique
C(7,4).
Nouveau!!: Dégénérescence (théorie des graphes) et Problème de la clique · Voir plus »
Réseau complexe
En théorie des graphes, un réseau complexe est un réseau possédant une architecture et une topologie complexe et irrégulière.
Nouveau!!: Dégénérescence (théorie des graphes) et Réseau complexe · Voir plus »
Théorie des réseaux
Graphe partiel de l'internet, basé sur les données de opte.org du 15 janvier 2005 (voir description de l'image pour plus de détails) La théorie des réseaux est l'étude de graphes en tant que représentation d'une relation symétrique ou asymétrique entre des objets discrets.
Nouveau!!: Dégénérescence (théorie des graphes) et Théorie des réseaux · Voir plus »