Topologie faibleEn mathématiques, la topologie faible d'un espace vectoriel topologique E est une topologie définie sur E au moyen de son dual topologique E'. On définit également sur E' une topologie dite faible-* au moyen de E. Dans tout cet article, sauf mention contraire, on notera pour et forme linéaire sur . Soient E un espace vectoriel normé (réel ou complexe), ou plus généralement un espace vectoriel topologique et E' son dual topologique, c’est-à-dire l'ensemble des formes linéaires continues sur E.
Pseudo-forêtvignette|upright=1.2 |Une 1-forêt (une pseudo-forêt maximale), composée de trois 1-arbres En théorie des graphes, une pseudo-forêt est un graphe non orienté, ou même un multigraphe dans lequel chaque composante connexe possède au plus un cycle. De manière équivalente, une pseudo-forêt est un graphe dans lequel deux cycles ne sont pas connectés par une chaîne. Un pseudo-arbre est une pseudo-forêt connexe. Les noms évoquent l'analogie avec les arbres et les forêts plus couramment étudiés : un arbre est un graphe connexe sans cycle ; une forêt est une union disjointe d'arbres.
Cycle basisIn graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expressed as a symmetric difference of basis cycles. A fundamental cycle basis may be formed from any spanning tree or spanning forest of the given graph, by selecting the cycles formed by the combination of a path in the tree and a single edge outside the tree.
Théorème du séparateur planaireEn théorie des graphes, le théorème du séparateur planaire, stipule que tout graphe planaire peut être divisé en parties plus petites en supprimant un petit nombre de sommets. Plus précisément, le théorème affirme qu'il existe un ensemble de sommets d'un graphe à sommets dont la suppression partitionne le graphe en sous-graphes disjoints dont chacun a au plus sommets. Une forme plus faible du théorème séparateur avec un séparateur de taille au lieu de a été prouvée à l'origine par Ungar (1951), et la forme avec la borne asymptotique plus fine sur la taille du séparateur a été prouvée pour la première fois par Lipton & Tarjan (1979).
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
Exponential time hypothesisIn computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time, i.e., for all constant , where n is the number of variables in the formula. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement.
Complexité en tempsEn algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Maximum cardinality matchingMaximum cardinality matching is a fundamental problem in graph theory. We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.
Théorème flot-max/coupe-minLe théorème flot-max/coupe-min (ou max flow/min cut en anglais) est un théorème important en optimisation et en théorie des graphes. Il stipule qu'étant donné un graphe de flots, le flot maximum pouvant aller de la source au puits est égal à la capacité minimale devant être retirée du graphe afin d'empêcher qu'aucun flot ne puisse passer de la source au puits. Ce théorème est un cas particulier du théorème de dualité en optimisation linéaire et généralise le théorème de Kőnig, le théorème de Hall (dans les graphes bipartis) et le théorème de Menger (dans les graphes quelconques).
Schéma d'approximation en temps polynomialEn informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS.
Problème de la cliquethumb|upright=1.5|Recherche exhaustive d'une 4-clique dans ce graphe à 7 sommets en testant la complétude des C(7,4)= 35 sous-graphes à 4 sommets. En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets tous adjacents deux à deux, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées.
BPP (complexité)En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3. La classe BPP est l'ensemble des problèmes, ou de façon équivalente des langages, pour lesquels il existe une machine de Turing probabiliste en temps polynomial qui satisfait les conditions d'acceptation suivantes : Si le mot n'est pas dans le langage, la machine le rejette avec une probabilité supérieure à 2/3.
