|
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. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details. 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Icosian Game
The icosian game is a mathematical game invented in 1856 by Irish mathematician William Rowan Hamilton. It involves finding a Hamiltonian cycle on a dodecahedron, a polygon using edges of the dodecahedron that passes through all its vertex (geometry), vertices. Hamilton's invention of the game came from his studies of symmetry, and from his invention of the icosian calculus, a mathematical system describing the symmetries of the dodecahedron. Hamilton sold his work to a game manufacturing company, and it was marketed both in the UK and Europe, but it was too easy to become commercially successful. Only a small number of copies of it are known to survive in museums. Although Hamilton was not the first to study Hamiltonian cycles, his work on this game became the origin of the name of Hamiltonian cycles. Several works of recreational mathematics studied his game. Other puzzles based on Hamiltonian cycles are sold as smartphone apps, and mathematicians continue to study combinatori ... [...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 matrix, a matrix with certain special properties commonly used in linear algebra * 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. Each vertex of this graph represents a square of the chessboard, and each edge connects two squares that are a knight's move apart from each other. More specifically, an m \times n knight's graph is a knight's graph of an m \times n chessboard.. Its vertices can be represented as the points of the Euclidean plane whose Cartesian coordinates (x,y) are integers with 1\le x\le m and 1\le y\le n (the points at the centers of the chessboard squares), and with two vertices connected by an edge when their Euclidean distance is \sqrt. For an m \times n knight's graph, the number of vertices is nm. If m>1 and n>1 then the number of edges is 4mn-6(m+n)+8 (otherwise there are no edges). For an n \times n knight's graph, these simplify so that the number of vertices is n^2 and the number of edges is 4(n-2)(n-1). A Hamiltonian cycle on the knight' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tournament (graph Theory)
In graph theory, a tournament is a directed graph with exactly one edge between each two vertices, in one of the two possible directions. Equivalently, a tournament is an orientation of an undirected complete graph. (However, as directed graphs, tournaments are not complete: complete directed graphs have two edges, in both directions, between each two vertices.) Equivalently, a tournament is a complete asymmetric relation. The name ''tournament'' comes from interpreting the graph as the outcome of a round-robin tournament, a game where each player is paired against every other exactly once. In a tournament, the vertices represent the players, and the edges between players point from the winner to the loser. Many of the important properties of tournaments were investigated by H. G. Landau in 1953 to model dominance relations in flocks of chickens. Tournaments are also heavily studied in voting theory, where they can represent partial information about voter preferences am ... [...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. If n = 1, it is an isolated loop. 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 n ... [...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 edg ... [...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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Leonhard Euler
Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential discoveries in many other branches of mathematics, such as analytic number theory, complex analysis, and infinitesimal calculus. He also introduced much of modern mathematical terminology and Mathematical notation, notation, including the notion of a mathematical function. He is known for his work in mechanics, fluid dynamics, optics, astronomy, and music theory. Euler has been called a "universal genius" who "was fully equipped with almost unlimited powers of imagination, intellectual gifts and extraordinary memory". He spent most of his adult life in Saint Petersburg, Russia, and in Berlin, then the capital of Kingdom of Prussia, Prussia. Euler is credited for popularizing the Greek letter \pi (lowercase Pi (letter), pi) to denote Pi, th ... [...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 (mathematician), 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 theo ... [...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 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 position ..., 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 upon syntheses of Greek mathematics (Euclid, Archimedes, Apollonius) and Indian mathematics (Aryabhata, Brahmagupta). Important developments of the period include extension of the place-value system to include decimal fractions, the systematised study of algebra and advances in geometry and trigonometry. The medieval Islamic world underwent significant developments in mathematics. Muhammad ibn Musa al-Khwārizmī played a key role in this transformation, introducing algebra as a distinct field in the 9th century. Al-Khwārizmī's approach, departing from earlier arithmetical traditions, laid the groundwork for the arithmetization of algebra, influencing mathematical thought for an extended period. Successors like Al-Karaji expanded on his work, contributing to advancements in various mathematical domains. The practicality and broad applicability of these mathematical metho ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
