Let G be a graph and T an even cardinality subset of its vertices. We call (G,T) a graft. A T-join is a subgraph of G whose odd-degree vertices are precisely those in T, and a T-cut is a cut delta(S) where S contains an odd number of vertices of T. An interesting question from a combinatorial optimization perspective is that of finding optimal T-joins and T-cuts. These have applications in various places. We give an overview of several such optimization problems, as well as several algorithms for finding optimal T-joins and T-cuts from the literature.We then consider a packing problem in grafts. It is a simple observation that the number of edge-disjoint T-joins is at most the number of edges in any T-cut. However it is not known exactly when these quantities are equal. It has been conjectured by Guenin that if G is planar and all T-cuts of G have the same parity and the size of every T-cut is at least k, then G contains k edge-disjoint T-joins. The case k = 3 is equivalent to the Four Colour Theorem, and the cases k = 4, which was conjectured by Seymour, and k = 5 were proved by Guenin. Recently, the case k = 6 was settled by Dvorak, Kawarabayashi and Kral. In this thesis, we give a proof of the case k = 7. / Soit G un graphe, et T un sous-ensemble de ses sommets de cardinalité pair. Nous appelons (G,T) une greffe. Définissons par T-jointure tout sous-graphe de G dans lequel les sommets de degré impair sont précisement ceux de l'ensemble T, et par T-coupure tout coupure delta(S) où S contient un nombre impair de sommets de T. Une question intéressante en optimisation combinatoire est celle de trouver les T-jointures et T-coupures optimales. Nous donnons un aperçu de divers problèmes d'optimisation auxquels ceux-ci s'appliquent, ainsi que plusieurs algorithmes pour trouver les T-jointures et T-coupures optimales.Nous considérons ensuite un problème d'empaquetage dans les greffes. C'est une observation facile que le nombre de T-jointures arête-disjointes dans le graphe G est au maximum le nombre d'arêtes dans quelconque T-coupure. Cependant on ne sait pas exactement quand ces quantités sont égales. Il a été conjecturé par Guenin que si G est planaire, que tous les T-coupures de G ont la même parité et que et le nombre d'arêtes dans chaque T-coupure est au moins k, alors G contient k T-jointures arête-disjointes. Quand k = 3 la question est équivalente au théorème des quatre couleurs, et le cas k = 4, ce qui a été conjecturé par Seymour, et k = 5 ont été prouvés par Guenin. Récemment, le cas k = 6 a été réglé par Dvorak, Kawarabayashi et Kral. Dans cette thèse, nous donnons une preuve pour le cas k = 7.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.104686 |
| Date | January 2011 |
| Creators | Edwards, Katherine |
| Contributors | Frederick Shepherd (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (Department of Mathematics and Statistics) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0022 seconds