| dbo:abstract
|
- En teoria de grafs, el teorema de De Bruijn-Erdős, demostrat per Nicolaas Govert de Bruijn i Paul Erdős el 1951, estableix que, per a cada G i enter finit k, es pot acolorir G amb k colors (de manera que cap parell de vèrtexs adjacents tingui el mateix color) si i només si tots els seus subgrafs finits es poden acolorir amb k colors. És a dir, cada (és a dir, cada graf que requereix k colors però per al qual tots els subgrafs requereixen un nombre menor de colors) ha de tenir un nombre finit de vèrtexs. (ca)
- In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named. The De Bruijn–Erdős theorem has several different proofs, all depending in some way on the axiom of choice. Its applications include extending the four-color theorem and Dilworth's theorem from finite graphs and partially ordered sets to infinite ones, and reducing the Hadwiger–Nelson problem on the chromatic number of the plane to a problem about finite graphs. It may be generalized from finite numbers of colors to sets of colors whose cardinality is a strongly compact cardinal. (en)
- Le théorème de De Bruijn-Erdős en théorie des graphes, démontré par Nicolaas Govert de Bruijn et Paul Erdős, établit que (pour tout entier naturel k) pour qu'un graphe non orienté infini possède une coloration par k couleurs, il suffit qu'il en soit ainsi pour tous ses sous-graphes finis. Autrement dit : tout graphe (en) (i.e. dont toute coloration a au moins k couleurs mais dont tous les sous-graphes propres sont k – 1-colorables) a un nombre fini de sommets. (fr)
- Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном. (ru)
- Теорема де Брейна — Ердеша — класична теорема теорії графів доведена Палом Ердешем і Ніколасом де Брейном. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 27425 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de grafs, el teorema de De Bruijn-Erdős, demostrat per Nicolaas Govert de Bruijn i Paul Erdős el 1951, estableix que, per a cada G i enter finit k, es pot acolorir G amb k colors (de manera que cap parell de vèrtexs adjacents tingui el mateix color) si i només si tots els seus subgrafs finits es poden acolorir amb k colors. És a dir, cada (és a dir, cada graf que requereix k colors però per al qual tots els subgrafs requereixen un nombre menor de colors) ha de tenir un nombre finit de vèrtexs. (ca)
- Le théorème de De Bruijn-Erdős en théorie des graphes, démontré par Nicolaas Govert de Bruijn et Paul Erdős, établit que (pour tout entier naturel k) pour qu'un graphe non orienté infini possède une coloration par k couleurs, il suffit qu'il en soit ainsi pour tous ses sous-graphes finis. Autrement dit : tout graphe (en) (i.e. dont toute coloration a au moins k couleurs mais dont tous les sous-graphes propres sont k – 1-colorables) a un nombre fini de sommets. (fr)
- Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном. (ru)
- Теорема де Брейна — Ердеша — класична теорема теорії графів доведена Палом Ердешем і Ніколасом де Брейном. (uk)
- In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named. (en)
|
| rdfs:label
|
- Teorema de De Bruijn–Erdős (teoria de grafs) (ca)
- De Bruijn–Erdős theorem (graph theory) (en)
- Théorème de De Bruijn-Erdős (théorie des graphes) (fr)
- Теорема де Брёйна — Эрдёша (теория графов) (ru)
- Теорема де Брейна — Ердеша (теорія графів) (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
