Graphe de Tietze

In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are embedded onto the Möbius strip may require six colors. The boundary segments of the regions of Tietze's subdivision (including the segments along the boundary of the Möbius strip itself) form an embedding of Tietze's graph. Tietze's graph may be formed from the Petersen graph by replacing one of its vertices with a triangle. Like the Tietze graph, the Petersen graph forms the boundary of six mutually touching regions, but on the projective plane rather than on the Möbius strip. If one cuts a hole from this subdivision of the projective plane, surrounding a single vertex, the surrounded vertex is replaced by a triangle of region boundaries around the hole, giving the previously described construction of the Tietze graph. Both Tietze's graph and the Petersen graph are maximally nonhamiltonian: they have no Hamiltonian cycle, but any two non-adjacent vertices can be connected by a Hamiltonian path. Tietze's graph and the Petersen graph are the only 2-vertex-connected cubic non-Hamiltonian graphs with 12 or fewer vertices. Unlike the Petersen graph, Tietze's graph is not hypohamiltonian: removing one of its three triangle vertices forms a smaller graph that remains non-Hamiltonian. Edge coloring Tietze's graph requires four colors; that is, its chromatic index is 4. Equivalently, the edges of Tietze's graph can be partitioned into four matchings, but no fewer. Tietze's graph matches part of the definition of a snark: it is a cubic bridgeless graph that is not 3-edge-colorable. However, most authors restrict snarks to graphs without 3-cycles, so Tietze's graph is not generally considered to be a snark.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Unités associées (1)

Concepts associés (3)

Séances de cours associées (4)

Graphe hypohamiltonien

En théorie des graphes, un graphe est hypohamiltonien s'il n'a pas de cycle hamiltonien mais que la suppression de n'importe quel sommet du graphe suffit à le rendre hamiltonien. Les graphes hypohamiltoniens furent étudiés pour la première fois par Sousselier en 1963 dans Problèmes plaisants et délectables. Sous forme d'une petite énigme la notion est introduite. L'énoncé demande de trouver un tel graphe d'ordre 10 (le graphe de Petersen) et de prouver que cet ordre est minimal, c'est-à-dire qu'il n'existe pas de graphe hypohamiltonien à moins de 10 sommets.

Snark (graphe)

En théorie des graphes, une branche des mathématiques, un snark est un graphe cubique connexe, sans isthme et d'indice chromatique égal à 4. En d'autres termes, c'est un graphe dans lequel chaque sommet a trois voisins, et dont les arêtes ne peuvent pas être colorées avec seulement 3 couleurs sans que deux arêtes de même couleur ne se rencontrent en un même sommet (d'après le théorème de Vizing, l'indice chromatique d'un graphe cubique est 3 ou 4). Pour éviter les cas triviaux, on exige souvent de plus que les snarks aient une maille d'au moins 5.

Graphe de Petersen

Le graphe de Petersen est, en théorie des graphes, un graphe particulier possédant et . Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois auparavant, en 1886.

Robust Non-Rigid Registration of 2D and 3D Graphs

Pascal Fua, Jan Kybic, Przemyslaw Rafal Glowacki

We present a new approach to matching graphs embedded in R2 or R3. Unlike earlier methods, our approach does not rely on the similarity of local appearance features, does not require an initial alignment, can handle partial matches, and can cope with non-l ...

2012

Couvre les bases des fonctions, y compris l'injectivité, la surjectivité et la bijectivité, ainsi que les preuves par induction.

S'inscrit dans l'équilibre complexe entre l'énergie, les besoins humains et la durabilité, soulignant l'importance de satisfaire les besoins humains dans les limites des contraintes écologiques.

Présentation de K-Means Clustering, un algorithme simple mais efficace pour regrouper des points de données en clusters.