Line graphEn théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.
Graphe planaireDans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.
List of graphsThis partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.
Problème de plus court cheminvignette|Exemple d'un plus court chemin du sommet A au sommet F : (A, C, E, D, F). En théorie des graphes, le 'problème de plus court chemin' est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale. Il existe de nombreuses variantes de ce problème suivant que le graphe est fini, orienté ou non, que chaque arc ou arête possède ou non une valeur qui peut être un poids ou une longueur.
Isomorphisme de graphesEn mathématiques, dans le cadre de la théorie des graphes, un isomorphisme de graphes est une bijection entre les sommets de deux graphes qui préserve les arêtes. Ce concept est en accord avec la notion générale d'isomorphisme, une bijection qui préserve les structures. Plus précisément, un isomorphisme f entre les graphes G et H est une bijection entre les sommets de G et ceux de H, telle qu'une paire de sommets {u, v} de G est une arête de G si et seulement si {ƒ(u), ƒ(v)} est une arête de H.
Graphe de PetersenLe graphe de Petersen est, en théorie des graphes, un graphe particulier possédant et . Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois auparavant, en 1886.
Graphe cordalthumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle.
Graphe bipartiEn théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans . Un graphe biparti permet notamment de représenter une relation binaire. Il existe plusieurs façons de caractériser un graphe biparti. Par le nombre chromatique Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2. Par la longueur des cycles Un graphe est biparti si et seulement s'il ne contient pas de cycle impair.
Graph operationsIn the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations. Unary operations create a new graph from a single initial graph. Elementary operations or editing operations, which are also known as graph edit operations, create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc.
Algorithme de DijkstraEn théorie des graphes, l'algorithme de Dijkstra (prononcé ) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée.
Optimisation (mathématiques)L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.
Optimisation combinatoireL’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.
Optimisation de codeEn programmation informatique, l'optimisation de code est la pratique consistant à améliorer l'efficacité du code informatique d'un programme ou d'une bibliothèque logicielle. Ces améliorations permettent généralement au programme résultant de s'exécuter plus rapidement, de prendre moins de place en mémoire, de limiter sa consommation de ressources (par exemple les fichiers), ou de consommer moins d'énergie électrique. La règle numéro un de l'optimisation est qu'elle ne doit intervenir qu'une fois que le programme fonctionne et répond aux spécifications fonctionnelles.
Chaîne (théorie des graphes)Dans un graphe non orienté, une chaîne reliant à , notée , est définie par une suite finie d'arêtes consécutives, reliant à . La notion correspondante dans les graphes orientés est celle de chemin. Une chaîne élémentaire est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts. Une chaîne simple est une chaîne ne passant pas deux fois par une même arête, c'est-à-dire dont toutes les arêtes sont distinctes. Un cycle est une chaîne simple dont les deux extrémités sont identiques.
Optimisation convexevignette|320x320px|Optimisation convexe dans un espace en deux dimensions dans un espace contraint L'optimisation convexe est une sous-discipline de l'optimisation mathématique, dans laquelle le critère à minimiser est convexe et l'ensemble admissible est convexe. Ces problèmes sont plus simples à analyser et à résoudre que les problèmes d'optimisation non convexes, bien qu'ils puissent être NP-difficile (c'est le cas de l'optimisation copositive). La théorie permettant d'analyser ces problèmes ne requiert pas la différentiabilité des fonctions.
Optimizing compilerIn computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power consumption (the last three being popular for portable computers). Compiler optimization is generally implemented using a sequence of optimizing transformations, algorithms which take a program and transform it to produce a semantically equivalent output program that uses fewer resources or executes faster.
Peephole optimizationPeephole optimization is an optimization technique performed on a small set of compiler-generated instructions; the small set is known as the peephole or window. Peephole optimization involves changing the small set of instructions to an equivalent set that has better performance.
Démonstration (logique et mathématiques)vignette| : un des plus vieux fragments des Éléments d'Euclide qui montre une démonstration mathématique. En mathématiques et en logique, une démonstration est un ensemble structuré d'étapes correctes de raisonnement. Dans une démonstration, chaque étape est soit un axiome (un fait acquis), soit l'application d'une règle qui permet d'affirmer qu'une proposition, la conclusion, est une conséquence logique d'une ou plusieurs autres propositions, les prémisses de la règle.
Windows XPWindows XP (nom de code Whistler) est un système d'exploitation multitâches, développé et commercialisé par Microsoft, permettant l'usage d'un ordinateur tel qu'un ordinateur fixe, un portable ou encore un Media Center. Les lettres « XP » proviennent dexp'erience. Microsoft a mis fin au support le . Entre autres, il n'y a plus de mises à jour et la base virale de Windows Defender n'est plus gérée. Officiellement le successeur de Windows Millennium Edition et de Windows 2000, Windows XP est sorti le et selon une estimation d'un institut de statistiques américaines, il a été vendu à près de 400 millions de copies en .
Théorie de la démonstrationLa théorie de la démonstration, aussi connue sous le nom de théorie de la preuve (de l'anglais proof theory), est une branche de la logique mathématique. Elle a été fondée par David Hilbert au début du . Hilbert a proposé cette nouvelle discipline mathématique lors de son célèbre exposé au congrès international des mathématiciens en 1900 avec pour objectif de démontrer la cohérence des mathématiques.
