Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Install
Faster access than browser!
 

Hamiltonian path

Index Hamiltonian path

In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. [1]

77 relations: Abraham de Moivre, Algebraic structure, Øystein Ore, Barnette's conjecture, Biconnected graph, Bipartite graph, Cayley graph, Chessboard, Complete graph, Connectivity (graph theory), Coxeter group, Cubic graph, Cycle (graph theory), Cycle graph, Degree (graph theory), Dense graph, Directed graph, Distance (graph theory), Dodecahedron, Eulerian path, Fleischner's theorem, Forbidden subgraph problem, Gabriel Andrew Dirac, Glossary of graph theory terms, Graph (discrete mathematics), Graph power, Graph theory, Graph toughness, Gray code, Grinberg's theorem, Hamiltonian decomposition, Hamiltonian path problem, Hypohamiltonian graph, Icosian calculus, Icosian game, Indian mathematics, Induced path, Israel Journal of Mathematics, John Adrian Bondy, Journal of Combinatorial Theory, Knight's graph, Knight's tour, Lajos Pósa (mathematician), László Rédei, LCF notation, Leonhard Euler, Line graph, Lovász conjecture, Mathematics, Mathematics in medieval Islam, ..., NP-completeness, Ore's theorem, Pancyclic graph, Path (graph theory), Permutohedron, Petersen graph, Philosophical Magazine, Planar graph, Platonic solid, Polyhedral graph, Proceedings of the Royal Irish Academy, Quaternion, Root of unity, Rudrata, Shortness exponent, Snake-in-the-box, Steinhaus–Johnson–Trotter algorithm, Strongly connected component, Subhamiltonian graph, Tait's conjecture, Thomas Kirkman, Tournament (graph theory), Travelling salesman problem, Václav Chvátal, Vertex (graph theory), Vertex-transitive graph, William Rowan Hamilton. Expand index (27 more) »

Abraham de Moivre

Abraham de Moivre (26 May 166727 November 1754) was a French mathematician known for de Moivre's formula, a formula that links complex numbers and trigonometry, and for his work on the normal distribution and probability theory.

New!!: Hamiltonian path and Abraham de Moivre · See more »

Algebraic structure

In mathematics, and more specifically in abstract algebra, an algebraic structure on a set A (called carrier set or underlying set) is a collection of finitary operations on A; the set A with this structure is also called an algebra.

New!!: Hamiltonian path and Algebraic structure · See more »

Øystein Ore

Øystein Ore (7 October 1899 – 13 August 1968) was a Norwegian mathematician known for his work in ring theory, Galois connections, graph theory, and the history of mathematics.

New!!: Hamiltonian path and Øystein Ore · See more »

Barnette's conjecture

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs.

New!!: Hamiltonian path and Barnette's conjecture · See more »

Biconnected graph

In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected.

New!!: Hamiltonian path and Biconnected graph · See more »

Bipartite graph

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.

New!!: Hamiltonian path and Bipartite graph · See more »

Cayley graph

In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group.

New!!: Hamiltonian path and Cayley graph · See more »

Chessboard

A chessboard is the type of checkerboard used in the board game chess, consisting of 64 squares (eight rows and eight columns).

New!!: Hamiltonian path and Chessboard · See more »

Complete graph

No description.

New!!: Hamiltonian path and Complete graph · See more »

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to disconnect the remaining nodes from each other.

New!!: Hamiltonian path and Connectivity (graph theory) · See more »

Coxeter group

In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections (or kaleidoscopic mirrors).

New!!: Hamiltonian path and Coxeter group · See more »

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three.

New!!: Hamiltonian path and Cubic graph · See more »

Cycle (graph theory)

In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.

New!!: Hamiltonian path and Cycle (graph theory) · See more »

Cycle graph

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain.

New!!: Hamiltonian path and Cycle graph · See more »

Degree (graph theory)

In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.

New!!: Hamiltonian path and Degree (graph theory) · See more »

Dense graph

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges.

New!!: Hamiltonian path and Dense graph · See more »

Directed graph

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them.

New!!: Hamiltonian path and Directed graph · See more »

Distance (graph theory)

In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them.

New!!: Hamiltonian path and Distance (graph theory) · See more »

Dodecahedron

In geometry, a dodecahedron (Greek δωδεκάεδρον, from δώδεκα dōdeka "twelve" + ἕδρα hédra "base", "seat" or "face") is any polyhedron with twelve flat faces.

New!!: Hamiltonian path and Dodecahedron · See more »

Eulerian path

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph which visits every edge exactly once.

New!!: Hamiltonian path and Eulerian path · See more »

Fleischner's theorem

In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle.

New!!: Hamiltonian path and Fleischner's theorem · See more »

Forbidden subgraph problem

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph G, find the maximal number of edges in an n-vertex graph which does not have a subgraph isomorphic to G. In this context, G is called a forbidden subgraph.

New!!: Hamiltonian path and Forbidden subgraph problem · See more »

Gabriel Andrew Dirac

Gabriel Andrew Dirac (13 March 1925 – 20 July 1984) was a mathematician who mainly worked in graph theory.

New!!: Hamiltonian path and Gabriel Andrew Dirac · See more »

Glossary of graph theory terms

This is a glossary of graph theory terms.

New!!: Hamiltonian path and Glossary of graph theory terms · See more »

Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

New!!: Hamiltonian path and Graph (discrete mathematics) · See more »

Graph power

In graph theory, a branch of mathematics, the kth power Gk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k.

New!!: Hamiltonian path and Graph power · See more »

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

New!!: Hamiltonian path and Graph theory · See more »

Graph toughness

In graph theory, toughness is a measure of the connectivity of a graph.

New!!: Hamiltonian path and Graph toughness · See more »

Gray code

The reflected binary code (RBC), also known just as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).

New!!: Hamiltonian path and Gray code · See more »

Grinberg's theorem

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles.

New!!: Hamiltonian path and Grinberg's theorem · See more »

Hamiltonian decomposition

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles.

New!!: Hamiltonian path and Hamiltonian decomposition · See more »

Hamiltonian path problem

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected).

New!!: Hamiltonian path and Hamiltonian path problem · See more »

Hypohamiltonian graph

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

New!!: Hamiltonian path and Hypohamiltonian graph · See more »

Icosian calculus

The icosian calculus is a non-commutative algebraic structure discovered by the Irish mathematician William Rowan Hamilton in 1856.

New!!: Hamiltonian path and Icosian calculus · See more »

Icosian game

The icosian game is a mathematical game invented in 1857 by William Rowan Hamilton.

New!!: Hamiltonian path and Icosian game · See more »

Indian mathematics

Indian mathematics emerged in the Indian subcontinent from 1200 BC until the end of the 18th century.

New!!: Hamiltonian path and Indian mathematics · See more »

Induced path

In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem.

New!!: Hamiltonian path and Induced path · See more »

Israel Journal of Mathematics

Israel Journal of Mathematics is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem (Magnes Press).

New!!: Hamiltonian path and Israel Journal of Mathematics · See more »

John Adrian Bondy

John Adrian Bondy, (Born 1944) a dual British and Canadian citizen, was a professor of graph theory at the University of Waterloo, in Canada.

New!!: Hamiltonian path and John Adrian Bondy · See more »

Journal of Combinatorial Theory

The Journal of Combinatorial Theory, Series A and Series B, are mathematical journals specializing in combinatorics and related areas.

New!!: Hamiltonian path and Journal of Combinatorial Theory · See more »

Knight's graph

In graph theory, a knight's graph, or a knight's tour graph, is a graph that represents all legal moves of the knight chess piece on a chessboard.

New!!: Hamiltonian path and Knight's graph · See more »

Knight's tour

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once.

New!!: Hamiltonian path and Knight's tour · See more »

Lajos Pósa (mathematician)

Lajos Pósa (born December 9, 1947 in Budapest) is a Hungarian mathematician working in the topic of combinatorics, and one of the most prominent mathematics educators of Hungary, best known of his mathematics camps for gifted students.

New!!: Hamiltonian path and Lajos Pósa (mathematician) · See more »

László Rédei

László Rédei (Rákoskeresztúr, 15 November 1900—Budapest, 21 November 1980) was a Hungarian mathematician.

New!!: Hamiltonian path and László Rédei · See more »

LCF notation

In combinatorial mathematics, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle.

New!!: Hamiltonian path and LCF notation · See more »

Leonhard Euler

Leonhard Euler (Swiss Standard German:; German Standard German:; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, logician and engineer, who made important and influential discoveries in many branches of mathematics, such as infinitesimal calculus and graph theory, while also making pioneering contributions to several branches such as topology and analytic number theory.

New!!: Hamiltonian path and Leonhard Euler · See more »

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by although both and used the construction before this.

New!!: Hamiltonian path and Line graph · See more »

Lovász conjecture

In graph theory, the Lovász conjecture (1969) is a classical problem on Hamiltonian paths in graphs.

New!!: Hamiltonian path and Lovász conjecture · See more »

Mathematics

Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

New!!: Hamiltonian path and Mathematics · See more »

Mathematics in medieval Islam

Mathematics during the Golden Age of Islam, especially during the 9th and 10th centuries, was built on Greek mathematics (Euclid, Archimedes, Apollonius) and Indian mathematics (Aryabhata, Brahmagupta).

New!!: Hamiltonian path and Mathematics in medieval Islam · See more »

NP-completeness

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

New!!: Hamiltonian path and NP-completeness · See more »

Ore's theorem

Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore.

New!!: Hamiltonian path and Ore's theorem · See more »

Pancyclic graph

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph.

New!!: Hamiltonian path and Pancyclic graph · See more »

Path (graph theory)

In graph theory, a path in a graph is a finite or infinite sequence of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another.

New!!: Hamiltonian path and Path (graph theory) · See more »

Permutohedron

In mathematics, the permutohedron of order n (also spelled permutahedron) is an (n − 1)-dimensional polytope embedded in an n-dimensional space, the vertices of which are formed by permuting the coordinates of the vector (1, 2, 3,..., n).

New!!: Hamiltonian path and Permutohedron · See more »

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges.

New!!: Hamiltonian path and Petersen graph · See more »

Philosophical Magazine

The Philosophical Magazine is one of the oldest scientific journals published in English.

New!!: Hamiltonian path and Philosophical Magazine · See more »

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.

New!!: Hamiltonian path and Planar graph · See more »

Platonic solid

In three-dimensional space, a Platonic solid is a regular, convex polyhedron.

New!!: Hamiltonian path and Platonic solid · See more »

Polyhedral graph

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron.

New!!: Hamiltonian path and Polyhedral graph · See more »

Proceedings of the Royal Irish Academy

The Proceedings of the Royal Irish Academy (PRIA) is the journal of the Royal Irish Academy, founded in 1785 to promote the study of science, polite literature, and antiquities.

New!!: Hamiltonian path and Proceedings of the Royal Irish Academy · See more »

Quaternion

In mathematics, the quaternions are a number system that extends the complex numbers.

New!!: Hamiltonian path and Quaternion · See more »

Root of unity

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that gives 1 when raised to some positive integer power.

New!!: Hamiltonian path and Root of unity · See more »

Rudrata

Rudrata (रुद्रट) was a Kashmiri poet and literary theorist, who wrote a work called the Kavyalankara in the first quarter of the ninth century.

New!!: Hamiltonian path and Rudrata · See more »

Shortness exponent

In graph theory, the shortness exponent is a numerical parameter of a family of graphs that measures how far from Hamiltonian the graphs in the family can be.

New!!: Hamiltonian path and Shortness exponent · See more »

Snake-in-the-box

The snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube.

New!!: Hamiltonian path and Snake-in-the-box · See more »

Steinhaus–Johnson–Trotter algorithm

The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of n elements.

New!!: Hamiltonian path and Steinhaus–Johnson–Trotter algorithm · See more »

Strongly connected component

In the mathematical theory of directed graphs, a graph is said to be strongly connected or diconnected if every vertex is reachable from every other vertex.

New!!: Hamiltonian path and Strongly connected component · See more »

Subhamiltonian graph

In graph theory and graph drawing, a subhamiltonian graph is a subgraph of a planar Hamiltonian graph.

New!!: Hamiltonian path and Subhamiltonian graph · See more »

Tait's conjecture

In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices".

New!!: Hamiltonian path and Tait's conjecture · See more »

Thomas Kirkman

Thomas Penyngton Kirkman FRS (31 March 1806 – 3 February 1895) was a British mathematician and ordained minister of the Church of England.

New!!: Hamiltonian path and Thomas Kirkman · See more »

Tournament (graph theory)

A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph.

New!!: Hamiltonian path and Tournament (graph theory) · See more »

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

New!!: Hamiltonian path and Travelling salesman problem · See more »

Václav Chvátal

Václav (Vašek) Chvátal (is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Canada. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.

New!!: Hamiltonian path and Václav Chvátal · See more »

Vertex (graph theory)

In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).

New!!: Hamiltonian path and Vertex (graph theory) · See more »

Vertex-transitive graph

In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism such that In other words, a graph is vertex-transitive if its automorphism group acts transitively upon its vertices.

New!!: Hamiltonian path and Vertex-transitive graph · See more »

William Rowan Hamilton

Sir William Rowan Hamilton MRIA (4 August 1805 – 2 September 1865) was an Irish mathematician who made important contributions to classical mechanics, optics, and algebra.

New!!: Hamiltonian path and William Rowan Hamilton · See more »

Redirects here:

Bondy and Chvatal theorem, Bondy and Chvatal's theorem, Bondy and Chvátal theorem, Bondy and Chvátal's theorem, Bondy-Chvatal theorem, Bondy-Chvátal theorem, Bondy–Chvátal theorem, Dirac's theorem on Hamiltonian cycles, Directed Hamiltonian circuit, Hamilton circuit, Hamilton cycle, Hamilton graph, Hamilton path, Hamilton-connected, Hamilton-connected graph, Hamiltonian Cycle, Hamiltonian circuit, Hamiltonian cycle, Hamiltonian graph, Hamiltonian tour, Hamiltonicity, Rudrata cycle, Rudrata path, Traceable graph, Traceable path.

References

[1] https://en.wikipedia.org/wiki/Hamiltonian_path

OutgoingIncoming
Hey! We are on Facebook now! »