Jump to content

Talk:De Bruijn graph: Difference between revisions

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Content deleted Content added
moved into subsection
Cewbot (talk | contribs)
m Maintain {{WPBS}}: 3 WikiProject templates. Keep majority rating "Start" in {{WPBS}}. Remove 3 same ratings as {{WPBS}} in {{Maths rating}}, {{Physics}}, {{Sys rating}}. Remove 2 deprecated parameters: field, historical.
 
(31 intermediate revisions by 19 users not shown)
Line 1: Line 1:
{{WikiProject banner shell|class=Start|
1=
{{WikiProject Mathematics| importance = low}}
{{WikiProject Physics|importance=Low}}
{{WikiProject Systems|importance=mid|field=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.

<span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/149.157.246.18|149.157.246.18]] ([[User talk:149.157.246.18|talk]]) 09:42, 23 February 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

==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. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/209.77.137.57|209.77.137.57]] ([[User talk:209.77.137.57|talk]]) 19:00, 14 August 2008 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

== 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==
== Graph Example==
The graph examples don't seem to be showing up.
The graph examples don't seem to be showing up.
Line 5: Line 28:


::(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. —[[User:David Eppstein|David Eppstein]] 19:22, 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. —[[User:David Eppstein|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. [[User:BetacommandBot|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, [[User:Sparrowsinger|Sparrowsinger]] ([[User talk: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."
:[[User:Zoolium|Zoolium]] ([[User talk: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 <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/86.4.54.160|86.4.54.160]] ([[User talk:86.4.54.160|talk]]) 05:37, 20 April 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== de Bruijn or De Bruijn? ==

There appears to be some confusion as to whether one should capitalize the "d" in "de Bruijn". (Note that [[Nicolaas Govert de Bruijn|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 [http://en.wikipedia.org/enwiki/w/index.php?title=De_Bruijn_graph&action=historysubmit&diff=432601861&oldid=427228757 recent change] changed it to being not capitalized in this article.). <span style="white-space:nowrap;"><b>[[User:Justin W Smith|Justin W Smith]]</b> <i><sup>[[User talk:Justin W Smith|talk]]</sup>/<sub>[[Special:Contributions/Justin W Smith|stalk]]</sub></i></span> 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! [[User:InverseHypercube|<span style="color:blue; font-size:small;">Inverse</span><span style="color:#6495ED; font-size:small;">Hypercube</span>]] 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 [[Dutch name#Surnames|here]]. <span style="white-space:nowrap;"><b>[[User:Justin W Smith|Justin W Smith]]</b> <i><sup>[[User talk:Justin W Smith|talk]]</sup>/<sub>[[Special:Contributions/Justin W Smith|stalk]]</sub></i></span> 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? <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/200.92.192.199|200.92.192.199]] ([[User talk:200.92.192.199|talk]]) 00:47, 10 July 2011 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

Latest revision as of 12:11, 13 February 2024

Vertices

[edit]

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)[reply]

Discovered???

[edit]

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)[reply]

Error in Set of Edges?

[edit]

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

[edit]

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)[reply]
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)[reply]
(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)[reply]

WikiProject class rating

[edit]

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)[reply]

Error in edge description?

[edit]

"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)[reply]


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)[reply]
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)[reply]

de Bruijn or De Bruijn?

[edit]

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)[reply]

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)[reply]
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)[reply]

cryptography

[edit]

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)[reply]