| dbo:abstract |
Ein kritischer Graph ist ein Begriff aus der Graphentheorie, der 1965 vom Vadim G. Vizing zur Untersuchung von Kantenfärbungen eingeführt worden ist. Er beschreibt eine Sorte von Graphen, deren chromatischer Index sich durch das Entfernen einer beliebigen Kante immer verkleinert. (de) In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one. (en) Критический граф — граф, в котором удаление любой вершины или ребра приводит к уменьшению хроматического числа графа. (ru) Критичний граф — граф, у якому видалення будь-якої вершини або ребра призводить до зменшення хроматичного числа графу. (uk) 數學分支圖論中，色临界图或臨界圖（英語：critical graph）是图染色问题中一类特殊的圖，從此類圖中，移除任何一邊或一點，皆會使圖的色數減少。这一类图具有一些非常好的性质，能在很多证明定理中发挥用处。 (zh) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Critical_graph_sample.svg?width=300 |
| dbo:wikiPageID |
680672 (xsd:integer) |
| dbo:wikiPageLength |
6703 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1115928254 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbc:Graph_families dbr:Regular_graph dbr:Undirected_graph dbr:De_Bruijn–Erdős_theorem_(graph_theory) dbr:Degree_(graph_theory) dbc:Graph_coloring dbr:Complete_graph dbr:Chromatic_number dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Critical_path_method dbr:K-edge-connected_graph dbr:Cycle_graph dbr:Brooks'_theorem dbr:Graph_theory dbr:Hajós_construction dbr:Factor-critical_graph dbr:File:Critical_graph_sample.svg |
| dbp:wikiPageUsesTemplate |
dbt:Citation dbt:Commons_category dbt:Distinguish dbt:Harvtxt dbt:R dbt:Refbegin dbt:Refend dbt:Reflist |
| dct:subject |
dbc:Graph_families dbc:Graph_coloring |
| gold:hypernym |
dbr:Members |
| rdf:type |
owl:Thing yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment |
Ein kritischer Graph ist ein Begriff aus der Graphentheorie, der 1965 vom Vadim G. Vizing zur Untersuchung von Kantenfärbungen eingeführt worden ist. Er beschreibt eine Sorte von Graphen, deren chromatischer Index sich durch das Entfernen einer beliebigen Kante immer verkleinert. (de) In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one. (en) Критический граф — граф, в котором удаление любой вершины или ребра приводит к уменьшению хроматического числа графа. (ru) Критичний граф — граф, у якому видалення будь-якої вершини або ребра призводить до зменшення хроматичного числа графу. (uk) 數學分支圖論中，色临界图或臨界圖（英語：critical graph）是图染色问题中一类特殊的圖，從此類圖中，移除任何一邊或一點，皆會使圖的色數減少。这一类图具有一些非常好的性质，能在很多证明定理中发挥用处。 (zh) |
| rdfs:label |
Kritischer Graph (de) Critical graph (en) Критический граф (ru) Критичний граф (uk) 色临界图 (zh) |
| owl:sameAs |
freebase:Critical graph yago-res:Critical graph wikidata:Critical graph dbpedia-de:Critical graph dbpedia-hr:Critical graph dbpedia-hu:Critical graph dbpedia-ru:Critical graph dbpedia-uk:Critical graph dbpedia-zh:Critical graph https://global.dbpedia.org/id/kGdN |
| prov:wasDerivedFrom |
wikipedia-en:Critical_graph?oldid=1115928254&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Critical_graph_sample.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Critical_graph |
| is dbo:wikiPageRedirects of |
dbr:Critical_element dbr:Double_critical_graph dbr:K-critical_graph |
| is dbo:wikiPageWikiLink of |
dbr:András_Hajnal dbr:List_of_graph_theory_topics dbr:Graph_coloring dbr:Well-covered_graph dbr:Critical_path dbr:Edge_coloring dbr:Hajós_construction dbr:László_Rátz dbr:Tychonoff's_theorem dbr:Factor-critical_graph dbr:Critical_element dbr:Double_critical_graph dbr:K-critical_graph |
| is foaf:primaryTopic of |
wikipedia-en:Critical_graph |
