This HTML5 document contains 108 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n17http://www.emis.de/newsletter/
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-huhttp://hu.dbpedia.org/resource/
n22http://planetmath.org/
n8https://global.dbpedia.org/id/
n13http://www.esi2.us.es/~mbilbao/pdffiles/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n15http://www.renyi.hu/~p_erdos/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Vizing's_theorem
rdf:type
yago:Proposition106750804 yago:Cognition100023271 yago:WikicatTheoremsInGraphTheory yago:Concept105835747 yago:WikicatConjectures yago:PsychologicalFeature100023100 yago:Communication100033020 yago:Abstraction100002137 yago:Message106598915 yago:Content105809192 yago:Idea105833840 yago:Statement106722453 yago:Hypothesis105888929 yago:Speculation105891783 yago:Theorem106752293
rdfs:label
Vizing's theorem Théorème de Vizing Twierdzenie Vizinga Vizing定理 Теорема Візінга 비징의 정리 Теорема Визинга Satz von Vizing
rdfs:comment
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. 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. В теорії графів, теорема Візінга (названа на честь Вадіма Візінга, який оприлюднив її в 1964) стверджує, що ребра кожного неорієнтованого графу можна пофарбувати, із використанням числа кольорів не більшого ніж найбільший степінь Δ графу плюс 1. Завжди необхідно не менше ніж Δ кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо Δ кольорів, і «клас два», для якого необхідно Δ + 1. Vizing定理是圖論中的定理。它描述了與度的關係。 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. Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин графа. Поскольку цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых цветов достаточно, и «второго класса», для которых необходимо цветов. Результат установлен Вадимом Визингом в 1964 году. 그래프 이론에서 비징의 정리(Визинг의定理, 영어: Vizing’s theorem)는 그래프의 변 색칠수와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다. 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.
dct:subject
dbc:Graph_coloring dbc:Theorems_in_graph_theory
dbo:wikiPageID
5449464
dbo:wikiPageRevisionID
1089165884
dbo:wikiPageWikiLink
dbr:Erdős–Rényi_model dbr:Sphere dbr:Information_Processing_Letters dbr:Planar_graph dbr:Graph_embedding dbr:Multigraph dbr:Oriented_manifold dbr:Almost_all dbr:Cycle_(graph_theory) dbr:PlanetMath dbr:Pseudoforest dbr:Snark_(graph_theory) dbr:Dual_graph dbr:Degree_(graph_theory) dbr:Bipartite_graph dbr:Torus dbr:Branko_Grünbaum dbr:Four_color_theorem dbr:Disjoint_union dbr:Graphs_and_Combinatorics dbc:Graph_coloring dbr:Total_coloring dbr:Vadim_G._Vizing dbr:Glossary_of_graph_theory_terms dbr:Edge_coloring dbr:Induced_subgraph dbc:Theorems_in_graph_theory dbr:Kempe_chain dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Journal_of_Combinatorial_Theory,_Series_B dbr:Independent_set_(graph_theory) dbr:Undirected_graph dbr:Path_(graph_theory) dbr:Platonic_solid dbr:Novosibirsk dbr:Brooks'_theorem
dbo:wikiPageExternalLink
n13:DiestelGT.pdf n15:1977-20.pdf n17:newsletter38.pdf n22:%3Fop=getobj&from=objects&id=6932
owl:sameAs
dbpedia-fa:قضیه_ویزینگ n8:27Lru dbpedia-hu:Vizing-tétel dbpedia-ru:Теорема_Визинга yago-res:Vizing's_theorem dbpedia-ko:비징의_정리 dbpedia-pl:Twierdzenie_Vizinga wikidata:Q2226822 dbpedia-fr:Théorème_de_Vizing dbpedia-de:Satz_von_Vizing freebase:m.0kvgt5t dbpedia-uk:Теорема_Візінга dbpedia-zh:Vizing定理
dbp:wikiPageUsesTemplate
dbt:= dbt:Main dbt:Math dbt:Reflist dbt:Citation dbt:Mvar dbt:Harvtxt dbt:Harv
dbo:abstract
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: В теорії графів, теорема Візінга (названа на честь Вадіма Візінга, який оприлюднив її в 1964) стверджує, що ребра кожного неорієнтованого графу можна пофарбувати, із використанням числа кольорів не більшого ніж найбільший степінь Δ графу плюс 1. Завжди необхідно не менше ніж Δ кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо Δ кольорів, і «клас два», для якого необхідно Δ + 1. 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. 그래프 이론에서 비징의 정리(Визинг의定理, 영어: Vizing’s theorem)는 그래프의 변 색칠수와 최대 차수의 차가 0 또는 1이라는 정리다. 이를 통해 모든 그래프를 두 종류로 분류할 수 있다. Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин графа. Поскольку цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых цветов достаточно, и «второго класса», для которых необходимо цветов. Результат установлен Вадимом Визингом в 1964 году. Vizing定理是圖論中的定理。它描述了與度的關係。 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. 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.
prov:wasDerivedFrom
wikipedia-en:Vizing's_theorem?oldid=1089165884&ns=0
dbo:wikiPageLength
20600
foaf:isPrimaryTopicOf
wikipedia-en:Vizing's_theorem