Overfull graph (original) (raw)
In graph theory, an overfull graph is a graph whose size is greater than the product of its maximum degree and half of its order floored, i.e. where is the size of G, is the maximum degree of G, and is the order of G. The concept of an overfull subgraph, an overfull graph that is a subgraph, immediately follows. An alternate, stricter definition of an overfull subgraph S of a graph G requires .
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, an overfull graph is a graph whose size is greater than the product of its maximum degree and half of its order floored, i.e. where is the size of G, is the maximum degree of G, and is the order of G. The concept of an overfull subgraph, an overfull graph that is a subgraph, immediately follows. An alternate, stricter definition of an overfull subgraph S of a graph G requires . (en) Переполненный граф (англ. overfull graph) — это такой простой граф (без кратных ребер и петель), размер которого больше произведения максимальной степени его вершин на округлённую вниз половину его порядка . Если граф имеет переполненный подграф и = то - называется графом с переполненным подграфом (англ. subgraph-overfull graph). Понятие переполненный граф было введено при рассмотрении задач о раскраске ребер графа, а именно при решении вопроса о принадлежности графа к Классу 1 или Классу 2. Как следует из Теоремы Визинга, хроматический индекс графа может быть либо , и тогда граф принадлежит к Классу 1, либо и тогда граф принадлежит к Классу 2. (ru) |
| dbo:wikiPageID | 23472134 (xsd:integer) |
| dbo:wikiPageLength | 3118 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032293333 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Anthony_Hilton dbc:Graph_families dbr:Induced_subgraph dbr:1-factorization_conjecture dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Edge_coloring dbr:Amanda_Chetwynd dbr:Floor_and_ceiling_functions dbr:Graph_theory dbr:Polynomial_time |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Reflist |
| dct:subject | dbc:Graph_families |
| rdf:type | yago:WikicatConjectures yago:Abstraction100002137 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Family108078020 yago:Group100031264 yago:Hypothesis105888929 yago:Idea105833840 yago:Organization108008335 yago:PsychologicalFeature100023100 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Speculation105891783 yago:Unit108189659 |
| rdfs:comment | In graph theory, an overfull graph is a graph whose size is greater than the product of its maximum degree and half of its order floored, i.e. where is the size of G, is the maximum degree of G, and is the order of G. The concept of an overfull subgraph, an overfull graph that is a subgraph, immediately follows. An alternate, stricter definition of an overfull subgraph S of a graph G requires . (en) Переполненный граф (англ. overfull graph) — это такой простой граф (без кратных ребер и петель), размер которого больше произведения максимальной степени его вершин на округлённую вниз половину его порядка . Если граф имеет переполненный подграф и = то - называется графом с переполненным подграфом (англ. subgraph-overfull graph). (ru) |
| rdfs:label | Overfull graph (en) Переполненный граф (ru) |
| owl:sameAs | freebase:Overfull graph wikidata:Overfull graph dbpedia-ru:Overfull graph https://global.dbpedia.org/id/4swLd yago-res:Overfull graph |
| prov:wasDerivedFrom | wikipedia-en:Overfull_graph?oldid=1032293333&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Overfull_graph |
| is dbo:wikiPageRedirects of | dbr:Overfull_conjecture |
| is dbo:wikiPageWikiLink of | dbr:Edge_coloring dbr:Overfull_conjecture |
| is foaf:primaryTopic of | wikipedia-en:Overfull_graph |