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.
Graphe dualEn théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual.
Graphe planaire extérieurvignette|Un graphe planaire extérieur maximal, muni d'une 3-coloration. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes.
Graph embeddingIn topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that: the endpoints of the arc associated with an edge are the points associated with the end vertices of no arcs include points associated with other vertices, two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold.
Nœud de trèflevignette|Faire un nœud de trèfle (vidéo) vignette|Surface de Seifert associée à un nœud de trèfle : il en forme le bord. En théorie des nœuds, le nœud de trèfle est le nœud le plus simple après le nœud trivial. C'est le seul nœud premier à trois croisements. On peut aussi le décrire comme nœud torique de type (2,3), son mot dans le groupe de tresses étant σ13. Une autre description (liée à la précédente) est l'intersection de la sphère unité dans C2 avec la courbe plane complexe d'équation .
Nœud premiervignette|90x90px| Entrelacs premier le plus simple En théorie des nœuds, un nœud premier, ou un entrelacs premier est un nœud ou entrelacs qui est, dans un certain sens, indécomposable. Les nœuds ou entrelacs qui ne sont pas premiers sont dits composés. Déterminer si un nœud donné est premier ou non peut être un problème non trivial. Un nœud ou entrelacs premier est un nœud ou entrelacs non trivial qui ne peut pas être obtenu comme la somme connexe de deux nœuds ou entrelacs non triviaux.
Torevignette|Modélisation d'un tore Un tore est un solide géométrique représentant un tube courbé refermé sur lui-même. Le terme « tore » comporte différentes acceptions plus spécifiques selon le contexte : en ingénierie ou en géométrie élémentaire, un tore est un solide de révolution de l'espace obtenu à partir d'un cercle, ou bien sa surface. Une chambre à air, une bouée, certains joints d'étanchéité ou encore certains beignets (les donuts nord-américains) ont ainsi une forme plus ou moins torique ; en architecture, un tore correspond à une moulure ronde, semi-cylindrique.
Graphe polyédriqueEn théorie des graphes, une branche des mathématiques, un graphe polyédrique est un graphe non orienté défini en termes géométriques : il représente les sommets et les arêtes d'un polyèdre convexe. On peut aussi définir un graphe polyédrique en termes purement issus de la théorie des graphes : c'est un graphe planaire 3 sommet-connexe. Le diagramme de Schlegel d'un polyèdre convexe représente ses sommets et ses arêtes par des points et des segments de droite dans le plan euclidien.
Chiral knotIn the mathematical field of knot theory, a chiral knot is a knot that is not equivalent to its mirror image (when identical while reversed). An oriented knot that is equivalent to its mirror image is an amphicheiral knot, also called an achiral knot. The chirality of a knot is a knot invariant. A knot's chirality can be further classified depending on whether or not it is invertible. There are only five knot symmetry types, indicated by chirality and invertibility: fully chiral, invertible, positively amphicheiral noninvertible, negatively amphicheiral noninvertible, and fully amphicheiral invertible.
Linkless embeddingIn topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.
Nœud (mathématiques)En mathématiques, et plus particulièrement en géométrie et en topologie algébrique, un nœud est un plongement d'un cercle dans R, l'espace euclidien de dimension 3, considéré à des déformations continues près. Une différence essentielle entre les nœuds usuels et les nœuds mathématiques est que ces derniers sont fermés (sans extrémités permettant de les nouer ou de les dénouer) ; les propriétés physiques des nœuds réels, telles que la friction ou l'épaisseur des cordes, sont généralement également négligées.
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).
Théorie des nœudsthumb|right|Représentation d’un nœud torique de type (3, 8). La théorie des nœuds est une branche de la topologie qui consiste en l'étude mathématique de courbes présentant des liaisons avec elles-mêmes, un « bout de ficelle » idéalisé en lacets. Elle est donc très proche de la théorie des tresses qui comporte plusieurs chemins ou « bouts de ficelle ». left|thumb|Nœuds triviaux La théorie des nœuds a commencé vers 1860 et avec des travaux de Carl Friedrich Gauss liés à l'électromagnétisme.
Test de planaritéEn théorie des graphes, le problème du test de planarité est le problème algorithmique qui consiste à tester si un graphe donné est un graphe planaire (c'est-à-dire s'il peut être dessiné dans le plan sans intersection d'arêtes). Il s'agit d'un problème bien étudié en informatique pour lequel de nombreux algorithmes pratiques ont été donnés, souvent en décrivant de nouvelles structures de données. La plupart de ces méthodes fonctionnent en temps O(n) (temps linéaire), où n est le nombre d'arêtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal.
Théorie topologique des graphesEn mathématiques, la théorie topologique des graphes est une branche de la théorie des graphes . Elle étudie entre autres les plongements de graphes dans des surfaces, les graphiques en tant qu'espaces topologiques ainsi que les immersions de graphes. Un plongement d'un graphe dans une surface donnée, une sphère par exemple, est une façon de dessiner ce graphe sur cette surface sans que deux arêtes se croisent. Un problème fondamental de la théorie topologique des graphes, souvent présenté comme un casse - tête mathématique, est le problème des trois chalets.
Graphe toroïdalright|frame| Un graphe plongé sur le tore de telle façon que les arêtes ne se coupent pas. En mathématiques, et plus précisément en théorie des graphes, un graphe G est toroïdal s'il peut être plongé sur le tore, c'est-à-dire que les sommets du graphe peuvent être placés sur le tore de telle façon que les arêtes ne se coupent pas. En général dire qu'un graphe est toroïdal sous-entend également qu'il n'est pas planaire.
Entrelacs (théorie des nœuds)En théorie des nœuds, un entrelacs est un enchevêtrement de plusieurs nœuds. L'étude des entrelacs et des nœuds est liée, plusieurs invariants s'interprétant plus naturellement dans le cadre général des entrelacs, au moyen notamment des relations d'écheveau. Un entrelacs est la donnée d'un plongement injectif d'une ou plusieurs copies du cercle S dans R ou dans S, appelées ses composantes, ou ses boucles. Deux entrelacs sont considérés équivalents lorsqu'ils sont identiques à isotopie près.
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.
Complément d'un nœudEn théorie des nœuds, une branche des mathématiques, le complément d'un nœud est l'espace tridimensionnel qui l'entoure. Plus précisément, dans une 3-variété M, si K est un nœud et N un voisinage tubulaire de K alors le complément X de K est le complémentaire de l'intérieur de N : La variété M considérée est le plus souvent (parfois même implicitement) la 3-sphère et K est supposé non . On définit de même le complément d'un entrelacs. Avec la définition ci-dessus, N est un tore plein, X est une 3-variété (compacte si M l'est), et leur frontière commune est un 2-tore.
Figure-eight knot (mathematics)In knot theory, a figure-eight knot (also called Listing's knot) is the unique knot with a crossing number of four. This makes it the knot with the third-smallest possible crossing number, after the unknot and the trefoil knot. The figure-eight knot is a prime knot. The name is given because tying a normal figure-eight knot in a rope and then joining the ends together, in the most natural way, gives a model of the mathematical knot.
