检查密集图中是否存在Hamilton周期 [英] Checking if a Hamilton Cycle exists in a dense graph

问题描述

定义1

一个图G如果对于每对不相邻的顶点u和v，d（u）+ d（v）> = n
，其中n = | V |和d（*）表示顶点的程度*

定义2

< blockquote>
G上的一个哈密尔顿圈是一个顶点序列（vi1，vi2，... vin，vi1），使得对于所有的l！= h和{ vil，vil}是G的一个边。

问题是：编写一个程序，给定一个密集的无向图G = V; E）作为输入，确定G是否承认G上的一个哈密尔顿循环，并输出该循环（如果有的话），或者输出N，如果没有的话。

我的解决方案是从源头开始查找所有可能的路径，并检查是否存在回到此源的路径。不幸的是，这个解决方案效率不高。

有什么建议吗？谢谢。

解决方案

根据 Ore定理，满足定义1的图总是有一个哈密顿周期，而 Palmer's algorithm 会给你一个O（n ² ）。

A few definitions first:

Definition 1

A graph G = (V, E) is called ``dense'' if for each pair of non-adjacent vertices u and v, d(u) + d(v)>=n where n = |V| and d(*) denotes the degree of the vertex *

Definition 2

A ``Hamiltonian cycle'' on G is a sequence of vertices ( vi1, vi2,....vin, vi1 ) such that vil != vih for all l!=h and { vil, vil} is an edge of G.

The problem is: write a program that, given a dense undirected graph G = (V; E) as input, determines whether G admits a Hamiltonian cycle on G and outputs that cycle, if there is one, or outputs ``N'' if there is none.

my solution is to find all the possible paths starting from a source and to check if a path exists that gets back to this source. Unfortunately, this solution is not efficient.

any suggestions? Thank you.

解决方案

According to Ore's theorem, graphs satisfying Definition 1 always have a Hamiltonian cycle, and Palmer's algorithm will give you one in O(n²).

这篇关于检查密集图中是否存在Hamilton周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！