Brooks' theorem
http://dbpedia.org/resource/Brooks'_theorem an entity of type: WikicatTheoremsInGraphTheory
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом. Согласно этой теореме вершины связного графа, в котором все вершины имеют не больше Δ соседей, можно раскрасить всего в Δ цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется Δ + 1 цветов. Теорема носит имя (англ. R. Leonard Brooks), опубликовавшего доказательство теоремы в 1941 году. Раскраска с использованием числа цветов, указанной в теореме Брукса иногда называется раскраской Брукса, или Δ-раскраской.
rdf:langString
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.
rdf:langString
У теорії графів, теорема Брукса встановлює зв'язок між максимальним степенем графа і його хроматичним числом. Згідно з теоремою, зв'язний граф, у якому кожна вершина має не більше Δ сусідів, вершини можуть бути пофарбовані не більше ніж в Δ кольорів, за винятком двох випадків — повний граф і граф-цикл непарної довжини, які вимагають Δ + 1 кольорів. Теорема названа на честь , який опублікував доказ в 1941 році. Розмальовку з кількістю кольорів, описаних теоремою Брукса, іноді називають забарвленням Брукса або Δ-розмальовкою.
rdf:langString
图论中,布鲁克定理(英語:Brooks' theorem) 描述了图的着色数与图中最大度数的关系,提供了图着色数的一个上界。定理斷言,若连通图G中,每個頂點都不多於Δ個鄰居,且G不是完全图或奇环,则G可以被Δ-着色,即G可以被染成Δ种颜色,使得相邻点颜色互不相同。
rdf:langString
rdf:langString
Satz von Brooks
rdf:langString
Brooks' theorem
rdf:langString
Teorema de Brooks
rdf:langString
Théorème de Brooks
rdf:langString
Twierdzenie Brooksa
rdf:langString
Теорема Брукса
rdf:langString
布鲁克斯定理
rdf:langString
Теорема Брукса
xsd:integer
21042117
xsd:integer
1109721609
rdf:langString
Bruce Reed
rdf:langString
László Lovász
rdf:langString
Vadim G. Vizing
rdf:langString
Bruce
rdf:langString
László
rdf:langString
Vadim
rdf:langString
Reed
rdf:langString
Lovász
rdf:langString
Vizing
rdf:langString
Brooks' Theorem
rdf:langString
BrooksTheorem
xsd:integer
1975
1976
1999
rdf:langString
cs2
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом. Согласно этой теореме вершины связного графа, в котором все вершины имеют не больше Δ соседей, можно раскрасить всего в Δ цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется Δ + 1 цветов. Теорема носит имя (англ. R. Leonard Brooks), опубликовавшего доказательство теоремы в 1941 году. Раскраска с использованием числа цветов, указанной в теореме Брукса иногда называется раскраской Брукса, или Δ-раскраской.
rdf:langString
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.
rdf:langString
У теорії графів, теорема Брукса встановлює зв'язок між максимальним степенем графа і його хроматичним числом. Згідно з теоремою, зв'язний граф, у якому кожна вершина має не більше Δ сусідів, вершини можуть бути пофарбовані не більше ніж в Δ кольорів, за винятком двох випадків — повний граф і граф-цикл непарної довжини, які вимагають Δ + 1 кольорів. Теорема названа на честь , який опублікував доказ в 1941 році. Розмальовку з кількістю кольорів, описаних теоремою Брукса, іноді називають забарвленням Брукса або Δ-розмальовкою.
rdf:langString
图论中,布鲁克定理(英語:Brooks' theorem) 描述了图的着色数与图中最大度数的关系,提供了图着色数的一个上界。定理斷言,若连通图G中,每個頂點都不多於Δ個鄰居,且G不是完全图或奇环,则G可以被Δ-着色,即G可以被染成Δ种颜色,使得相邻点颜色互不相同。
xsd:nonNegativeInteger
8125