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.
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.
Kuratowski's theoremIn graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of (the complete graph on five vertices) or of (a complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph).
Homéomorphisme de graphesEn théorie des graphes, une branche des mathématiques, deux graphes et sont homéomorphes si l'on peut obtenir un même graphe en subdivisant certaines de leurs arêtes. Deux graphes sont homéomorphes si et seulement si leurs représentations graphiques usuelles (avec des segments de droites reliant les sommets entre eux) sont homéomorphes au sens que ce mot a en topologie. Subdivision La subdivision d'une arête conduit à un graphe contenant un nouveau sommet et où l'on a remplacé l'arête par deux nouvelles arêtes, et .
Énigme des trois maisonsL'énigme des trois maisons, aussi appelée l'énigme de l'eau, du gaz et de l'électricité, est un jeu mathématique dont l'analyse utilise un théorème de topologie ou de théorie des graphes. Ce problème n'a pas de solution. Georges Perec le cite en 1978 dans son livre Je me souviens : . Cette énigme est déjà posée par Henry Dudeney en 1917 dans son livre Amusements in mathematics. Il précise qu'. Celle de l'article en est une, qu'il appelle eau, gaz, et électricité.
