Graphe fortement régulierEn théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier. Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que Toute paire de sommets adjacents a exactement λ voisins communs. Toute paire de sommets non-adjacents a exactement μ voisins communs. Un graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).
Graphe completEn théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens). Un graphe complet est un graphe dont tous les sommets sont adjacents. À isomorphisme près, il n'existe qu'un seul graphe complet non orienté d'ordre n, que l'on note .
Contrainte (mathématiques)En mathématiques, une contrainte est une condition que doit satisfaire la solution d'un problème d'optimisation. On distingue deux types de contraintes : les contraintes d'égalité et les contraintes en inégalité. L'ensemble des solutions satisfaisant toutes les contraintes est appelé l'ensemble admissible. On considère un problème d'optimisation classique : avec et et désigne le vecteur . Dans cet exemple, la première ligne montre la fonction à minimiser (appelée fonction objectif ou fonction-coût) mais aussi l'ensemble où la solution doit être recherché, ici C.
Graphe distance-régulierEn théorie des graphes, un graphe régulier est dit distance-régulier si pour tous sommets distants de , et pour tous entiers naturels , il y a toujours le même nombre de sommets qui sont à la fois à distance de et à distance de . De manière équivalente, un graphe est distance-régulier si pour tous sommets , le nombre de sommets voisins de à distance de et le nombre de sommets voisins de à distance de ne dépendent que de et de la distance entre et . Formellement, tels que et où est l’ensemble des sommets à distance de , et .
Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
NP (complexité)La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.
Propagation de contraintesLa propagation de contraintes dans le domaine de la programmation par contraintes est le fait de réduire le domaine d'une variable afin de maintenir l'ensemble des valeurs possibles cohérent avec les contraintes du problème. La propagation de contraintes permet ainsi de résoudre un problème si la propagation permet d'établir la cohérence du problème. Les techniques de propagation de contraintes sont utilisées pour réduire la taille de l'espace de recherche lors de la résolution d'un problème de satisfaction de contraintes par un algorithme de recherche arborescente.
Graphe de KneserEn théorie des graphes, les graphes de Kneser forment une famille infinie de graphes. Le graphe de Kneser KGn,k est un graphe simple dont les sommets correspondent aux sous-ensembles à k éléments d'un ensemble à n éléments. Deux sommets sont reliés s'ils correspondent à des sous-ensembles disjoints. Son ordre est donc égal , le nombre de combinaison de k parmi n, et il est régulier de degré . En 1955, le mathématicien Martin Kneser se pose la question suivante : Kneser conjecture que ce n'est pas possible et le publie sous forme d'un exercice.
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.
Eulerian pathIn graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this: Given the graph in the image, is it possible to construct a path (or a cycle; i.
