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.
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).
Nombre de croisements (théorie des graphes)vignette| Une représentation du graphe de Heawood avec trois croisements. C'est le nombre minimum de croisements parmi toutes les représentations de ce graphe, qui a donc un nombre de croisements . En théorie des graphes, le nombre de croisements d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes.
Graphe orienté acycliqueEn théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.
Tracé de graphesEn théorie des graphes, le tracé de graphes consiste à représenter des graphes dans le plan. Le tracé de graphes est utile à des applications telles que la conception de circuits VLSI, l'analyse de réseaux sociaux, la cartographie, et la bio-informatique. Les graphes sont généralement représentés en utilisant des points, disques ou boites pour représenter les sommets, et des courbes ou des segments pour représenter les arêtes. Pour les graphes orientés, on utilise habituellement ses flèches en bout d'arête pour représenter l'orientation.
Cas dégénéréEn mathématiques, un cas dégénéré peut consister en un objet dont la définition fait apparaître des éléments redondants ou superflus, se ramenant parfois à une définition plus simple. Il peut aussi être vu comme un cas particulier d'une construction générale, ne satisfaisant pas une certaine propriété générique, notamment si ces cas sont rares dans un sens topologique ou en théorie de la mesure.
Vecteur positionEn géométrie, le vecteur position, ou rayon vecteur, est le vecteur qui sert à indiquer la position d'un point par rapport à un repère. L'origine du vecteur se situe à l'origine fixe du repère et son autre extrémité à la position du point. Si l'on note M cette position et O l'origine, le vecteur position se note . On le note aussi ou . En physique, le vecteur déplacement d'un point matériel ou d'un objet est le vecteur reliant une ancienne position à une nouvelle, donc le vecteur position final moins le vecteur position initial.
Majorant ou minorantEn mathématiques, soient (E , ≤) un ensemble ordonné et F une partie de E ; un élément x de E est : un majorant de F s'il est supérieur ou égal, par la relation binaire définie au préalable, à tous les éléments de F : ; un minorant de F s'il est inférieur ou égal, par la relation binaire définie au préalable, à tous les éléments de F :. Si F possède un majorant x alors on dit que F est une partie majorée. Si F possède un minorant x alors on dit que F est une partie minorée.
Année (calendrier)Une année est un intervalle de temps défini conventionnellement dans le cadre d’un calendrier, égal à un presque nombre entier de jours (certaines années, bissextiles, du calendrier chrétien comptant 365,25 jours), et plus ou moins proche de l’année tropique qui correspond à la périodicité des saisons terrestres. La durée d'une année et son commencement peuvent varier selon le calendrier considéré ; la durée de l’année tropique est elle-même sujette à variations au cours de longues périodes.
Plan (mathématiques)En géométrie classique, un plan est une surface plate illimitée, munie de notions d’alignement, d’angle et de distance, et dans laquelle peuvent s’inscrire des points, droites, cercles et autres figures planes usuelles. Il sert ainsi de cadre à la géométrie plane, et en particulier à la trigonométrie lorsqu’il est muni d’une orientation, et permet de représenter l’ensemble des nombres complexes. Un plan peut aussi se concevoir comme partie d’un espace tridimensionnel euclidien, dans lequel il permet de définir les sections planes d’un solide ou d’une autre surface.
