Distance (théorie des graphes)En théorie des graphes, la distance entre deux nœuds d'un graphe est la longueur d'un plus court chemin entre ces deux nœuds. La longueur d'un chemin est sa longueur en nombre d'arêtes. Pour un graphe pondéré c'est la somme des poids des arêtes empruntées. Pour les graphes non orientés, c'est une distance au sens mathématique, tandis que pour les graphes orientés elle ne vérifie pas la propriété de symétrie. Cette notion permet entre autres de définir le diamètre et le rayon d'un graphe. Catégorie:Concept
Coloration fractionnairedroite|vignette| 5: 2-coloration du graphe dodécaédrique. Il n'existe pas de 4: 2-coloration de ce graphe. En théorie des graphes, la coloration fractionnaire est une généralisation de la coloration des graphes ordinaire. Dans une coloration de graphe traditionnelle, une couleur est affectée à chaque sommet d'un graphe, et deux sommets adjacents ne doivent pas avoir la même couleur. Dans une coloration fractionnaire, un ensemble de couleurs est affecté à chaque sommet du graphe.
Graphe orienté acycliqueEn théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.
Implicit graphIn the study of graph algorithms, an implicit graph representation (or more simply implicit graph) is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are determined algorithmically from some other input, for example a computable function. The notion of an implicit graph is common in various search algorithms which are described in terms of graphs. In this context, an implicit graph may be defined as a set of rules to define all neighbors for any specified vertex.
Graphe de Ramanujanvignette|Le graphe de Pappus, qui selon les valeurs propres de sa matrice de connexion, est aussi un graphe de Ramanujan. Un graphe de Ramanujan, nommé d'après Srinivasa Ramanujan, est un graphe régulier dont le trou spectral (spectral gap) est presque aussi grand que possible. De tels graphes sont d'excellents graphes expanseurs. Autrement dit, il s'agit d'une famille de graphes où chaque sommet a un même degré (régulier) et où les deux valeurs propres les plus élevées ont une différence presque aussi grande que possible.
Problème NP-completEn théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
Problème de l'isomorphisme de graphesvignette|Le problème est de savoir si deux graphes sont les mêmes. En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets. Ce problème est particulièrement important en théorie de la complexité, plus particulièrement pour le problème P=NP.
Medical procedureA medical procedure is a course of action intended to achieve a result in the delivery of healthcare. A medical procedure with the intention of determining, measuring, or diagnosing a patient condition or parameter is also called a medical test. Other common kinds of procedures are therapeutic (i.e., intended to treat, cure, or restore function or structure), such as surgical and physical rehabilitation procedures. "An activity directed at or performed on an individual with the object of improving health, treating disease or injury, or making a diagnosis.
Relativité généraleLa relativité générale est une théorie relativiste de la gravitation, c'est-à-dire qu'elle décrit l'influence de la présence de matière, et plus généralement d'énergie, sur le mouvement des astres en tenant compte des principes de la relativité restreinte. La relativité générale englobe et supplante la théorie de la gravitation universelle d'Isaac Newton qui en représente la limite aux petites vitesses (comparées à la vitesse de la lumière) et aux champs gravitationnels faibles.
RenforcementEn psychologie, le renforcement est un procédé qui augmente la probabilité de répétition d'un comportement. Les théories sur l'apprentissage par renforcement sont étudiées par la psychologie béhavioriste et font l'objet de nombreuses applications visant à modifier les comportements animaux et humains. B.F. Skinner fut le premier à en étudier systématiquement les effets sur des rats et des pigeons. Le renforcement est une procédure par laquelle la fréquence d'apparition d'un comportement va augmenter en fonction de sa conséquence.
Modèle de langageEn traitement automatique des langues, un modèle de langage ou modèle linguistique est un modèle statistique de la distribution de symboles distincts (lettres, phonèmes, mots) dans une langue naturelle. Un modèle de langage peut par exemple prédire le mot suivant dans une séquence de mots. Un modèle de langage n-gramme est un modèle de langage qui modélise des séquences de mots comme un processus de Markov. Il utilise l'hypothèse simplificatrice selon laquelle la probabilité du mot suivant dans une séquence ne dépend que d'une fenêtre de taille fixe de mots précédents.
Recherche tabouLa recherche tabou est une métaheuristique d'optimisation présentée par Fred W. Glover en 1986. On trouve souvent l'appellation recherche avec tabous en français. Cette méthode est une métaheuristique itérative qualifiée de recherche locale au sens large. L'idée de la recherche tabou consiste, à partir d'une position donnée, à en explorer le voisinage et à choisir la position dans ce voisinage qui minimise la fonction objectif.
