Coloration de graphethumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune.
Algorithme gloutonUn algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton.
Suite de Fibonaccivignette|Une juxtaposition de carrés dont les côtés ont pour longueur des nombres successifs de la suite de Fibonacci : 1, 1, 2, 3, 5, 8, 13 et 21. En mathématiques, la suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent. Notée , elle est définie par , et pour . Les termes de cette suite sont appelés nombres de Fibonacci et forment la : vignette|Représentation géométrique de la fraction continue de φ faisant apparaître les nombres de la suite de Fibonacci.
Coloration des arêtes d'un graphethumb|Coloration des arêtes du graphe de Desargues avec trois couleurs. En théorie des graphes et en algorithmique, une coloration des arêtes d'un graphe consiste à attribuer à chaque arête une couleur, en évitant que deux arêtes ayant une extrémité commune soient de la même couleur. La figure ci-contre est un exemple de coloration d'arêtes correcte. On vérifie en effet qu'aucun sommet n'est commun à deux arêtes de même couleur. On remarquera qu'ici, il n'aurait pas été possible de colorer les arêtes du graphe avec seulement deux couleurs.
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.
Total coloringIn graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ′′(G) of a graph G is the fewest colors needed in any total coloring of G.
Coloration gloutonnedroite|vignette|upright=1.4| Deux colorations gloutonnes du même graphe couronne pour des ordres différents sur les sommets. La numérotation de droite se généralise aux graphes bicolores à n sommets, et l'algorithme glouton utilise couleurs. Dans l'étude des problèmes de coloration de graphes en mathématiques et en informatique, une coloration gloutonne ou coloration séquentielle est une coloration des sommets d'un graphe obtenue par un algorithme glouton qui examine les sommets du graphe en séquence et attribue à chaque sommet la première couleur disponible.
Généralisations de la suite de FibonacciEn mathématiques, la suite de Fibonacci est définie par récurrence par : pour tout entier . Autrement dit, les deux valeurs de départ 0 et 1 étant données, chaque nombre est la somme des deux précédents. La suite de Fibonacci peut être généralisée de nombreuses façons ; par exemple, en partant d'autres nombres que 0 et 1, en ajoutant plus de deux termes pour générer le suivant, ou en ajoutant des objets autres que des nombres. À l'aide de la relation , on peut étendre la suite de Fibonacci à des indices entiers négatifs.
Codage de FibonacciLe codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont chaque terme est la somme des deux termes consécutifs précédents, ce qui lui confère une robustesse aux erreurs. Le code de Fibonacci produit est un code préfixe et universel. Dans ce code, on utilise la représentation de Zeckendorf, de telle façon que la séquence « 11 », interdite dans le nombre, apparaisse uniquement en fin de codage, et serve ainsi de délimiteur.
Polynôme de FibonacciEn mathématiques les polynômes de Fibonacci, nommés ainsi en l'honneur du mathématicien italien Leonardo Fibonacci, sont une suite de polynômes généralisant les nombres de Fibonacci, définis d'une manière telle que soit égal au n-ième nombre de la suite de Fibonacci. Les polynômes de Lucas généralisent de même les nombres de Lucas. Les polynômes de Fibonacci sont définis par une relation de récurrence linéaire. est un polynôme de degré n-1.
Mot de FibonacciEn mathématiques et plus précisément en combinatoire des mots, un mot de Fibonacci est une suite particulière de symboles pris dans un alphabet quelconque de deux lettres. Les mots de Fibonacci sont à l'opération de concaténation ce que les nombres de Fibonacci sont à l'addition. Le mot de Fibonacci infini est l'exemple paradigmatique de mot sturmien. Le nom « mot de Fibonacci » réfère aussi parfois aux éléments d'un langage formel composé des mots sur un alphabet de deux lettres et et ne contenant pas deux consécutifs.
Dégénérescence (théorie des graphes)En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté. Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k, et la dégénérescence d'un graphe est le plus petit k tel qu'il est k-dégénéré. On peut de façon équivalente définir le paramètre en utilisant un ordre sur les sommets (appelé ordre de dégénérescence) tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k. On parle alors parfois de nombre de marquage.
Algorithme de KruskalEn informatique, l'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum (ARPM) ou arbre couvrant minimum (ACM) dans un graphe connexe non-orienté et pondéré. Il a été conçu en 1956 par Joseph Kruskal. On considère un graphe connexe non-orienté et pondéré : chaque arête possède un poids qui est un nombre qui représente le coût de cette arête. Dans un tel graphe, un arbre couvrant est un sous-graphe connexe sans cycle qui contient tous les sommets du graphe.
Problème du sac à dosEn algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments décrits par leurs poids et valeurs.
Cutting stock problemIn operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimization problem in mathematics that arises from applications in industry. In terms of computational complexity, the problem is an NP-hard problem reducible to the knapsack problem. The problem can be formulated as an integer linear programming problem.
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.
Portable Document FormatLe Portable Document Format, communément abrégé en PDF, est un langage de description de page présenté par la société Adobe Systems en 1992 et qui est devenu une norme ISO en 2008. La spécificité du PDF est de préserver la mise en page d’un document telle qu'elle a été définie par son auteur, et cela quels que soient le logiciel, le système d'exploitation et l'ordinateur utilisés pour l’imprimer ou le visualiser. Le Portable Document Format qui se traduit de l'anglais en « format de document portable », généralement abrégé en PDF, est un format de fichier informatique créé par Adobe Systems.
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 nulEn mathématiques, plus spécialement en théorie des graphes, un graphe nul désigne soit un graphe d'ordre zéro (i.e. sans sommets), soit un graphe avec sommets mais sans arêtes (on parle aussi dans ce dernier cas de graphe vide). Lorsqu'un graphe nul contient des sommets tous isolés, on le note où représente le nombre de sommets du graphe. La taille (i.e. le nombre d'arêtes ou d'arcs) d'un graphe nul est toujours zéro. L'ordre (i.e. le nombre de sommets) d'un graphe nul n'est pas nécessairement zéro.
Graphe (mathématiques discrètes)Dans le domaine des mathématiques discrètes, la théorie des graphes définit le graphe, une structure composée d'objets et de relations entre deux de ces objets. Abstraitement, lesdits objets sont appelés sommets (ou nœuds ou points), et les relations entre eux sont nommées arêtes (ou liens ou lignes). On distingue les graphes non orientés, où les arêtes relient deux sommets de manière symétrique, et les graphes orientés, où les arêtes, alors appelées arcs (ou flèches), relient deux sommets de manière asymétrique.
