A Spanning tree of a graph G is a subgraph that is a tree which concludes all of the vertices of G. And a graph G is bipartite if the vertex set of G can be partitioned in to two sets A and B, such that every edge of G joins a vertex of A and a vertex of B. We can see that every tree(including spanning tree) is bipartite. We define type of a spanning tree using this idea as follows: We divide vertices of a spanning trees in to two partitions A and B by using its bipartition. Then, we define type of the spanning tree by (| A |, | B |), provided | A | less than or equal to | B |. We first identify the characteristics for a graph to have a spanning trees of a certain type. Then, implement some theorems about the type.

A network is a system that involves movement or flow of some commodities such as goods and services. In fact any structure that is in the form of a system of components some of which interact can be considered as a network. In network design the problem is often to construct economical and reliable networks which satisfy certain requirements and which are optimal according to some criterion such as cost, output or performance. Graph theory is useful when the requirements of the network can be expressed in terms of graph parameters, usually as bounds. Some of the graph parameters that have been considered include: degree; distance; diameter; and connectivity. Problems with these parameter restrictions are usually from a class of NP-complete problems with instances that require exponential computer time to solve by available algorithms.The major focus of this thesis is to develop fast and efficient heuristics for some of these NP-complete problems. The two main topics analysed are Restricted Spanning Trees and Graph Partitioning. The aim of the Restricted Spanning Trees section is to construct the most efficient spanning tree (connected network) subject to various degree constraints. These degree constraints imposed are usually in the form of an upper bound. The upper bound represents the maximum number of connections allowed on a particular vertex. The Graph Partitioning section considers the problem of clustering vertices of the graph into sets such that the overall cost of the edges in the different sets is minimised.Chapter 1 provides the notation and terminology used throughout the thesis and a review and summary of the thesis.A literature review of related work that has been carried out to date is presented in Chapter 2. Some of the more promising results are discussed. The first part of the chapter surveys work related to the Restricted Spanning Tree problem. ++ / Analysis of both exact and heuristic methods is given. The second part of Chapter 2 provides a survey of the Graph Partitioning problem. We discuss the many different approaches that have been proposed to solve this problem. The quality of computational results achieved is discussed.Chapter 3 considers the Degree Constraint Minimum Weight Spanning Tree problem. This problem arises in networks where a given terminal is only allowed connections to a maximum number of specified terminals. We consider a number of cases including: same degree constraint on each vertex; different degree constraint on some vertices; and when the degree constraint is only on one or two vertices. A number of heuristics are developed and implemented and compared against an exact Branch and Cut algorithm. Our computational results demonstrated the value of our better performing heuristics.Chapter 4 considers the complexity of the (1,k)-tree problem. This problem is defined m given a graph G with maximum degree k find a spanning tree T with all vertices having degree 1 or k. Analysis is done on graphs with maximum degree 3, 4 and 5. Results establishing that the (1,3)-tree and (1, 4)-tree problems are NP-complete are presented. Further consideration is also given to the complexity of spanning trees with degree from the set { 1, 3, 5}. Analysis is also carried out on the number of degree one vertices in the (1, k)-tree. Presentation of heuristic procedures to solve this NP-complete problem concludes the chapter.Chapter 5 is devoted to the Graph Partitioning problem. A number of heuristics are presented and extensive computational work carried out. Computational findings support the usefulness of the heuristic methods both in terms of quality and time.We conclude this thesis by detailing some future work that can be carried out.

No description available.

Thesis (M.Sc.). / Written for the School of Computer Science. Title from title page of PDF (viewed 2008/01/15). Includes bibliographical references.

Thesis (M.Sc.). / Written for the Dept. of Mathematics and Statistics. Title from title page of PDF (viewed 2008/05/29). Includes bibliographical references.

Over the last decade a number of potential tracers of massive star (M > 8M ) formation have been put forward. In this thesis I attempt to understand how these tracers relate to one another and attempt to identify the most suitable tracer for future surveys for massive star formation sites. In this thesis we examine a number of these tracers; the Methanol Maser Multi- Beam Survey (MMB), the Red MSX Survey (RMS), the Boston University Five Colleges Radio Astronomical Observatory (BU-FCRAO) Galactic Ring Survey (GRS), the BOLOCAM Galactic Plane Survey (BGPS) and the Perretto &amp; Fuller (P&F) Infrared Dark Cloud (IRDC) Catalogue, in addition to the Cyganowski Extended Green Objects Catalogue. This work employs a bespoke non-circular aperture photometry technique, K=1 Nearest Neighbour Analysis and Minimum Spanning Trees (MSTs) in multi-dimensional parameter space with oversampling, edge weighing, mean edge fracturing and convex hull tting. Additional, new 13CO observations were made of the young infrared cluster BDS[2003] 107 (Bica 107) and its environs. We see that despite not being contained within the GLIMPSE Point Source Archive the bulk of masers have an infrared bright counterpart. Photometry of the counterparts shows that they occupy the same colour spaces as that previously determined in Ellingsen (2006); [3.6]-[4.5]>1 and [8.0]<1. We show that the bulk of RMS MYSOs do not exhibit masing and that a signi cant fraction of MYSOs are not found within the RMS . Additionally, we see that the EGO RMS association rate is higher than expected. The BGPS, GRS and P&amp;F IRDC exhibit clustering and elongating, with a common characteristic clustering scale of the order of 6 8 pc. We see that the BGPS is more strongly associated with massive star formation than the GRS. Additionally, we see that although in general all three hull types occupy similar co-located spatial positions they also appear as isolated hulls. The analysis of Bica 107 shows that it is part of a larger star forming region containing Bica 108 and the ultra compact HII region, G5.89. The maser associated with Bica 107 appears to lie on the edge of the cluster's expanding CO shell. The observation that the IRAC colour-magnitude occupied by the masers from the Ellingsen sample is consistent with the MMB, sample suggest that these objects have broadly consistent colours during their masing phase. This can be attributed to the dust and gas envelope being radiatively dominant. The cross matching results indicate that the majority of MYSOs do not exhibit masing. The RMS appears to be missing MYSOs due to missing sources in the MSX catalogue and a photospheric bluing due to MSX large beam width, moving candidates outside the RMS colour cut. The RMS EGO relationship appears to be inconsistent with observed MYSO evolution and may be indicative of multiple EGO generation mechanism as suggested by De Buizer and Vacca (2010). The BPGS and GRS objects and IRDCs do not appear to form a star formation sequence and their existence is not necessarily an indicator of on-going star formation; rather they are an indication of the potential for star formation. All three species types showing signs of clustering and elongation. The shared characteristic scale is suggestive that there may be a processes acting below the scale of the GMC but above that of a single star forming region. The maser associated with Bica 107 appears to be either an example of triggered star formation or late onset star formation within the region and is not an example of continuing star formation within Bica 107. We conclude that a GLIMPSE based colour-selected survey, with follow-up observation to reduce contamination, would be the most appropriate method for identifying MYSOs, given the reliability of the tracers examined in this thesis.

Given a graph G, we construct T(G), called the tree graph of G. The vertices of T(G) are the spanning trees of G, with edges between vertices when their respective spanning trees differ only by a single edge. In this paper we detail many new results concerning tree graphs, involving topics such as clique decomposition, planarity, and automorphism groups. We also investigate and present a number of new results on orthogonal tree decompositions of complete graphs.

Not available / text

No description available.

The minimum degree spanning tree problem is a widely studied NP-hard variation of the minimum spanning tree problem, and a generalization of the Hamiltonian path problem. Most of the work done on the minimum degree spanning tree problem has been on approximation algorithms, and very little work has been done studying graph classes where this problem may be polynomial time solvable. The Hamiltonian path problem has been widely studied on graph classes, and we use classes with polynomial time results for the Hamiltonian path problem as a starting point for graph class results for the minimum degree spanning tree problem. We show the minimum degree spanning tree problem is polynomial time solvable for chain graphs. We then show this problem is polynomial time solvable on bipartite permutation graphs, and that there exist minimum degree spanning trees of these graphs that are caterpillars, and that have other particular structural properties.