In this report, we study the enumeration of spanning trees in graphs, using two methods withinlinear algebra, Kirchhoff’s Matrix Tree Theorem and an alternative method, also referred to asLemma 1, derived by S. Klee and M.T Stamps in [KS20]. Along with introducing preliminary tools from linear algebra, we also study the Laplace matrix ofa graph and use its properties in the two methods to derive combinatorical expressions on spanningtree enumeration of different graph families. We discuss properties of the Laplace matrix obtainedfrom different graph structures, and determine which method is more suitable in each case, withrespect to linear algebra. Specifically, complete graphs, Ferrers graphs and Windmill graphs areconsidered.

No description available.

In 1992 Du and Hwang published a paper confirming the correctness of a well known 1968 conjecture of Gilbert and Pollak suggesting that the Euclidean Steiner ratio for the plane is 2/3. The original objective of this thesis was to adapt the technique used in this proof to obtain results for other Minkowski spaces. In an attempt to create a rigorous and complete version of the proof, some known results were given new proofs (results for hexagonal trees and for the rectilinear Steiner ratio) and some new results were obtained (on approximation of Steiner ratios and on transforming Steiner trees). The most surprising result, however, was the discovery of a fundamental gap in the proof of Du and Hwang. We give counter examples demonstrating that a statement made about inner spanning trees, which plays an important role in the proof, is not correct. There seems to be no simple way out of this dilemma, and whether the Gilbert-Pollak conjecture is true or not for any number of points seems once again to be an open question. Finally we consider the question of whether Du and Hwang's strategy can be used for cases where the number of points is restricted. After introducing some extra lemmas, we are able to show that the Gilbert-Pollak conjecture is true for 7 or fewer points. This is an improvement on the 1991 proof for 6 points of Rubinstein and Thomas. / Mathematical Sciences / Ph. D. (Mathematics)

In 1992 Du and Hwang published a paper confirming the correctness of a well known 1968 conjecture of Gilbert and Pollak suggesting that the Euclidean Steiner ratio for the plane is 2/3. The original objective of this thesis was to adapt the technique used in this proof to obtain results for other Minkowski spaces. In an attempt to create a rigorous and complete version of the proof, some known results were given new proofs (results for hexagonal trees and for the rectilinear Steiner ratio) and some new results were obtained (on approximation of Steiner ratios and on transforming Steiner trees). The most surprising result, however, was the discovery of a fundamental gap in the proof of Du and Hwang. We give counter examples demonstrating that a statement made about inner spanning trees, which plays an important role in the proof, is not correct. There seems to be no simple way out of this dilemma, and whether the Gilbert-Pollak conjecture is true or not for any number of points seems once again to be an open question. Finally we consider the question of whether Du and Hwang's strategy can be used for cases where the number of points is restricted. After introducing some extra lemmas, we are able to show that the Gilbert-Pollak conjecture is true for 7 or fewer points. This is an improvement on the 1991 proof for 6 points of Rubinstein and Thomas. / Mathematical Sciences / Ph. D. (Mathematics)

This term project deals with the functionality of Spanning Tree protocols, especially the Rapid Spanning Tree Protocol, and the Multiple Spanning Tree Protocol. The primary usage of spanning tree protocols is the prevention of loops within the data link layer, the prevention of a broadcast storm, and also dealing with redundancy in the network. Moreover, the project contains the description of configuration of these protocols on Cisco devices. The main goal of this thesis is to implement the Multiple Spanning Tree protocol into INET framework within the OMNeT++ simulation system. Then, the implemented solution is tested and it's functionality is compared with the referential behavior in a Cisco network.

In this thesis, we study robust combinatorial problems with interval data. We introduce several new measures of robustness in response to the drawbacks of existing measures of robustness. The idea of these new measures is to ensure that the solutions are satisfactory for the decision maker in all scenarios, including the worst case scenario. Therefore, we have introduced a threshold over the worst case costs, in which above this threshold, solutions are no longer satisfactory for the decision maker. It is, however, important to consider other criteria than just the worst case. Therefore, in each of these new measures, a second criteria is used to evaluate the performance of the solution in other scenarios such as the best case one. We also study the robust deviation p-elements problem. In fact, we study when this solution is equal to the optimal solution in the scenario where the cost of each element is the midpoint of its corresponding interval. Then, we finally formulate the robust combinatorial problem with interval data as a bicriteria problem. We also integrate the decision maker's preferences over certain types of solutions into the model. We propose a method that uses these preferences to find the set of solutions that are never preferred by any other solution. We call this set the final set. We study the properties of the final sets from a coherence point of view and from a robust point of view. From a coherence point of view, we study necessary and sufficient conditions for the final set to be monotonic, for the corresponding preferences to be without cycles, and for the set to be stable. Those that do not satisfy these properties are eliminated since we believe these properties to be essential. We also study other properties such as the transitivity of the preference and indifference relations and more. We note that many of our final sets are included in one another and some are even intersections of other final sets. From a robust point of view, we compare our final sets with different measures of robustness and with the first- and second-degree stochastic dominance. We show which sets contain all of these solutions and which only contain these types of solutions. Therefore, when the decision maker chooses his preferences to find the final set, he knows what types of solutions may or may not be in the set. Lastly, we implement this method and apply it to the Robust Shortest Path Problem. We look at how this method performs using different types of randomly generated instances.

Parmi les systèmes complexes étudiés en mécanique statistique, les systèmes possédant un comportement critique à l'équilibre thermodynamique jouissent d'un statut particulier. En effet, pour les systèmes à deux dimensions, les techniques de l'invariance conforme ont permis de les caractériser en grand détail. Cette thèse présente l'étude d'un des tous premiers exemples de systèmes statistiques hors équilibre à pouvoir être traité par des méthodes similaires. Le modèle des piles de sable, considéré dans cet ouvrage, est un modèle dynamique introduit fin des années 80 comme prototype de « criticalité auto-organisée ». On entend par ce terme, des systèmes évoluant spontanément vers un état hautement corrélé qui exhibent des propriétés d'échelle similaires à celles du point critique de systèmes statistiques à l'équilibre. L'outil principal permettant de caractériser l'état stationnaire du modèle sur réseau est la correspondance univoque entre les configurations de hauteur du modèle et certains types de graphes appelés « arbres couvrants ». Cette correspondance a été utilisée pour identifier les opérateurs d'échelle correspondant aux observables de hauteur. Il s'avère que ces opérateurs s'organisent en termes de représentations de l'algèbre conforme de charge centrale c = −2 dont la réalisation naturelle est donnée par une théorie quantique de champs fermioniques libres. Bien que les opérateurs d'échelle des observables locales s'expriment en termes de champs de cette réalisation, il a été montré que les observables de hauteur non locales engendrent une nouvelle réalisation inéquivalente de l'algèbre conforme. Le rapprochement entre ces deux domaines de la physique permet non seulement de fournir un cadre nouveau pour l'étude du modèle des piles de sable et accéder ainsi à des propriétés jusque là impossibles à obtenir par la méthode traditionnelle, mais fournit aussi un outil supplémentaire pour l'étude des théories conformes dites logarithmiques qui sont encore mal comprises à ce jour.

Snow cleaning is one of the important tasks in the winter time in Sweden. Every year government spends huge amount money for snow cleaning purpose. In this thesis we generate a shortest road network of the city and put the depots in different place of the city for snow cleaning. We generate shortest road network using minimum spanning tree algorithm and find the depots position using greedy heuristic. When snow is falling, vehicles start work from the depots and clean the snow all the road network of the city. We generate two types of model. Models are economic model and efficient model. Economic model provide good economical solution of the problem and it use less number of vehicles. Efficient model generate good efficient solution and it take less amount of time to clean the entire road network.

Doctor of Philosophy / Department of Mathematics / Nathan Albin / The concept of discrete $p$-modulus provides a general framework for understanding arbitrary families of objects on a graph. The $p$-modulus provides a sense of ``structure'' of the underlying graph, with different families of objects leading to different insight into the graph's structure. This dissertation builds on this idea, with an emphasis on the family of spanning trees and the underlying graph structure that spanning tree modulus exposes. This dissertation provides a review of the probabilistic interpretation of modulus. In the context of spanning trees, this interpretation rephrases modulus as the problem of choosing a probability mass function on the spanning trees so that two independent, identically distributed random spanning trees have expected overlap as small as possible. A theoretical lower bound on the expected overlap is shown. Graphs that attain this lower bound are called homogeneous and have the property that there exists a probability mass function that gives every edge equal likelihood to appear in a random tree. Moreover, any nonhomogeneous graph necessarily has a homogeneous subgraph (called a homogeneous core), which is shown to split the modulus problem into two smaller subproblems through a process called deflation. Spanning tree modulus and the process of deflation establish a type of hierarchical structure in the underlying graph that is similar to the concept of core-periphery structure found in the literature. Using this, one can see an alternative way of decomposing a graph into its hierarchical community components using homogeneous cores and a related concept: minimum feasible partitions. This dissertation also introduces a simple greedy algorithm for computing the spanning tree modulus that utilizes any efficient algorithm for finding minimum spanning trees. A theoretical proof of the convergence rate is provided, along with computational examples.

No description available.