Clearly, the two words in the Gray code sequence form a cycle. The trivial case is when words have a length of one. Cyclic Gray code can be inductively produced through reflected binary code. Thus, a Gray code cycle consisting of words of length n contains all the 2 n possible bit string combinations. Cyclic Gray Code A finite Gray code sequence is called cyclic if the transition between the last word of the sequence and the first is a single bit exchange that is the first and last strings differ by a single binary digit. Rather, Gray code is produced by applying the exclusive-or operation to consecutive bits of the equivalent binary number (Table. Where the binary counting system, like the decimal counting system, places the value of a bit or number on the digit’s position, Gray code does not. Gray code is a binary counting system in which consecutive numbers differ by a single bit. Gray Code Tightly coupled with the notion of binary counting is that of Gray Code. A layered Q 3 graph with M 3 outlined in the centerģ. Definition 6 (Word or String) The terms word and string are used interchangeably to refer to a binary number consisting of a sequence of zeros and ones.įigure 2. Definition 5 (Middle Level Graph) The middle layer graph, denoted, is a subgraph of containing the vertices in levels and (Fig. The level of the hypercube refers to the set of vertices of which contain I ones in their vertex string (Fig. Definition 4 (Vertex Levels of a Hypercube) When mapped to a coordinate axis, each vertex of a hypercube,, can be assigned a binary string of length n. Definition 3 (Hamiltonian Cycle) In a graph, a cycle c of, which contains every vertex of once, is said to be a Hamiltonian cycle, and for this reason, is called a Hamiltonian graph. Hypercubes of the first, second and third dimensionĭefinition 2 (Hamiltonian Path) In a graph a path that contains every vertex of once is referred to as a Hamiltonian Path. These graphs are denoted by, where n is the dimension (Fig. For the purpose of this paper it should be noted that all hypercubes refer to binary n-dimensional graphs. Definitions and Notations Definition 1 (Hypercube) A hypercube is the graphical representation of the edges and vertices in a single volumetric unit in any dimension n. Finally, this paper will look into how queue Gray codes can be used to search for paths and cycles within middle level graphs and the results of queue Gray code and antipodal tests on known Hamiltonian paths within various middle level graphs. This paper takes a look at various properties of the hypercube and the middle level graph as well as the use of Gray codes to develop some of these properties. As of 2006, with the aid of technology, and were the largest graphs of this nature to be proved to contain Hamiltonian cycles. There are a few strategies which can be used to disprove the existence of such cycles, but the middle level graph, as little effort will show, fails on these accounts. The difficulty in solving the problem is undoubtedly due in part to the unclear nature of Hamiltonian cycles in general, for there is no known method to prove the existence of a Hamiltonian cycle in a graph. The conjecture states that for every odd n-dimensional hypercube for, there exists a Hamiltonian cycle in the graph of the middle layers of the hypercube. First proposed in the 1980’s by Ivan Havel, the Middle Level Conjecture, under the name “The Revolving Door Conjecture” remains an open problem in mathematics unanimously thought to be true. The question of whether particular subgraphs of the hypercube are Hamiltonian is less clear. It is well known that these graphs are Hamiltonian. Introduction A hypercube, sometimes referred to as a n-cube, is the graphical representation of the edges and vertices in a single volumetric unit in any dimension n.
Yun, S.-K., Park, K.-H.: Comments on 'Hierarchical Cubic Networks'.Parhami, B., Kwai, D.-M.: A Unified Formulation of Honeycomb and Diamond Networks.Lai, C.-N., Chen, G.-H., Duh, D.-R.: Constructing One-to-Many Disjoint Paths in Folded Hypercubes.Harary, F., Hayes, J.P., Wu, H.-J.: A Survey of the Theory of Hypercube Graphs.Efe, K.: A Variation on the Hypercube with Lower Diameter.Akers, S.B., Krishnamurthy,B.: A Group-Theoretic Model for Symmetric Interconnection Network.Akers, S.B., Harel, D., Krishnamurthy, B.: The Star Graph: An Attractive Alternative to The n-Cube.Abraham, S.: The Twisted Cube Topology for Multiprocessor: A Study in Network Asymmetry.
0 kommentar(er)
