De Bruijn-gráf

De Bruijn-gráf
B(2,3) De Bruijn-gráf
Névadó	Nicolaas Govert de Bruijn
Csúcsok száma	n^k
Élek száma	n^k+1

A B(n,k) De Bruijn-gráf olyan irányított gráf, amelynek csúcsai egy adott n elemű ábécé összes k hosszúságú szavai, és két csúcs akkor van összekötve egy irányított éllel, ha az első csúcs utolsó k-1 betűje megegyezik a második csúcs első k-1 betűjével.

Értelmezése

A B(n,k) De Bruijn-gráf csúcsai az n elemű A halmaz elemeiből képzett összes k hosszúságú szó (azaz a₁a₂...a_k alakú szavak, ahol az a₁, a₂, ..., a_k, nem feltétlenül különböző elemek, mind az A halmazból vannak). Az a₁a₂...a_k csúcsból irányított él vezet a b₁b₂...b_k csúcsba, ha a₂a₃...a_k=b₁b₂...b_k-1, és ekkor az élt a₁a₂...a_kb_k jelöli.

Példa

n=2 és k=3 esetében, azaz kétbetűs ábécé (pl. 0 és 1) és hárombetűs szavak (azaz 000, 001, 010, 011, 100, 101, 110, 111) esetében az infoboxban látható gráfot kapjuk. A 001 csúcsból például van irányított él a 010 csúcsba, mivel 01 közös a két csúcs között. A megfelelő él címkéje: 0010 (a 001 és 010 egymásra csúsztatása). Minden csúcsból 2 él megy ki, és minden csúcsba 2 él megy be.

Története

Nevét Nicolaas Govert de Bruijn holland matematikusról kapta, aki egy 1946-ban közölt cikkében használta ezt a fogalmat,[1] habár tőle függetlenül I. J. Good 1946-ban szintén használta egy cikkében.[2] Később kiderült, hogy a fogalom valamilyen formában már sokkal hamarabb ismert volt, mivel C. Flye Sainte-Marie már 1896-ban leírta.[3] Helyesen De Bruijn-gráfként kell írni, habár gyakrabban szerepel de Bruijn-gráfként, helytelenül.[4]

Tulajdonságok

• A B(n,k) gráfnak n^k csúcsa és n^k+1 éle van.
• Minden csúcsból n él fut ki, és minden csúcsba n él fut be.
• Minden De Bruijn-gráf tartalmaz Hamilton-kört és zárt Euler-vonalat.
• Egy Hamilton-kör törlésével a gráf összefüggő marad (azaz, ha eltekintünk az irányítástól, a gráf bármely két csúcsa között van út)
• A B(n,k) De Bruijn-gráfban (n!)^n k-1/n^k Hamilton-kör van.

A B(n,k+1) gráf a B(n,k) élgráfja, azaz a B(n,k) élei lesznek a B(n,k+1) csúcsai, és ez utóbbinak két csúcsa össze lesz kötve egy irányított éllel, ha a két csúcsnak megfelelő eredeti két él egymásutáni a B(n,k) gráfban. Az alábbi ábrán látható, hogyan alakítható a kék színű B(2,1) gráf a piros színű B(2,2) gráffá, majd ez a B(2,2) gráf a zöld színű B(2,3) gráffá.

Két Hamilton-kör élfüggetlen, ha nem tartalmaz közös élt. Bond és Iványi 1987-ben megfogalmazta a máig nem bizonyított sejtést, miszerint n>2, k>0 esetében a B(n,k) gráfban n-1 élfüggetlen Hamilton-kör van.[5]

Nem irányított De Bruijn-gráfok

Ha elhagyjuk az élek irányítását, a többszörös éleket egyetlen eggyel helyettesítjük, és töröljük a hurkokat, akkor nem irányított De Bruijn-gráfokat kapunk. Sok csúcs esetén igen szép ábrákat eredményez.

Kétbetűs ábécé fölötti De Bruijn-gráfok, 128 és 256 csúcsúak

Hárombetűs ábécé fölötti De Bruijn-gráfok, 81 és 243 csúcsúak

Négybetűs ábécé fölötti De Bruijn-gráf, 64 csúcsú

Négybetűs ábécé fölötti De Bruijn-gráf, 256 csúcsú

Ötbetűs ábécé fölötti De Bruijn-gráf, 125 csúcsú

   LaTeX-program De Bruijn-gráfok rajzolására

\documentclass{article}
\usepackage{tikz}
\usepackage[nomessages]{fp}
\textwidth=15cm

\newcommand{\DeBruijn}[2]{
 % #1 n
 % #2 k
\begin{tikzpicture}[rotate=90,scale=3] %% ábra elforgatása 90 fokkal, 3-szoros nagyítással

\FPeval\result{round(#1^#2:0)}      %% n k-adik hatványa
\pgfmathtruncatemacro{\p}{\result}%
\pgfmathtruncatemacro{\pp}{\p-1}    %% a k-adik hatvány mínusz 1

  \foreach \i in {0,...,\pp}
  {
    \path (360/\p*\i:1cm) node (X\i) { };    %% csúcsok egyenletes elosztása a körön
    \draw[fill=magenta] (X\i) circle  (1pt); %% csúcsok rajzolása
  }
  
   \foreach \i in {0,...,\pp}
  {
     \foreach \k in {1,...,#1}
       {
          \pgfmathtruncatemacro{\kk}{\k-1}
          \pgfmathtruncatemacro{\r}{mod(#1*\i+\kk,\p)};
          \draw[fill=green] (X\i) -- (X\r);  %% élek rajzolása
       }
  }
 \end{tikzpicture}
}

\begin{document}

\DeBruijn{2}{7} \DeBruijn{2}{8}

\DeBruijn{5}{3} \DeBruijn{9}{2}

\end{document}

Jegyzetek

1. N. G. de Bruijn, A combinatorial problem, Koninklijke Nederlandse Akademie v. Wetenschappen, 49 (1946) 758–764.
2. I. J. Good: Normal recurring decimals, Journal of the London Mathematical Society, 21, 3 (1946) 167–169.
3. C. Flye Sainte-Marie: Question 48, L'Intermédiaire Math., 1 (1894) 107–110.
4. "We mention a peculiarity concerning the spelling of some Dutch names. When omitting the initials of N. G. de Bruijn, one should capitalizale the word 'de' and furthermore the name should be listed under B." J. H. van Lint, R. M. Wilson: A course in combinatorics (2nd ed.), Cambridge University Press. p. 76.
5. J. Bond, A. Iványi: Modeling of interconnection networks using de Bruijn graphs, Third Conference of Program Designers, July 1-3, 1987. Eötvös Loránd University, Faculty of Natural Sciences, Budapest, 1987, pp. 75-88

Források

• G. Chartrand, O. R. Oellermann: Applied and Algorithmic Graph Theory, McGraw-Hill, Inc. 1993. p. 219.
• J. H. van Lint, R. M. Wilson: A Course in Combinatorics (2nd ed.), Cambridge University Press. Chapter 8.
• J. Bond, A. Iványi: Modeling of interconnection networks using de Bruijn graphs, Third Conference of Program Designers, July 1-3, 1987. Eötvös Loránd University, Faculty of Natural Sciences, Budapest, 1987, pp. 75–88.

Kapcsolódó szócikkek

• Gráf
• De Bruijn-szó