In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence. For a set of m symbols S = {s1, …, sm}, the set of vertices is: Although De Bruijn graphs are named after Nicolaas Govert de Bruijn, they were discovered independently by both De Bruijn and I. J. Good. Much earlier, Camille Flye Sainte-Marie implicitly used their properties.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Orientita grafeo de de Bruijn (eo)
- Grafo de De Bruijn (es)
- De Bruijn graph (en)
- Graphe de de Bruijn (fr)
- Grafo di de Bruijn (it)
- De Bruijn-graf (sv)
|
| rdfs:comment
| - 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 laterojn respektivaj al ĉiu eblaj vortoj de longo m de alfabeto de amplekso n. La latero konektas la verticon al la vertico . sur B(n, m) prezentas la plej mallongan vicon de signoj de alfabeto de amplekso n kiu inkluzivas ĉiujn eblajn 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 kaj de m. (eo)
- Un grafo di de Bruijn è un tipo di digrafo utilizzato nella teoria dei sistemi e in bioinformatica. Scoperto in maniera indipendente da de Bruijn e Good, un grafo è composto a partire da un alfabeto di cardinalità e un numero intero . Il grafo possiede vertici che contengono tutte le sequenze di lunghezza (denominate sequenze di de Bruijn). Sia l'alfabeto di simboli e sia il dizionario delle sequenze di de Bruijn di lunghezza . L'insieme degli archi del grafo di de Bruijn è definito da . (it)
- In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence. For a set of m symbols S = {s1, …, sm}, the set of vertices is: Although De Bruijn graphs are named after Nicolaas Govert de Bruijn, they were discovered independently by both De Bruijn and I. J. Good. Much earlier, Camille Flye Sainte-Marie implicitly used their properties. (en)
- Un grafo de De Bruijn es un grafo dirigido que permite representar los solapamientos de longitud entre todas las palabras (cadenas de caracteres) de longitud con un alfabeto dado. El nombre de los grafos deriva del matemático Nicolaas Govert de Bruijn quien los describió en 1946. Sin embargo, dichos grafos ya habían sido descritos por Camille Flye Santa-Casa en 1894 y por Irving J. Good en 1946. (es)
- Un graphe de de Bruijn est un graphe orienté qui permet de représenter les chevauchements de longueur entre tous les mots de longueur sur un alphabet donné. Les graphes sont nommés ainsi d'après le mathématicien Nicolaas Govert de Bruijn qui les a décrits en 1946. Les graphes ont déjà été décrits antérieurement, notamment par Camille Flye Sainte-Marie en 1894 et par Irving J. Good en 1946. (fr)
- Inom grafteori är en n-dimensionell de Bruijn-graf över m tecken en riktad graf som representerar överlappningar mellan teckensekvenser. Den har mn hörn (noder), vilka består av alla möjliga sekvenser med längden n av de givna tecknen (samma tecken får förekomma mer än en gång i samma sekvens). Om vi har mängden med m tecken S:={s1,... ,sm} så är mängden hörn: V=Sn = {s1...s1s1, s1...s1s2, ..., s1...s1sm, s1...s2s1, ..., smsmsm} E={((v1, v2, ..., vn), (v2, ..., vn, si)) : i = 1, ..., m} (sv)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| align
| |
| caption
| - Binary De Bruijn graph (en)
- Lorenz attractor (en)
|
| id
| |
| image
| - DeBruijn-3-2.svg (en)
- Lorenz attractor2.svg (en)
|
| title
| |
| total width
| |
| has abstract
| - 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 laterojn respektivaj al ĉiu eblaj vortoj de longo m de alfabeto de amplekso n. La latero konektas la verticon al la vertico . sur B(n, m) prezentas la plej mallongan vicon de signoj de alfabeto de amplekso n kiu inkluzivas ĉiujn eblajn 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 kaj de m. (eo)
- Un grafo de De Bruijn es un grafo dirigido que permite representar los solapamientos de longitud entre todas las palabras (cadenas de caracteres) de longitud con un alfabeto dado. El nombre de los grafos deriva del matemático Nicolaas Govert de Bruijn quien los describió en 1946. Sin embargo, dichos grafos ya habían sido descritos por Camille Flye Santa-Casa en 1894 y por Irving J. Good en 1946. El grafo de De Bruijn de orden con un alfabeto de letras está construido como se explica a continuación. Los nodos (o vértices) de están en biyección con (están etiquetados por) las palabras de longitud sobre . Si y son dos nodos, hay un arco de a cuando la palabra obtenida al suprimir la primera letra o caracter de es la misma que la palabra obtenida al suprimir la última letra de , dicho de otra manera, cuando hay dos letras y , y una palabra o cadena , tales que y . La presencia de un arco significa entonces que hay una sobreposición entre dos palabras de la misma longitud. (es)
- In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence. For a set of m symbols S = {s1, …, sm}, the set of vertices is: 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. Thus the set of arcs (that is, directed edges) is Although De Bruijn graphs are named after Nicolaas Govert de Bruijn, they were discovered independently by both De Bruijn and I. J. Good. Much earlier, Camille Flye Sainte-Marie implicitly used their properties. (en)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
