| 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
| |
| dbo:wikiPageLength
|
- 3118 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |