|
Berge's Lemma
In graph theory, Berge's theorem states that a matching ''M'' in a graph ''G'' is maximum (contains the largest possible number of edges) if and only if there is no augmenting path (a path that starts and ends on free (unmatched) vertices, and alternates between edges in and not in the matching) with ''M''. It was proven by French mathematician Claude Berge in 1957 (though already observed by Petersen in 1891 and Kőnig in 1931). Proof To prove Berge's theorem, we first need a lemma. Take a graph ''G'' and let ''M'' and ''M′'' be two matchings in ''G''. Let ''G′'' be the resultant graph from taking the symmetric difference of ''M'' and ''M′''; i.e. (''M'' - ''M′'') ∪ (''M′'' - ''M''). ''G′'' will consist of connected components that are one of the following: # An isolated vertex. # An even cycle whose edges alternate between ''M'' and ''M′''. # A path whose edges alternate between ''M'' and ''M′'', with distinct endpoints ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matching (graph Theory)
In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem. Definitions Given a graph a matching ''M'' in ''G'' is a set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share common vertices. A vertex is matched (or saturated) if it is an endpoint of one of the edges in the matching. Otherwise the vertex is unmatched (or unsaturated). A maximal matching is a matching ''M'' of a graph ''G'' that is not a subset of any other matching. A matching ''M'' of a graph ''G'' is maximal if every edge in ''G'' has a non-empty intersection with at least one edge in ''M''. The following figure shows examples of maximal matchings (red) in three graphs. : A maximum matching (also known as maximum-cardinality matching) is a matching that contains the largest possible number of edges. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph (discrete Mathematics)
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a Set (mathematics), set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
France
France (), officially the French Republic ( ), is a country primarily located in Western Europe. It also comprises of Overseas France, overseas regions and territories in the Americas and the Atlantic Ocean, Atlantic, Pacific Ocean, Pacific and Indian Oceans. Its Metropolitan France, metropolitan area extends from the Rhine to the Atlantic Ocean and from the Mediterranean Sea to the English Channel and the North Sea; overseas territories include French Guiana in South America, Saint Pierre and Miquelon in the North Atlantic, the French West Indies, and many islands in Oceania and the Indian Ocean. Due to its several coastal territories, France has the largest exclusive economic zone in the world. France borders Belgium, Luxembourg, Germany, Switzerland, Monaco, Italy, Andorra, and Spain in continental Europe, as well as the Kingdom of the Netherlands, Netherlands, Suriname, and Brazil in the Americas via its overseas territories in French Guiana and Saint Martin (island), ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Claude Berge
Claude Jacques Berge (5 June 1926 – 30 June 2002) was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. Biography and professional history Claude Berge's parents were André Berge and Geneviève Fourcade. André Berge (1902–1995) was a physician and psychoanalyst who, in addition to his professional work, had published several novels. He was the son of the René Berge, a mining engineer, and Antoinette Faure. Félix François Faure (1841–1899) was Antoinette Faure's father; he was President of France from 1895 to 1899. André Berge married Geneviève in 1924, and Claude was the second of their six children. His five siblings were Nicole (the eldest), Antoine, Philippe, Edith, and Patrick. Claude attended the near Verneuil-sur-Avre, about west of Paris. This famous private school, founded by the sociologist Edmond Demolins in 1899, attracted students from all over France to its innovative educational program. At this stage ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Julius Petersen
Julius Peter Christian Petersen (16 June 1839, Sorø, West Zealand – 5 August 1910, Copenhagen) was a Danish mathematician. His contributions to the field of mathematics led to the birth of graph theory. Biography Petersen's interests in mathematics were manifold, including: geometry, complex analysis, number theory, mathematical physics, mathematical economics, cryptography and graph theory. His famous paper ''Die Theorie der regulären graphs'' was a fundamental contribution to modern graph theory as we know it today. In 1898, he presented a counterexample to Tait's claimed theorem about 1-factorability of 3-regular graphs, which is nowadays known as the " Petersen graph". In cryptography and mathematical economics he made contributions which today are seen as pioneering. He published a systematic treatment of geometrical constructions (with straightedge and compass) in 1880. A French translation was reprinted in 1990. A special issue of Discrete Mathematic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dénes Kőnig
Dénes Kőnig (September 21, 1884 – October 19, 1944) was a Hungarian mathematician of Jewish heritage who worked in and wrote the first textbook on the field of graph theory. Biography Kőnig was born in Budapest, the son of mathematician Gyula Kőnig. In 1907, he received his doctorate Translated by Richard McCoart; with commentary by W.T. Tutte. at, and joined the faculty of the Royal Joseph University in Budapest (today Budapest University of Technology and Economics). His classes were visited by Paul Erdős, who, as a first year student, solved one of his problems. Kőnig became a full professor there in 1935. To honor his fathers' death in 1913, Kőnig and his brother György created the Gyula Kőnig prize in 1918. This prize was meant to be an endowment for young mathematicians, however was later devaluated. But the prize remained as a medal of high scientific recognition. In 1899, he published his first work while still attending High School in a journal ''Matematikai ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lemma (mathematics)
In mathematics, informal logic and argument mapping, a lemma (plural lemmas or lemmata) is a generally minor, proven proposition which is used as a stepping stone to a larger result. For that reason, it is also known as a "helping theorem" or an "auxiliary theorem". In many cases, a lemma derives its importance from the theorem it aims to prove; however, a lemma can also turn out to be more important than originally thought. The word "lemma" derives from the Ancient Greek ("anything which is received", such as a gift, profit, or a bribe). Comparison with theorem There is no formal distinction between a lemma and a theorem, only one of intention (see Theorem terminology). However, a lemma can be considered a minor result whose sole purpose is to help prove a more substantial theorem – a step in the direction of proof. Well-known lemmas A good stepping stone can lead to many others. Some powerful results in mathematics are known as lemmas, first named for their originally min ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Symmetric Difference
In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \. The symmetric difference of the sets ''A'' and ''B'' is commonly denoted by A \ominus B, or A\operatorname \triangle B. The power set of any set becomes an abelian group under the operation of symmetric difference, with the empty set as the neutral element of the group and every element in this group being its own inverse. The power set of any set becomes a Boolean ring, with symmetric difference as the addition of the ring and intersection as the multiplication of the ring. Properties The symmetric difference is equivalent to the union of both relative complements, that is: :A\,\triangle\,B = \left(A \setminus B\right) \cup \left(B \setminus A\right), The symmetric difference can also be expressed using the XOR operation ⊕ on t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vertex (graph Theory)
In discrete 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). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another. From the point of view of graph theory, vertices are treated as featureless and indivisible objects, although they may have additional structure depending on the application from which the graph arises; for instance, a semantic network is a graph in which the vertices represent concepts or classes of objects. The two vertices forming an edge are said to be the endpoints of this edge, and the edge is said to be incident to the vertices. A vertex ''w'' is said to be ad ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cycle (graph Theory)
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an ''acyclic graph''. A directed graph without directed cycles is called a ''directed acyclic graph''. A connected graph without cycles is called a ''tree''. Definitions Circuit and cycle * A circuit is a non-empty trail in which the first and last vertices are equal (''closed trail''). : Let be a graph. A circuit is a non-empty trail with a vertex sequence . * A cycle or simple circuit is a circuit in which only the first and last vertices are equal. Directed circuit and directed cycle * A directed circuit is a non-empty directed trail in which the first and last vertices are equal (''closed directed trail''). : Let be a directed graph. A directed circuit is a non-empty directed trail with a vertex sequence ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Path (graph Theory)
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes called dipathGraph Structure Theory: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graph Minors, Held June 22 to July 5, 1991p.205/ref>) in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction. Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See e.g. Bondy and Murty (1976), Gibbons (1985), or Diestel (2005). Korte et al. (1990) cover more advanced algorithmic topics concerning paths in graphs. Definitions Walk, trail, and path * A walk is a finite or infinite sequence of edges which joins a sequence of vertices. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
