| dbo:abstract
|
- In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected. (en)
- Гамильтоново разложение заданного графа — это разбиение рёбер графа на гамильтоновы циклы. Гамильтоновы разложения изучались как для неориентированных графов, так и для ориентированных графов. В случае неориентированного графа гамильтоново разложение может быть описано как 2-факторизация графа, такая что каждый фактор связен. Чтобы такое разложение существовало для неориентированного графа, он должен быть связным регулярным графом с чётной степенью.Ориентированный же граф с таким разложением должен быть сильно связен и все вершины должны иметь одинаковые полустепени захода и исхода, но эти степени не обязаны быть чётными. Известно, что любой полный граф с нечётным числом вершин имеет гамильтоново разложение. Этот результат, являющийся специальным случаем задачи Обервольфаха разложения полных графов на изоморфные 2-факторы, Эдуард Люка в 1892 году приписывал Валецки.Построение Валецки помещает вершин в правильный многоугольник и покрывает полный граф на этом подмножестве вершин гамильтоновыми путями, идущими зигзагом через многоугольник с поворотом каждого пути на кратный угол.Пути могут затем быть дополнены до гамильтоновых циклов путём соединения их концов через оставшуюся вершину. Ориентированные случай полных графов — это турниры. Отвечая на гипотезу Келли 1968 года, Даниэла Кюн и Дирик Остус доказали в 2012 году, что любой достаточно большой регулярный турнир имеет гамильтоново разложение. Проверка, имеет ли произвольный граф гамильтоново разложение, является NP-полной задачей как для ориентированных, так и неориентированных графов. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9531 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected. (en)
- Гамильтоново разложение заданного графа — это разбиение рёбер графа на гамильтоновы циклы. Гамильтоновы разложения изучались как для неориентированных графов, так и для ориентированных графов. В случае неориентированного графа гамильтоново разложение может быть описано как 2-факторизация графа, такая что каждый фактор связен. Чтобы такое разложение существовало для неориентированного графа, он должен быть связным регулярным графом с чётной степенью.Ориентированный же граф с таким разложением должен быть сильно связен и все вершины должны иметь одинаковые полустепени захода и исхода, но эти степени не обязаны быть чётными. (ru)
|
| rdfs:label
|
- Hamiltonian decomposition (en)
- Гамильтоново разложение (ru)
- Гамільтонів розклад (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
