Vizing's theorem
http://dbpedia.org/resource/Vizing's_theorem an entity of type: WikicatConjectures
Le théorème de Vizing est un théorème de la théorie des graphes qui stipule que la coloration des arêtes d'un graphe G peut s'effectuer à l'aide de Δ+1 couleurs au maximum, où Δ est le degré maximal du graphe G. Il est dû à Vadim G. Vizing.
rdf:langString
그래프 이론에서 비징의 정리(Визинг의定理, 영어: Vizing’s theorem)는 그래프의 변 색칠수와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다.
rdf:langString
In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree Δ of the graph.At least Δ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which Δ colors suffice, and "class two" graphs for which Δ + 1 colors are necessary.A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most Δ+µ colors, where µ is the multiplicity of the multigraph.The theorem is named for Vadim G. Vizing who published it in 1964.
rdf:langString
Twierdzenie Vizinga – twierdzenie określające relację pomiędzy maksymalnym stopniem wierzchołka i indeksem chromatycznym w grafie. Nazwa twierdzenia została ustanowiona na cześć ukraińskiego matematyka , który opublikował je 1964 roku. Każdy nieskierowany graf prosty G można pokolorować krawędziowo używając liczby kolorów równej maksymalnemu stopniowi wierzchołka Δ, lub maksymalnemu stopniowi wierzchołka powiększonemu o jeden Δ+ 1. Grafy, które można pokolorować krawędziowo przy pomocy Δ kolorów, należą do klasy 1., a grafy, które można pokolorować za pomocą Δ+1 kolorów, należą do klasy 2.
rdf:langString
Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин графа. Поскольку цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых цветов достаточно, и «второго класса», для которых необходимо цветов. Результат установлен Вадимом Визингом в 1964 году.
rdf:langString
В теорії графів, теорема Візінга (названа на честь Вадіма Візінга, який оприлюднив її в 1964) стверджує, що ребра кожного неорієнтованого графу можна пофарбувати, із використанням числа кольорів не більшого ніж найбільший степінь Δ графу плюс 1. Завжди необхідно не менше ніж Δ кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо Δ кольорів, і «клас два», для якого необхідно Δ + 1.
rdf:langString
Vizing定理是圖論中的定理。它描述了與度的關係。
rdf:langString
Der Satz von Vizing ist ein 1964 von Vadim G. Vizing publizierter mathematischer Lehrsatz aus der Graphentheorie. Er liefert sowohl eine Untergrenze als auch eine Obergrenze für den chromatischen Index eines Graphen. Sei ein Multigraph, d. h. ein Graph mit Mehrfachkanten aber ohne Schlingen, mit dem chromatischen Index und dem Maximalgrad . Weiterhin bezeichne die maximale Anzahl von Kanten, die zwei Ecken verbinden. Dann gilt die folgende Ungleichung: Diese Ungleichung ist optimal, die Gleichung wird von Shannon-Multigraphen realisiert.
rdf:langString
rdf:langString
Satz von Vizing
rdf:langString
Théorème de Vizing
rdf:langString
비징의 정리
rdf:langString
Twierdzenie Vizinga
rdf:langString
Теорема Визинга
rdf:langString
Vizing's theorem
rdf:langString
Теорема Візінга
rdf:langString
Vizing定理
xsd:integer
5449464
xsd:integer
1089165884
rdf:langString
Der Satz von Vizing ist ein 1964 von Vadim G. Vizing publizierter mathematischer Lehrsatz aus der Graphentheorie. Er liefert sowohl eine Untergrenze als auch eine Obergrenze für den chromatischen Index eines Graphen. Sei ein Multigraph, d. h. ein Graph mit Mehrfachkanten aber ohne Schlingen, mit dem chromatischen Index und dem Maximalgrad . Weiterhin bezeichne die maximale Anzahl von Kanten, die zwei Ecken verbinden. Dann gilt die folgende Ungleichung: Diese Ungleichung ist optimal, die Gleichung wird von Shannon-Multigraphen realisiert. Im Falle eines einfachen Graphen, d. h. eines Graphen ohne Mehrfachkanten, vereinfacht sich die obige Ungleichung dann zu:
rdf:langString
Le théorème de Vizing est un théorème de la théorie des graphes qui stipule que la coloration des arêtes d'un graphe G peut s'effectuer à l'aide de Δ+1 couleurs au maximum, où Δ est le degré maximal du graphe G. Il est dû à Vadim G. Vizing.
rdf:langString
그래프 이론에서 비징의 정리(Визинг의定理, 영어: Vizing’s theorem)는 그래프의 변 색칠수와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다.
rdf:langString
In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree Δ of the graph.At least Δ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which Δ colors suffice, and "class two" graphs for which Δ + 1 colors are necessary.A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most Δ+µ colors, where µ is the multiplicity of the multigraph.The theorem is named for Vadim G. Vizing who published it in 1964.
rdf:langString
Twierdzenie Vizinga – twierdzenie określające relację pomiędzy maksymalnym stopniem wierzchołka i indeksem chromatycznym w grafie. Nazwa twierdzenia została ustanowiona na cześć ukraińskiego matematyka , który opublikował je 1964 roku. Każdy nieskierowany graf prosty G można pokolorować krawędziowo używając liczby kolorów równej maksymalnemu stopniowi wierzchołka Δ, lub maksymalnemu stopniowi wierzchołka powiększonemu o jeden Δ+ 1. Grafy, które można pokolorować krawędziowo przy pomocy Δ kolorów, należą do klasy 1., a grafy, które można pokolorować za pomocą Δ+1 kolorów, należą do klasy 2.
rdf:langString
Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин графа. Поскольку цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых цветов достаточно, и «второго класса», для которых необходимо цветов. Результат установлен Вадимом Визингом в 1964 году.
rdf:langString
В теорії графів, теорема Візінга (названа на честь Вадіма Візінга, який оприлюднив її в 1964) стверджує, що ребра кожного неорієнтованого графу можна пофарбувати, із використанням числа кольорів не більшого ніж найбільший степінь Δ графу плюс 1. Завжди необхідно не менше ніж Δ кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо Δ кольорів, і «клас два», для якого необхідно Δ + 1.
rdf:langString
Vizing定理是圖論中的定理。它描述了與度的關係。
xsd:nonNegativeInteger
20600