Talk:De Bruijn graph

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. Low This article has been rated as Low-priority on the project's priority scale. ‹See TfM› Physics Low‑importance Physics portal This article is within the scope of WikiProject Physics, a collaborative effort to improve the coverage of Physics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks. Low This article has been rated as Low-importance on the project's importance scale. Systems Mid‑importance Systems science portal This article is within the scope of WikiProject Systems, which collaborates on articles related to systems and systems science. Mid This article has been rated as Mid-importance on the project's importance scale. This article is within the field of Dynamical systems.

Vertices

Could someone describe the set of vertices a bit more clearly please? It is not clear from the example exactly what the pattern is.

Actually the same goes for the Edges abstract example following. It is not at all clear what this means as the description permits ambiguity.

— Preceding unsigned comment added by 149.157.246.18 (talk) 09:42, 23 February 2012 (UTC)

Discovered???

Didn't I read somewhere that mathematics can't be discovered? I mean graphs aren't exactly like animal species where they're waiting in some ethereal plane to be discovered by mathematicians. —Preceding unsigned comment added by 209.77.137.57 (talk) 19:00, 14 August 2008 (UTC)

Error in Set of Edges?

Shouldn't the definition of "E = ..." end with "v_n = w_n", instead of "v_n = w_(n-1)"? With n-1, it doesn't fit the description. -- 27 May 2007

Agree - there should either be a description of what 'w' means in this context, or let's lose the set-builder notation. I for one didn't find the set of edges helpful, whereas the properties and descriptions were much better.

Graph Example

The graph examples don't seem to be showing up.

I don't think that graph is the clearest explanation of De Bruijn graphs. I'll make a new one when I get the chance. --Rajah 18:01, 3 November 2006 (UTC)

There are two drawings of De Bruijn graphs already available; the other one is Image:Debruijngraph.gif. When I made the one now on the page, my intention was not to make a clear drawing of that specific eight-vertex graph (I think the other one is better for that), but rather a drawing that would show the structure of De Bruijn graphs more generally — the same style of drawing generalizes to binary De Bruijn graphs of any dimension. As I wrote here, the drawing also makes visible some structural properties of De Bruijn graphs (i.e. they are two-queue graphs) and suggests an analogy with dynamical systems. If you think the drawing should be replaced, please keep these considerations in mind when drawing a replacement. —David Eppstein 18:19, 3 November 2006 (UTC)

(later:) I found some published work supporting the dynamical systems analogy and used it as the basis for moving the figure into a new section describing that connection. Feel free to draw something else as the main illustration for the page. —David Eppstein 19:22, 3 November 2006 (UTC)

WikiProject class rating

This article was automatically assessed because at least one WikiProject had rated the article as start, and the rating on other projects was brought up to start class. BetacommandBot 09:47, 10 November 2007 (UTC)

Error in edge description?

"If one of the vertices can be expressed by shifting all symbols by one place to the left and adding a new symbol at the end of another vertex, then the latter has a directed edge to the former vertex."

This phrasing is not very clear to me, but I think that the mathematical description of the set of directed edges has the edge pointing the other way? (e.g the edge goes from the vertex where we shift all of the elements one to the left (v1...vn) to the vertex with the additional character at the end?(w1...wn)) Thanks, Sparrowsinger (talk) 01:27, 4 April 2011 (UTC)

Agreed, the description does not appear correct to me either, e.g. in the example [001] --> [011], fits this rule, [*01.(1|0)] ==> [011]

• NOT* [01] ==> [011.(1|0)] which the current text suggests.

I'm changing the line to:

"If one of the vertices can be expressed as another vertex by shifting all its symbols by one place to the left and adding a new symbol at the end of this vertex, then the latter has a directed edge to the former vertex."

Zoolium (talk) 16:05, 2 November 2011 (UTC)

How about "If one of the vertices 'v' can be expressed as another vertex 'w' by shifting all 'w's symbols by one place to the left, dropping the leftmost symbol and adding a new symbol to the right, then 'v' has a directed edge to 'w' . ? -- 20 April 2012 — Preceding unsigned comment added by 86.4.54.160 (talk) 05:37, 20 April 2012 (UTC)

de Bruijn or De Bruijn?

There appears to be some confusion as to whether one should capitalize the "d" in "de Bruijn". (Note that de Bruijn was Dutch.) Capitalization#Compound_names states: "In Dutch, all particles like "van", or "de", or "der", or "ter" in a surname are always capitalized unless a given name or initial precedes it." So shouldn't the "d" be capitalized? (A recent change changed it to being not capitalized in this article.). Justin W Smith ^talk/_stalk 00:25, 5 June 2011 (UTC)

I think you are correct. I saw it uncapitalized in a few places, such as http://mathworld.wolfram.com/deBruijnSequence.html, so I thought that was the standard. I will revert the edits.

Thank you! InverseHypercube 00:41, 5 June 2011 (UTC)

No problem. It's a confusing topic since many other "de" names are not capitalized. There's more said about it here. Justin W Smith ^talk/_stalk 00:45, 5 June 2011 (UTC)

cryptography

Is there any evidence that de Bruijn graphs (at least by Good) were not developed at Bletchly Park for cryptographic purposes? — Preceding unsigned comment added by 200.92.192.199 (talk) 00:47, 10 July 2011 (UTC)