| dbo:abstract
|
- In mathematics, a vertex cycle cover (commonly called simply cycle cover) of a graph G is a set of cycles which are subgraphs of G and contain all vertices of G. If the cycles of the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover. This is sometimes known as exact vertex cycle cover. In this case the set of the cycles constitutes a spanning subgraph of G. A disjoint cycle cover of an undirected graph (if it exists) can be found in polynomial time by transforming the problem into a problem of finding a perfect matching in a larger graph. If the cycles of the cover have no edges in common, the cover is called edge-disjoint or simply disjoint cycle cover. Similar definitions exist for digraphs, in terms of directed cycles. Finding a vertex-disjoint cycle cover of a directed graph can also be performed in polynomial time by a similar reduction to perfect matching. However, adding the condition that each cycle should have length at least 3 makes the problem NP-hard. (en)
- Покрытие вершин циклами (или просто покрытие циклами) графа G — это набор циклов, которые являются подграфами графа G и содержат все вершины G. Если покрывающие циклы не имеют общих вершин, покрытие называется вершинно непересекающимся или иногда просто покрытием непересекающимися циклами. В этом случае набор циклов составляет остовный подграф графа G.Покрытие непересекающимися циклами неориентированного графа (если такое существует) может быть найдено за полиномиальное время путём преобразования задачи в задачу поиска совершенного паросочетания в большем графе. Если циклы покрытия не имеют общих рёбер, покрытие называется рёберно непересекающимся или просто покрытием непересекающимися циклами. Аналогичные определения существуют для орграфов в терминах ориентированных циклов. Поиск покрытия вершинно непересекающимися циклами ориентированного графа может быть осуществлён за полиномиальное время путём аналогичного сведения к совершенному паросочетанию. Однако добавление условия, что каждый цикл должен иметь длину не менее 3, делает задачу NP-трудной. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3802 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In mathematics, a vertex cycle cover (commonly called simply cycle cover) of a graph G is a set of cycles which are subgraphs of G and contain all vertices of G. If the cycles of the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover. This is sometimes known as exact vertex cycle cover. In this case the set of the cycles constitutes a spanning subgraph of G. A disjoint cycle cover of an undirected graph (if it exists) can be found in polynomial time by transforming the problem into a problem of finding a perfect matching in a larger graph. (en)
- Покрытие вершин циклами (или просто покрытие циклами) графа G — это набор циклов, которые являются подграфами графа G и содержат все вершины G. Если покрывающие циклы не имеют общих вершин, покрытие называется вершинно непересекающимся или иногда просто покрытием непересекающимися циклами. В этом случае набор циклов составляет остовный подграф графа G.Покрытие непересекающимися циклами неориентированного графа (если такое существует) может быть найдено за полиномиальное время путём преобразования задачи в задачу поиска совершенного паросочетания в большем графе. (ru)
|
| rdfs:label
|
- Vertex cycle cover (en)
- Покрытие вершин циклами (ru)
- Покриття вершин циклами (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
