Spelling suggestions: "subject:"cycle decomposition""
1 |
Heuristic algorithms for graph decomposition problemsAndriy Kvyatkovskyy Unknown Date (has links)
The research presented in this thesis investigates the performance of some well-known heuristic algorithms on graph decomposition problems. First, a genetic algorithm is introduced and some modifications are trialled on finding Steiner triple systems (STS) of small orders. The results show that traditional genetic algorithms are not well suited to finding graph decompositions. Then a hill climbing optimisation technique is presented and investigated in the context of cycle decompositions. Such searches have previously proved to be effective at finding STSs. However, the general hill climbing approach is not immediately applicable to decompositions into cycles of length larger than 3. A modification of the hill climbing algorithm for cycles, called slippery hill climbing, is introduced and tested on decompositions of graphs into cycles of small lengths larger than 3. Slippery hill climbing successfully decomposed complete and dense non-complete graphs of considerable sizes into cycles of small lengths. In addition, we applied the slippery hill climbing approach to completing partial latin squares. It is reasonably expected that the algorithms developed in this study will also be applicable to other related problems in combinatorics and graph theory.
|
2 |
Snarks : Generation, coverings and colouringsHägglund, Jonas January 2012 (has links)
For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis. The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order. In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24. In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs. In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings. Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.
|
Page generated in 0.1133 seconds