Spelling suggestions: "subject:"complete problems."" "subject:"incomplete problems.""
21 |
Local properties of graphsDe Wet, Johan Pieter 10 1900 (has links)
We say a graph is locally P if the induced graph on the neighbourhood of every vertex has the property P. Specically, a graph is locally traceable (LT) or locally hamiltonian (LH) if the induced graph on the neighbourhood of every vertex is traceable or hamiltonian, respectively. A locally locally hamiltonian (L2H) graph is a graph in which the graph induced by the neighbourhood of each vertex is an
LH graph. This concept is generalized to an arbitrary degree of nesting, to make it possible to work with LkH graphs. This thesis focuses on the global cycle properties of LT, LH and LkH graphs. Methods are developed to construct and combine such graphs to create others with desired properties. It is shown that with the exception of three graphs, LT graphs with maximum degree no greater than 5 are fully cycle extendable (and hence hamiltonian), but
the Hamilton cycle problem for LT graphs with maximum degree 6 is NP-complete. Furthermore, the smallest nontraceable LT graph has order 10, and the smallest value of the maximum degree for which LT graphs can be nontraceable is 6. It is also shown that LH graphs with maximum degree 6 are fully cycle extendable, and that there exist nonhamiltonian LH graphs with maximum degree 9 or less for all orders greater than 10. The Hamilton cycle problem is shown to be
NP-complete for LH graphs with maximum degree 9. The construction of r-regular nonhamiltonian graphs is demonstrated, and it is shown that the number of vertices in a longest path in an LH graph can contain a vanishing fraction of the vertices of the graph. NP-completeness of the Hamilton cycle problem for LkH graphs for higher values of k is also investigated. / Mathematical Sciences / D. Phil. (Mathematics)
|
22 |
Genetické algoritmy / Genetic AlgorithmsMiček, David January 2009 (has links)
This thesis presents description of Genetic algorithm. The description begins with theory of complexity and following basic theory of genetic algorithm. Next part explains the principle of all three tasks – travelling salesman problem, knapsack problem and evolution of algorithm for five-in-a-row. The main focus was on developing the algorithm for five-in-a-row. The results were tested with other similar algorithms from internet. In case of travelling salesman problem and knapsack problem, the results were compared with gradient optimization methods.
|
23 |
The complexity of unavoidable word patternsSauer, Paul Van der Merwe 12 1900 (has links)
Bibliography: pages 192-195 / The avoidability, or unavoidability of patterns in words over finite alphabets has
been studied extensively. The word α over a finite set A is said to be unavoidable
for an infinite set B+ of nonempty words over a finite set B if, for all but finitely
many elements w of B+, there exists a semigroup morphism φ ∶ A+ → B+ such that
φ(α) is a factor of w.
In this treatise, we start by presenting a historical background of results that are
related to unavoidability. We present and discuss the most important theorems
surrounding unavoidability in detail.
We present various complexity-related properties of unavoidable words. For words
that are unavoidable, we provide a constructive upper bound to the lengths of
words that avoid them. In particular, for a pattern α of length n over an alphabet
of size r, we give a concrete function N(n, r) such that no word of length N(n, r)
over the alphabet of size r avoids α.
A natural subsequent question is how many unavoidable words there are. We show
that the fraction of words that are unavoidable drops exponentially fast in the
length of the word. This allows us to calculate an upper bound on the number of
unavoidable patterns for any given finite alphabet.
Subsequently, we investigate computational aspects of unavoidable words. In
particular, we exhibit concrete algorithms for determining whether a word is
unavoidable. We also prove results on the computational complexity of the problem
of determining whether a given word is unavoidable. Specifically, the
NP-completeness of the aforementioned problem is established. / Decision Sciences / D. Phil. (Operations Research)
|
24 |
Evoluční algoritmy při řešení problému obchodního cestujícího / Evolutionary Algorithms for the Solution of Travelling Salesman ProblemJurčík, Lukáš January 2014 (has links)
This diploma thesis deals with evolutionary algorithms used for travelling salesman problem (TSP). In the first section, there are theoretical foundations of a graph theory and computational complexity theory. Next section contains a description of chosen optimization algorithms. The aim of the diploma thesis is to implement an application that solve TSP using evolutionary algorithms.
|
Page generated in 0.0685 seconds