| dbo:abstract
|
- Der Satz von Brooks gibt eine Obergrenze für die Anzahl der Farben an, die benötigt werden, um alle Knoten eines Graphen so zu färben, dass keine zwei benachbarten Knoten dieselbe Farbe haben. (de)
- In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors. The theorem is named after R. Leonard Brooks, who published a proof of it in 1941. A coloring with the number of colors described by Brooks' theorem is sometimes called a Brooks coloring or a Δ-coloring. (en)
- En teoría de grafos, el teorema de Brooks establece la relación entre la valencia máxima del grafo con el número cromático: En donde es la valencia máxima del grafo G. (es)
- En mathématiques, et plus particulièrement dans la théorie des graphes, le théorème de Brooks donne une relation entre le degré maximal d'un graphe connexe non orienté et son nombre chromatique. Selon ce théorème, dans un graphe où chaque sommet a au plus Δ voisins, les sommets peuvent être colorés avec au plus Δ couleurs, sans que deux sommets adjacents n'aient la même couleur, sauf dans deux cas, les graphes complets et les graphes cycles de longueur impaire, qui ont besoin de Δ + 1 couleurs. (fr)
- Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом. Согласно этой теореме вершины связного графа, в котором все вершины имеют не больше Δ соседей, можно раскрасить всего в Δ цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется Δ + 1 цветов. Теорема носит имя (англ. R. Leonard Brooks), опубликовавшего доказательство теоремы в 1941 году. Раскраска с использованием числа цветов, указанной в теореме Брукса иногда называется раскраской Брукса, или Δ-раскраской. (ru)
- Twierdzenie Brooksa – w teorii grafów twierdzenie określające relację pomiędzy maksymalnym stopniem wierzchołka i liczbą chromatyczną w grafie. Nazwa twierdzenia została ustanowiona na cześć angielskiego matematyka , który opublikował jego dowód w 1941 roku. (pl)
- У теорії графів, теорема Брукса встановлює зв'язок між максимальним степенем графа і його хроматичним числом. Згідно з теоремою, зв'язний граф, у якому кожна вершина має не більше Δ сусідів, вершини можуть бути пофарбовані не більше ніж в Δ кольорів, за винятком двох випадків — повний граф і граф-цикл непарної довжини, які вимагають Δ + 1 кольорів. Теорема названа на честь , який опублікував доказ в 1941 році. Розмальовку з кількістю кольорів, описаних теоремою Брукса, іноді називають забарвленням Брукса або Δ-розмальовкою. (uk)
- 图论中，布鲁克定理（英語：Brooks' theorem） 描述了图的着色数与图中最大度数的关系，提供了图着色数的一个上界。定理斷言，若连通图G中，每個頂點都不多於Δ個鄰居，且G不是完全图或奇环，则G可以被Δ-着色，即G可以被染成Δ种颜色，使得相邻点颜色互不相同。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8125 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
|
- Bruce Reed (en)
- László Lovász (en)
- Vadim G. Vizing (en)
|
| dbp:first
|
- Bruce (en)
- László (en)
- Vadim (en)
|
| dbp:last
|
- Reed (en)
- Lovász (en)
- Vizing (en)
|
| dbp:mode
| |
| dbp:title
| |
| dbp:urlname
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
|
- 1975 (xsd:integer)
- 1976 (xsd:integer)
- 1999 (xsd:integer)
|
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Der Satz von Brooks gibt eine Obergrenze für die Anzahl der Farben an, die benötigt werden, um alle Knoten eines Graphen so zu färben, dass keine zwei benachbarten Knoten dieselbe Farbe haben. (de)
- In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors. The theorem is named after R. Leonard Brooks, who published a proof of it in 1941. A coloring with the number of colors described by Brooks' theorem is sometimes called a Brooks coloring or a Δ-coloring. (en)
- En teoría de grafos, el teorema de Brooks establece la relación entre la valencia máxima del grafo con el número cromático: En donde es la valencia máxima del grafo G. (es)
- En mathématiques, et plus particulièrement dans la théorie des graphes, le théorème de Brooks donne une relation entre le degré maximal d'un graphe connexe non orienté et son nombre chromatique. Selon ce théorème, dans un graphe où chaque sommet a au plus Δ voisins, les sommets peuvent être colorés avec au plus Δ couleurs, sans que deux sommets adjacents n'aient la même couleur, sauf dans deux cas, les graphes complets et les graphes cycles de longueur impaire, qui ont besoin de Δ + 1 couleurs. (fr)
- Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом. Согласно этой теореме вершины связного графа, в котором все вершины имеют не больше Δ соседей, можно раскрасить всего в Δ цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется Δ + 1 цветов. Теорема носит имя (англ. R. Leonard Brooks), опубликовавшего доказательство теоремы в 1941 году. Раскраска с использованием числа цветов, указанной в теореме Брукса иногда называется раскраской Брукса, или Δ-раскраской. (ru)
- Twierdzenie Brooksa – w teorii grafów twierdzenie określające relację pomiędzy maksymalnym stopniem wierzchołka i liczbą chromatyczną w grafie. Nazwa twierdzenia została ustanowiona na cześć angielskiego matematyka , który opublikował jego dowód w 1941 roku. (pl)
- У теорії графів, теорема Брукса встановлює зв'язок між максимальним степенем графа і його хроматичним числом. Згідно з теоремою, зв'язний граф, у якому кожна вершина має не більше Δ сусідів, вершини можуть бути пофарбовані не більше ніж в Δ кольорів, за винятком двох випадків — повний граф і граф-цикл непарної довжини, які вимагають Δ + 1 кольорів. Теорема названа на честь , який опублікував доказ в 1941 році. Розмальовку з кількістю кольорів, описаних теоремою Брукса, іноді називають забарвленням Брукса або Δ-розмальовкою. (uk)
- 图论中，布鲁克定理（英語：Brooks' theorem） 描述了图的着色数与图中最大度数的关系，提供了图着色数的一个上界。定理斷言，若连通图G中，每個頂點都不多於Δ個鄰居，且G不是完全图或奇环，则G可以被Δ-着色，即G可以被染成Δ种颜色，使得相邻点颜色互不相同。 (zh)
|
| rdfs:label
|
- Satz von Brooks (de)
- Brooks' theorem (en)
- Teorema de Brooks (es)
- Théorème de Brooks (fr)
- Twierdzenie Brooksa (pl)
- Теорема Брукса (ru)
- 布鲁克斯定理 (zh)
- Теорема Брукса (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
