Arbre binaireEn informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père. Au niveau le plus élevé, niveau 0, il y a un nœud racine.
Graphe parfaitEn théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égal à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait.
Problème du voyageur de commercevignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.
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.
Théorème des quatre couleursLe théorème des quatre couleurs indique qu'il est possible, en n'utilisant que quatre couleurs différentes, de colorier n'importe quelle carte découpée en régions connexes, de sorte que deux régions adjacentes (ou limitrophes), c'est-à-dire ayant toute une frontière (et non simplement un point) en commun reçoivent toujours deux couleurs distinctes. L'énoncé peut varier et concerner, de manière tout à fait équivalente, la coloration des faces d'un polyèdre ou celle des sommets d'un graphe planaire, en remplaçant la carte par un graphe dont les sommets sont les régions et les arêtes sont les frontières entre régions.
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.
Graphe cubiqueEn théorie des graphes, une branche des mathématiques, un graphe cubique est un graphe régulier de degré 3. En d'autres termes, c'est un graphe dans lequel il y a exactement trois arêtes incidentes à chaque sommet. Le graphe complet K4 est le plus petit graphe cubique. Le graphe biparti complet K3,3 est le plus petit graphe cubique non-planaire. Le graphe de Petersen est le plus petit graphe cubique de maille 5. Le graphe de Heawood est le plus petit graphe cubique de maille 6.
Théorie de la percolationLa théorie de la percolation est une branche de la physique statistique et mathématique qui s'intéresse aux caractéristiques des milieux aléatoires, plus précisément aux ensembles de sommets connectés dans un graphe aléatoire. Cette théorie s'applique notamment en science des matériaux pour formaliser les propriétés d'écoulement dans les milieux poreux et pour la modélisation de phénomènes naturels, comme les incendies. L’histoire de la percolation prend ses racines dans l’industrie du charbon.
Arbre couvrant de poids minimalthumb|L'arbre couvrant de poids minimal d'un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur. En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal (ACM), arbre couvrant minimum ou arbre sous-tendant minimum de ce graphe est un arbre couvrant (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe).
Théorème de HallEn mathématiques, le théorème de Hall ou lemme des mariages est un résultat combinatoire qui donne une condition nécessaire et suffisante, sur une famille d'ensembles finis, pour qu'il soit possible de choisir des éléments distincts, un par ensemble. Il a été démontré par Philip Hall et a été à l'origine de la théorie du couplage dans les graphes. On appelle système de représentants distincts d'une suite de n ensembles finis , toute suite de n éléments distincts tels que pour tout , appartienne à .
