De Bruijn-gráf

A Wikipédiából, a szabad enciklopédiából
De Bruijn-gráf
De Bruijn digraph 2 3.png
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[szerkesztés | forrásszöveg szerkeszté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 a1a2...ak alakú szavak, ahol az a1, a2, ..., ak, nem feltétlenül különböző elemek, mind az A halmazból vannak). Az a1a2...ak csúcsból irányított él vezet a b1b2...bk csúcsba, ha a2a3...ak=b1b2...bk-1, és ekkor az élt a1a2...akbk jelöli.

Példa[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

  • A B(n,k) gráfnak nk csúcsa és nk+1 éle van.
  • Minden csúcsból k él fut ki, és minden csúcsba k é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/nk Hamilton-kör van.

A B(n,k+1) gráf a B(n,k) vonalgrá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á.

DeBruijn-as-line-digraph.svg


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[szerkesztés | forrásszöveg szerkesztése]

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ú
  •  

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  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[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]