|
Folded Cube Graph
In graph theory, a folded cube graph is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects ''opposite'' pairs of hypercube vertices. Construction The folded cube graph of dimension ''k'' (containing 2''k'' − 1 vertices) may be formed by adding edges between opposite pairs of vertices in a hypercube graph of dimension ''k'' − 1. (In a hypercube with 2''n'' vertices, a pair of vertices are ''opposite'' if the shortest path between them has length ''n''.) It can, equivalently, be formed from a hypercube graph (also) of dimension ''k'', which has twice as many vertices, by identifying together (or contracting) every opposite pair of vertices. Properties A dimension-''k'' folded cube graph is a ''k''- regular with 2''k'' − 1 vertices and 2''k'' − 2''k'' edges. The chromatic number of the dimension-''k'' folded cube graph is two when ''k'' is even (that is, in this case, t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clebsch Hypercube
Rudolf Friedrich Alfred Clebsch (19 January 1833 – 7 November 1872) was a German mathematician who made important contributions to algebraic geometry and invariant theory. He attended the University of Königsberg and was habilitated at Berlin. He subsequently taught in Berlin and Karlsruhe. His collaboration with Paul Gordan in Giessen led to the introduction of Clebsch–Gordan coefficients for spherical harmonics, which are now widely used in quantum mechanics. Together with Carl Neumann at Göttingen, he founded the mathematical research journal '' Mathematische Annalen'' in 1868. In 1883 Saint-Venant translated Clebsch's work on elasticity into French and published it as ''Théorie de l'élasticité des Corps Solides''. Books by A. Clebsch Vorlesungen über Geometrie(Teubner, Leipzig, 1876-1891) edited by Ferdinand Lindemann. Théorie der binären algebraischen Formen(Teubner, 1872) Theorie der Abelschen Functionenwith P. Gordan (B. G. Teubner, 1866) Theorie der Elas ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bipartite Double Cover
In graph theory, the bipartite double cover of an undirected graph is a bipartite, covering graph of , with twice as many vertices as . It can be constructed as the tensor product of graphs, . It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of . It should not be confused with a cycle double cover of a graph, a family of cycles that includes each edge twice. Construction The bipartite double cover of has two vertices and for each vertex of . Two vertices and are connected by an edge in the double cover if and only if and are connected by an edge in . For instance, below is an illustration of a bipartite double cover of a non-bipartite graph . In the illustration, each vertex in the tensor product is shown using a color from the first term of the product () and a shape from the second term of the product (); therefore, the vertices in the double cover are shown as circles while the vertices are shown as squares. : ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Halved Cube Graph
In graph theory, the halved cube graph or half cube graph of dimension is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square of the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph. Equivalent constructions The construction of the halved cube graph can be reformulated in terms of binary numbers. The vertices of a hypercube may be labeled by binary numbers in such a way that two vertices are adjacent exactly when they differ in a single bit. The demicube may be constructed from the hypercube as the convex hull of the subset of binary numbers with an even number of nonzero bits (the evil numbers), and its edges connect pairs of numbers whose Hamming distance is exactly two. It is also possible to construct the halved cube graph from a lower-dimensional hypercube graph, wit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distributed Algorithm
A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific computing, distributed information processing, and real-time process control. Standard problems solved by distributed algorithms include leader election, consensus, distributed search, spanning tree generation, mutual exclusion, and resource allocation. Distributed algorithms are a sub-type of parallel algorithm, typically executed concurrently, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing. One of the major challenges in developing and implementing distributed algorithms is successfully coordinating the behavior of the independent parts of the algorithm in the face of processor failures and unreliable communic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. This is also known as the geodesic distance or shortest-path distance. Notice that there may be more than one shortest path between two vertices. If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite. In the case of a directed graph the distance between two vertices and is defined as the length of a shortest directed path from to consisting of arcs, provided at least one such path exists. Notice that, in contrast with the case of undirected graphs, does not necessarily coincide with —so it is just a quasi-metric, and it might be the case that one is defined while the other is not. Related concepts A metric space defined over a set of points in terms of distances in a graph defined over ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Network Topology
Network topology is the arrangement of the elements ( links, nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, including command and control radio networks, industrial fieldbusses and computer networks. Network topology is the topological structure of a network and may be depicted physically or logically. It is an application of graph theory wherein communicating devices are modeled as nodes and the connections between the devices are modeled as links or lines between the nodes. Physical topology is the placement of the various components of a network (e.g., device location and cable installation), while logical topology illustrates how data flows within a network. Distances between nodes, physical interconnections, transmission rates, or signal types may differ between two different networks, yet their logical topologies may be identical. A network’s physical topology ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parallel Computing
Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different forms of parallel computing: bit-level, instruction-level, data, and task parallelism. Parallelism has long been employed in high-performance computing, but has gained broader interest due to the physical constraints preventing frequency scaling.S.V. Adve ''et al.'' (November 2008)"Parallel Computing Research at Illinois: The UPCRC Agenda" (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits—increased clock frequency and smarter but increasingly complex architectures—are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather tha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kummer Configuration
In geometry, the Kummer configuration, named for Ernst Kummer, is a geometric configuration of 16 points and 16 planes such that each point lies on 6 of the planes and each plane contains 6 of the points. Further, every pair of points is incident with exactly two planes, and every two planes intersect in exactly two points. The configuration is therefore a biplane, specifically, a 2−(16,6,2) design. The 16 nodes and 16 tropes of a Kummer surface form a Kummer configuration. There are three different non-isomorphic ways to select 16 different 6-sets from 16 elements satisfying the above properties, that is, forming a biplane. The most symmetric of the three is the Kummer configuration, also called "the best biplane" on 16 points. Construction Following the method of Jordan (1869), but see also Assmus and Sardi (1981), arrange the 16 points (say the numbers 1 to 16) in a 4x4 grid. For each element in turn, take the 3 other points in the same row and the 3 other points in the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kummer Graph
Kummer is a German surname. Notable people with the surname include: * Bernhard Kummer (1897–1962), German Germanist *Clare Kummer (1873—1958), American composer, lyricist and playwright *Clarence Kummer (1899–1930), American jockey * Christopher Kummer (born 1975), German economist *Corby Kummer (born 1957), American journalist * Dirk Kummer (born 1966), German actor, director, and screenwriter * Eberhard Kummer (1940–2019), Austrian concert singer, lawyer, and medieval music expert * Eduard Kummer, also known as the following Ernst Kummer * Eloise Kummer (1916–2008), American actress *Ernst Kummer (1810–1893), German mathematician **Kummer configuration, a mathematical structure discovered by Ernst Kummer ** Kummer surface, a related geometrical structure discovered by Ernst Kummer * Ferdinand von Kummer (1816-1900), German general *Frederic Arnold Kummer (1873–1943), American author, playwright, and screenwriter * Friedrich August Kummer (1797–1879), German celli ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Bipartite Graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. 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 bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher. Llull himself had made similar drawings of complete graphs three centuries earlier.. Definition A complete bipartite graph is a graph whose vertices can be partitioned into two subsets and such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph such that for every two vertices and, is an edge in . A complete bipartite graph wit ... [...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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Binary Tree
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (''L'', ''S'', ''R''), where ''L'' and ''R'' are binary trees or the empty set and ''S'' is a singleton set containing the root. Some authors allow the binary tree to be the empty set as well. From a graph theory perspective, binary (and K-ary) trees as defined here are arborescences. A binary tree may thus be also called a bifurcating arborescence—a term which appears in some very old programming books, before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an undirected, rather than a directed graph, in which case a binary tree is an ordered, rooted tree. Some authors use rooted binary tree instead of ''binary tree'' to emphasize the fact that the tree is rooted, but ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
