| dbo:abstract
|
- In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, relates two parameters of a graph:
* The size of the largest collection of vertex-disjoint cycles contained in the graph;
* The size of the smallest feedback vertex set in the graph: a set that contains one vertex from every cycle. (en)
- En théorie des graphes, le théorème d'Erdős-Pósa, nommé après Paul Erdős et (en), relie dans un graphe la taille maximale d'une collection de cycles disjoints à la taille minimale d'un coupe-cycles de sommets (feedback vertex set). (fr)
- В теории графов теорема Эрдёша – Поза (Пал Эрдёш и ) утверждает, что существует функция f(k), такая, что для любого натурального числа k любой граф либо содержит k разъединённых по вершинам циклов, либо он имеет из f(k) вершин, которое пересекает любой цикл. Более того, f(k) = O(k log k) в нотации O Большое. Ввиду этой теоремы, говорят, что циклы имеют свойство Эрдёша – Поза. Теорема утверждает, что для любого конечного числа k существует некоторое (минимальное) значение f(k), для которого в любом графе, не имеющем k вершинно разъединённых циклов, все циклы могут быть покрыты f(k) вершинами. Это обобщает неопубликованный результат , который утверждает, что f(2) = 3. Эрдёш и Поза получили границы c1k log k < f(k) < c2k log k в общем случае. Этот результат предполагает, что хотя существует бесконечно много графов без k разъединённых циклов, они распадаются на конечное число просто описываемых классов. Для случая k = 2, Ловаш дал полное описание. Восс доказал, что f(3) = 6 и 9 ≤ f(4) ≤ 12. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8995 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, relates two parameters of a graph:
* The size of the largest collection of vertex-disjoint cycles contained in the graph;
* The size of the smallest feedback vertex set in the graph: a set that contains one vertex from every cycle. (en)
- En théorie des graphes, le théorème d'Erdős-Pósa, nommé après Paul Erdős et (en), relie dans un graphe la taille maximale d'une collection de cycles disjoints à la taille minimale d'un coupe-cycles de sommets (feedback vertex set). (fr)
- В теории графов теорема Эрдёша – Поза (Пал Эрдёш и ) утверждает, что существует функция f(k), такая, что для любого натурального числа k любой граф либо содержит k разъединённых по вершинам циклов, либо он имеет из f(k) вершин, которое пересекает любой цикл. Более того, f(k) = O(k log k) в нотации O Большое. Ввиду этой теоремы, говорят, что циклы имеют свойство Эрдёша – Поза. (ru)
|
| rdfs:label
|
- Erdős–Pósa theorem (en)
- Théorème d'Erdős-Pósa (fr)
- Теорема Эрдёша — Поза (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
