Authors: Sprengel, Eva-Maria
Title: Maximale Kreispackungen für verallgemeinerte Petersen Graphen und die Bestimmung der Kreispackungszahl unter Verwendung von Knotenseparatoren
Language (ISO): de
Abstract: For a graph G = (V;E) a maximum cycle packing is a collection of pairwise edgedisjoint cycles. The maximum cardinality n(G) of such a packing is denoted as the cycle packing number of G. In general the determination of a maximum cycle packing and n(G), respectively, is NP-hard. In this thesis we first introduce the theoretical problem by some examples of cycle packings for three particular graphs. Afterwards we give three practical examples, where you can use cycle packings on special graphs for establishing a practical solution. In Chapter 3 we outline the connection between vertex cuts and maximum cylce packings. We first have a look at graphs which contain a vertex cut of cardinality two or three. Following this we regard graphs with a given vertex cut of an arbitrary cardinality. At least we consider the family P(n;k) of generalized Petersen graphs. In case k even, we outline, that there exists always an maximum cycle packing, where all cycles excepted one are shortest cycles of length eight, if n is big enough. In case k odd, we also prove this for some special cases.
Für einen gegebenen Graphen G = (V;E) ist eine maximale Kreispackung eine maximale Menge paarweise kantendisjunkter Kreise in G. Die maximale Anzahl n(G) wird als Kreispackungszahl bezeichnet. Es ist bekannt, dass die Bestimmung einer maximalen Kreispackung sowie der Kreispackungszahl ein NP􀀀schweres Problem darstellen. In dieser Arbeit werden maximale Kreispackungen zunächst an Hand einiger graphentheoretischer Beispiele eingeführt. Anschließend werden drei praktische Problemstellungen vorgestellt, deren Lösungen sich durch das Auffinden einer maximalen Kreispackung oder die Bestimmung der Kreispackungszahl auf einem geeigneten Graphen herleiten lassen. Im dritten Kapitel wird der Zusammenhang zwischen Knotenseparatoren und maximalen Kreispackungen erläutert. Dazu werden zunächst Graphen betrachtet, welche einen Knotenseparator mit zwei bzw. drei Knoten enthalten. Abschließend wird der Fall eines Graphen mit einem gegebenen Knotenseparator mit einer beliebigen Anzahl von Knoten behandelt. Im letzten Kapitel wird eine spezielle Graphenfamilie, die Familie der verallgemeinerten Petersen Graphen P(n;k) vorgestellt. Es wird für den Fall k mod 2 = 0 gezeigt, dass immer eine maximale Kreispackung existiert, welche, bis auf höchstens einen Kreis, ausschließlich aus kürzesten Kreisen der Länge acht besteht, sofern n groß genug ist. Für den Fall k mod 2 = 1 wird diese Aussage ebenfalls für einige Spezialfälle bewiesen.
Subject Headings: Graphentheorie
Graph
Kreispackung
Kreispackungszahl
Knotenseparator
Verallgemeinerte Petersen Graph
Subject Headings (RSWK): Graphentheorie / Packungsproblem / Petersen-Graph
URI: http://hdl.handle.net/2003/34101
http://dx.doi.org/10.17877/DE290R-7318
Issue Date: 2015
Appears in Collections:Fachgebiet Operations Research und Wirtschaftsinformatik

Files in This Item:
File Description SizeFormat 
Dissertation.pdfDNB1.58 MBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.