DeBruijin Diagrams/Shift Register GraphsDate: 10/30/2001 at 12:53:05 From: Anthony Di Bona Subject: Graphing Theory - DeBruijin Diagrams/Shift Register Graphs We are currently studying de Bruijin diagrams and shift register sequences. I've been able to draw some simple examples e.g. D(2,4) for 'p' letters = 2 and words of length 'n' = 4. I just know there must be a general layout to these things to make them more elegant looking. My specific problem is how to graph D(3,3) and then come up with a shift register sequence from that graph. I know the idea is to connect an arc from word b1b2...bn-1 to every word of the form b2b3...bn. With 27 arcs coming off 9 vertices, things get out of hand fairly quickly. Is there a shape I should be aiming for? Date: 10/31/2001 at 03:14:28 From: Doctor Pete Subject: Re: Graphing Theory - DeBruijin Diagrams/Shift Register Graphs Hi, I assume that the problem here is not really about the structure of the graph, but rather how to draw the graph in a way that reveals its structure more clearly. The other part of the question, i.e., finding a de Bruijn sequence from the graph, is not too hard because there are many to choose from, and all it amounts to is finding an Eulerian circuit on the corresponding digraph. That said, the particular way I want you to arrange the nine vertices {00, 01, 02, 10, 11, 12, 20, 21, 22} is to imagine them on the Cartesian plane with the following coordinates: 00: (0,0) 11: (0,2) 22: (0,-2) 10: (1,1) 21: (1,0) 02: (1,-1) 01: (-1,1) 12: (-1,0) 20: (-1,-1). There is a certain logic to this arrangement, because we can now easily draw the following directed edges, which are straight lines: 001: (0,0) -> (-1,1) 002: (0,0) -> (1,-1) 100: (1,1) -> (0,0) 200: (-1,-1) -> (0,0), 010: (-1,1) -> (1,1) 101: (1,1) -> (-1,1) 202: (-1,-1) -> (1,-1) 020: (1,-1) -> (-1,-1), and so forth, the other segments being 012, 120, 021, 210, 110, 011, 220, 022. These are pretty obvious. The next ones are also straight line segments, but they cross over the previously drawn edges: 122, 221, 211, 112. The next 4 edges are curved, but are not difficult to draw in a systematic/symmetrical way: 121, 212, 102, 201. The remaining 3 edges are the loops: 000, 111, 222. You may verify that we have enumerated all 3^3 edges. You may also verify that each vertex, as drawn, has in-degree 3 and out-degree 3. I'd say this is about the clearest way to draw this particular graph. From here it is not difficult to find an Eulerian circuit by trial and error. This I leave up to you. - Doctor Pete, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/