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.
Réduction polynomialeUne réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP. Dans le cadre des langages formels pour les problèmes de décision, on dit qu'un langage est réductible en temps polynomial à un langage (noté ) s'il existe une fonction calculable en temps polynomial telle que pour tout , si et seulement si .
Temps de calcul pseudo-polynomialEn informatique théorique, et notamment en théorie de la complexité, un algorithme est appelé pseudo-polynomial si sa complexité en temps est un polynôme en la valeur numérique de l'entrée (mais pas nécessairement en la taille en mémoire de l'entrée). Considérons le problème du test de primalité. On peut vérifier qu'un entier naturel donné n est premier en testant qu'il n'est divisible par aucun des entiers . Cela exige divisions, de sorte que le temps pris par cet algorithme naïf est linéaire en la valeur n .
Graphe complémentaireframe|right|Le graphe de Petersen, à gauche et son complémentaire, à droite. En théorie des graphes, le graphe complémentaire ou graphe inversé d'un graphe simple est un graphe simple ayant les mêmes sommets et tel que deux sommets distincts de soient adjacents si et seulement s'ils ne sont pas adjacents dans . Le graphe complémentaire ne doit pas être confondu avec le complémentaire dans le sens de la théorie des ensembles. En effet, l'ensemble des sommets de G reste inchangé. Le complémentaire du complémentaire est le graphe original.
Densité d'un grapheEn mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.
Théorie des graphes extrémauxEn 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.
Graphe de comparabilitéDans la théorie des graphes, un graphe de comparabilité est un graphe non orienté qui relie les paires d'éléments qui sont comparables les uns aux autres dans un ordre partiel donné. On les trouve aussi sous le nom de transitively orientable graphs, partially orderable graphs, et containment graphs. Les graphes de comparabilité sont des graphes parfaits. Les cographes sont des graphes de comparabilité Les graphes qui sont de comparabilité et dont le complémentaire est aussi de comparabilité sont exactement les graphes de permutations.
Graphe distance-unitéEn mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe s'obtenant à partir d'un ensemble de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1. Les arêtes peuvent se croiser si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. S'il n'y a pas de croisement entre les arêtes, alors le graphe est qualifié de graphe allumette.
Optimisation non linéaireEn optimisation, vue comme branche des mathématiques, l'optimisation non linéaire (en anglais : nonlinear programming – NLP) s'occupe principalement des problèmes d'optimisation dont les données, i.e., les fonctions et ensembles définissant ces problèmes, sont non linéaires, mais sont aussi différentiables autant de fois que nécessaire pour l'établissement des outils théoriques, comme les conditions d'optimalité, ou pour la bonne marche des algorithmes de résolution qui y sont introduits et analysés.
Graphe trivialement parfaitvignette|upright=2| Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre. En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S.
Morphisme de graphesUn morphisme de graphes ou homomorphisme de graphes est une application entre deux graphes (orientés ou non orientés) qui respecte la structure de ces graphes. Autrement dit l'image d'un graphe dans un graphe doit respecter les relations d'adjacence présentes dans . thumb|alt=Un homomorphisme entre deux graphes|Le graphe de gauche se projette dans le graphe de droite, par exemple de cette façon là Si et sont deux graphes dont on note les sommets V(G) et V(H) et les arêtes E(G) et E(H), une application qui envoie les sommets de G sur ceux de H est un morphisme de graphes si : , .
Algorithmethumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.
