|
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. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete. Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the icosian game, now also known as ''Hamilton's puzzle'', which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the icosian calculus, an algebraic structure based on roots of unity with many similarities to the quaternions (also invented by Hami ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Icosian Game
The icosian game is a mathematical game invented in 1857 by William Rowan Hamilton. The game's object is finding a Hamiltonian cycle along the edges of a dodecahedron such that every vertex is visited a single time, and the ending point is the same as the starting point. The puzzle was distributed commercially as a pegboard with holes at the nodes of the dodecahedral graph and was subsequently marketed in Europe in many forms. The motivation for Hamilton was the problem of symmetries of an icosahedron, for which he invented icosian calculus—an algebraic tool to compute the symmetries. The solution of the puzzle is a cycle containing twenty (in ancient Greek ''icosa'') edges (i.e. a Hamiltonian circuit on the dodecahedron). See also * Hunt the Wumpus * Dual polyhedron * Seven Bridges of Königsberg The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1736 laid the foundations of graph theory and pre ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hamiltonian
Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian with two-electron nature ** Molecular Hamiltonian, the Hamiltonian operator representing the energy of the electrons and nuclei in a molecule * Hamiltonian (control theory), a function used to solve a problem of optimal control for a dynamical system * Hamiltonian path, a path in a graph that visits each vertex exactly once * Hamiltonian group, a non-abelian group the subgroups of which are all normal * Hamiltonian economic program, the economic policies advocated by Alexander Hamilton, the first United States Secretary of the Treasury See also * Alexander Hamilton (1755 or 1757–1804), American statesman and one of the Founding Fathers of the US * Hamilton (other) Hamilton may refer to: People * Hamilton (name), a common ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tournament (graph Theory)
A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. That is, it is an orientation of a complete graph, or equivalently a directed graph in which every pair of distinct vertices is connected by a directed edge (often, called an arc) with any one of the two possible orientations. Many of the important properties of tournaments were first investigated by H. G. Landau in to model dominance relations in flocks of chickens. Current applications of tournaments include the study of voting theory and social choice theory among other things. The name ''tournament'' originates from such a graph's interpretation as the outcome of a round-robin tournament in which every player encounters every other player exactly once, and in which no draws occur. In the tournament digraph, the vertices correspond to the players. The edge between each pair of players is oriented from the winner to the loser. If player a beats player b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called . The number of vertices in equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it. Terminology There are many synonyms for "cycle graph". These include simple cycle graph and cyclic graph, although the latter term is less often used, because it can also refer to graphs which are merely not acyclic. Among graph theorists, cycle, polygon, or ''n''-gon are also often used. The term ''n''-cycle is sometimes used in other settings. A cycle with an even number of vertices is called an even cycle; a cycle with an odd number of vertices is called an odd cycle. Properties A cycle graph is: * 2-edge colorable, if and only if it has an even number of vertices * 2-regular * 2-ve ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction). Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull. Such a drawing is sometimes referred to as a mystic rose. Properties The complete graph on vertices is denoted by . Some sources claim that the letter in this notation stands for the German word , but the German name for a complete graph, , does not contain the letter , and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory. has edges (a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected. Necessary conditions For a Hamiltonian decomposition to exist in an undirected graph, the graph must be connected and regular of even degree. A directed graph with such a decomposition must be strongly connected and all vertices must have the same in-degree and out-degree as each other, but this degree does not need to be even. Special classes of graphs Complete graphs Every complete graph with an odd number n of vertices has a Hamiltonian decomposition. This result, which is a special case of the Oberwolfach problem of decomposing complete graphs into isomorphic 2-factors, was attributed to W ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Directed Graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pair where * ''V'' is a set whose elements are called '' vertices'', ''nodes'', or ''points''; * ''A'' is a set of ordered pairs of vertices, called ''arcs'', ''directed edges'' (sometimes simply ''edges'' with the corresponding set named ''E'' instead of ''A''), ''arrows'', or ''directed lines''. It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, which are usually called ''edges'', ''links'' or ''lines''. The aforementioned definition does not allow a directed graph to have multiple arrows with the same source and target nodes, but some authors consider a broader definition that allows directed graphs to have such multiple arcs (namely, they allow the arc set to be a m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Leonhard Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in many other branches of mathematics such as analytic number theory, complex analysis, and infinitesimal calculus. He introduced much of modern mathematical terminology and notation, including the notion of a mathematical function. He is also known for his work in mechanics, fluid dynamics, optics, astronomy and music theory. Euler is held to be one of the greatest mathematicians in history and the greatest of the 18th century. A statement attributed to Pierre-Simon Laplace expresses Euler's influence on mathematics: "Read Euler, read Euler, he is the master of us all." Carl Friedrich Gauss remarked: "The study of Euler's works will remain the best school for the different fields of mathematics, and nothing else can replace it." Euler is a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Abraham De Moivre
Abraham de Moivre FRS (; 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. He moved to England at a young age due to the religious persecution of Huguenots in France which reached a climax in 1685 with the Edict of Fontainebleau. He was a friend of Isaac Newton, Edmond Halley, and James Stirling. Among his fellow Huguenot exiles in England, he was a colleague of the editor and translator Pierre des Maizeaux. De Moivre wrote a book on probability theory, ''The Doctrine of Chances'', said to have been prized by gamblers. De Moivre first discovered Binet's formula, the closed-form expression for Fibonacci numbers linking the ''n''th power of the golden ratio ''φ'' to the ''n''th Fibonacci number. He also was the first to postulate the central limit theorem, a cornerstone of probability theory. Life Early years Abraham ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Al-Adli Ar-Rumi
Al-Adli al-Rumi (), was an Arab player and theoretician of Shatranj, an ancient form of chess from Persia. Originally from Anatolia, he authored one of the first treatises on Shatranj in 842, called ''Kitab ash-shatranj'' ('Book of Chess'). He was recognized as the best Shatranj player in the 9th century during the reign of al-Wathiq until his loss to al-Razi, just before or early into the reign of al-Mutawakkil. In his treatise al-Adli compiled the ideas of his predecessors on Shatranj. The book was lost but the problems he discussed survived in the works of successors. Mansūbāt were end game scenarios, where victory was obtained either by checkmate or stalemate Stalemate is a situation in the game of chess where the player whose turn it is to move is not in check and has no legal move. Stalemate results in a draw. During the endgame, stalemate is a resource that can enable the player with the inferior ..., or by baring the opposing king. From his work came a variant of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 of Perga, Apollonius) and Indian mathematics (Aryabhata, Brahmagupta). Important progress was made, such as full development of the decimal place-value system to include decimal fractions, the first systematised study of algebra, and advances in geometry and trigonometry. Arabic works played an important role in the transmission of mathematics to Europe during the 10th—12th centuries. Concepts Algebra The study of algebra, the name of which is derived from the Arabic language, Arabic word meaning completion or "reunion of broken parts", flourished during the Islamic golden age. Muhammad ibn Musa al-Khwarizmi, a Persian scholar in the House of Wisdom in Baghdad was the founder of algebra, is along with the Greek people, Greek mathematician Diophantus, known as the father of algebra. In his book ''The Compendious Book on ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
