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	nk
Élek száma	nk+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, habár tőle függetlenül I. J. Good 1946-ban szintén használta egy cikkében. 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. Helyesen De Bruijn-gráfként kell írni, habár gyakrabban szerepel de Bruijn-gráfként, helytelenül.

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.

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}

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ó