Orientita grafeo de de Bruijn

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
B(2, 4)

La orientita grafeo de de Bruijn B(n, m) estas orientita grafeo kies verticoj estas ĉiuj eblaj vortoj de longo m-1 de alfabeto de amplekso n.

B(n, m) havas n^{m} laterojn respektivaj al ĉiu eblaj vortoj de longo m de alfabeto de amplekso n. La latero a_1a_2\dots a_n konektas la verticon a_1a_2\dots a_{n-1} al la vertico a_2a_3\dots a_n.

Eŭlera ciklo sur B(n, m) prezentas la plej mallongan vicon de signoj de alfabeto de amplekso n kiu inkluzivas ĉiujn eblajn subvicojn de m signoj. Ekzemple, la vico 000011110010101000 inkluzivas ĉiujn 4-bitajn subvicojn. Ĉiu orientita grafeo de de Bruijn devas havi eŭleran ciklon, pro tio ke ĉiu vertico havas enan gradon kaj eksteran gradon de m.

Eksteraj ligiloj[redakti | redakti fonton]