M.Sc. (Mathematics) / Please refer to full text to view abstract

The n-antiprism graph is not widely studied as a class of graphs in graph theory hence there is not much literature. We begin by de ning the n-antiprism graph and discussing properties, which we prove in the thesis, and which have not been previously presented in graph theory literature. Some of our signi cant results include proving that an n-antiprism is 4-connected, 4-edge connected and has a pathwidth of 4. A highly studied area of graph theory is the chromatic polynomial of graphs. We investigate the chromatic polynomial of the antiprism graph and attempt to nd explicit expressions for the chromatic polynomial of the antiprism graph. We express this chromatic polynomial in several forms to discover the best-suited form. We then explore the Tutte polynomial and search for an explicit expression of the Tutte polynomial of the antiprism graph. Using the relationship between a graph and its dual graph, we provide an iterative expression of the Tutte polynomial of the antiprism graph.

Firstly we express the chromatic polynomials of some graphs in tree form. We then Study a special product that comes natural and is useful in the calculation of some Chromatic polynomials. Next we use the tree form to study the chromatic polynomial Of a graph obtained from a forest (tree) by "blowing up" or "replacing" the vertices Of the forest (tree) by a graph. Then we give explicit expressions, in terms of induced Subgraphs, for the first five coefficients of the chromatic polynomial of a connected Graph. In the case of higher order graphs we develop some useful computational Techniques to obtain some higher order coefficients. In the process we obtain some Useful combinatorial identities, some of which are new. We discuss in detail the Application of these combinatorial identities to some families of graphs. We also discuss Pairs of graphs that are chromatically equivalent and graph that are chromatically Unique with special emphasis on wheels. In conclusion,

Ce travail de thèse constitue une contribution à la modélisation et au diagnostic des systèmes multi-domaines à commutation (hybrides). Il est appliqué à la supervision des systèmes multi-sources d’énergie propre où l’hydrogène est utilisé comme moyen de stockage. Un tel système associe des composantes énergétiques de nature différente et fait l’objet de commutations produites par la connexion et déconnexion d’un ou plusieurs composants. Ces commutations génèrent différents modes de fonctionnement et sont liées à l’intermittence des sources primaires, aux capacités de stockage et à la disponibilité opérationnelle des ressources matérielles qui constituent le système. La présence de ces commutations engendre une dynamique variable qui est classiquement difficile à exprimer mathématiquement sans exploiter tous les modes. Ces difficultés de modélisation se propagent pour affecter toutes les tâches dépendantes du modèle comme le diagnostic et la gestion de modes de fonctionnement. Pour résoudre ces problématiques, un nouvel outil, Bond Graph Hybride piloté par événements, a été développé. Entièrement graphique, ce formalisme permet une modélisation interdisciplinaire globale du système. En séparant la dynamique continue gérée par le Bond Graph Hybride des états discrets modélisés par un automate intégré, l’approche proposée simplifie la gestion des modes de fonctionnement. Le modèle issu de cette méthodologie est également bien adapté au diagnostic robuste, réalisable sans recourir aux équations analytiques. Associée au diagnostic robuste, cette gestion des modes permet l’implémentation de stratégies de reconfiguration et de protection en présence de défaillances. / This research work constitutes a general contribution towards a simpler modelling and diagnosis of the multidisciplinary hybrid systems. Hybrid renewable energy systems where hydrogen is used to store the surplus of the power fits perfectly under this description. Such system gathers different energetic components that are needed to be connected or disconnected according to different operating conditions. These different switching configurations generate different operating modes and depend on the intermittency of the primary sources, the storage capacities and the operational availability of the different hardwares that constitute the system. The switching behaviour engenders a variable dynamic which is hard to be expressed mathematically without investigating all the operating modes. This modelling difficulty is transmitted to affect all the model-based tasks such as the diagnosis and the operating mode management. To solve this problematic, a new modelling tool, called event-driven hybrid bond graph, is developed. Entirely graphic, this formalism allows a multidisciplinary global modelling for all the operating modes at once. By separating the continuous dynamic driven by the bond graph, from the discrete states handled by an integrated automaton, this approach simplifies the management of the operating modes. The model issued using this methodology is also well-adapted to perform a robust diagnosis which is achievable without referring back to the analytical description of the model. The operating mode management, when associated with the on-line diagnosis, allows the implementation of reconfiguration strategies and protection protocols when faults are detected.

For a weighted graph with n vertices and m edges, the Minimum k-Way Cut problem is to find a partition of the vertices into k sets that minimizes the total weight of edges crossing the sets. We obtain several important structural properties of minimum multiway cuts and use them to design efficient algorithms for several multiway partition problems. We design the first algorithm for finding minimum 3-way cuts in hypergraphs, which runs in O(dmn 3) time, where d is the sum of the degrees of all the vertices. We also give an O(n 4k--lg k) algorithm for finding all minimum k-way cuts in graphs. Our algorithm is based on a divide-and-conquer method and improves all well-known existing algorithms along this divide-and-conquer method. As for approximation algorithms, we determine the tight approximation ratio of a general greedy splitting algorithm (finding a minimum k-way cut by iteratively increasing a constant number of components). Our result implies that the approximation ratio of the algorithm that iteratively increases h -- 1 components is 2 -- h/k + O(h2 /k2), which settles a well-known open problem. / For an unweighted graph and a given subset T ⊂ V of k terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of l edges (respectively, non-terminal vertices), whose removal from G separates each terminal from all the others. We show that Edge Multiterminal Cut is polynomial-time solvable for 1 = O(log n) by presenting an O(2lkT(n, m)) algorithm, where T(n, m) is the running time of finding a maximum flow in unweighted graphs. We also give three algorithms for Vertex Multiterminal Cut that run in O(k lT(n, m)), O( l!2 2l T(n, m)) and O(lk 4lT( n, m)) time respectively. Furthermore, we obtain faster algorithms for small k: Edge 3-Terminal Cut can be solved in O(1.415lT(n, m)) time, and Vertex {3, 4, 5, 6}-Terminal Cuts can be solved in O(2.059 lT(n, m)), O(2.772 lT(n, m)), O(3.349 lT(n, m)) and O(3.857 lT(n, m)) times respectively. Our results on Multiterminal Cut can be used to obtain faster algorithms for Multicut. / In this thesis, we study algorithmic issues for three closely related partition problems in graphs: k-Way Cut (k-Cut), Multiterminal Cut, and Multicut. These three problems attempt to separate a graph, by edge or vertex deletion, into several components with certain properties. The k-Way Cut (k-Cut) problem is to separate the graph into k components, the Multiterminal Cut problem is to separate a subset of vertices away from each other, and the Multicut problem is to separate some given pairs of vertices. These three problems have many applications in parallel and distributed computing, VLSI system design, clustering problems, communications network and many others. / Xiao, Mingyu. / Adviser: Andrew C. Yao. / Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3617. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 85-92). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

Lau, Siu Cheong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 51-52). / Abstracts in English and Chinese. / Chapter 1 --- In search of minimal cycles --- p.9 / Chapter 1.1 --- What do we mean by cycles? --- p.9 / Chapter 1.2 --- Integral currents --- p.10 / Chapter 1.3 --- Calibration theory --- p.13 / Chapter 2 --- Motivation from the Hodge Conjecture --- p.17 / Chapter 2.1 --- Hodge theory on Riemannian manifolds --- p.17 / Chapter 2.2 --- Hodge decomposition in Kahler manifolds --- p.19 / Chapter 2.3 --- The Hodge conjecture --- p.22 / Chapter 3 --- Variation of cycles in symmetric orbit --- p.26 / Chapter 3.1 --- Variational formulae --- p.26 / Chapter 3.2 --- Stability of cycles in Sm and CPn --- p.29 / Chapter 3.3 --- Symmetric orbit in Euclidean space --- p.31 / Chapter 3.4 --- Projective spaces in simple Jordan algebra --- p.39 / Chapter 3.4.1 --- Introduction to simple Jordan algebra --- p.39 / Chapter 3.4.2 --- Projective spaces as symmetric orbits --- p.41 / Chapter 3.4.3 --- Computation of second fundamental form --- p.43 / Chapter 3.4.4 --- The main theorem --- p.45 / Chapter 3.5 --- Future directions --- p.49 / Bibliography --- p.51

關於有唯一禁子圖的改邊問題的多項式核心無H加/删/加删邊問題求是否可能加/删/加删至多k條邊於一圖使其無任何與H同構的誘導子圖。此乃計算機科學基本問題之一，其研究廣泛。此題對任意固定H為NP完全且固定參數可解。本文研究無H改邊問題之多項式核心；其存在視H之結構而定。之分類在當H為一圈，路徑或三聯通圖時則完全，當H為删一邊於完全圖之結果時則近完全，當H為樹時則部分此結果加強對無H改邊問題之認識。本文的思路與工具益未來研究，或有助於無H改邊問題多項式核心存在二分定理之發現。 / The H-free edge completion (deletion, editing) problem asks whether it is possible to add to (delete from, add to and delete from) a graph at most k edges so that no induced sub graph isomorphic to H remains. These problems are fundamental in computer science and were studied extensively. They are NP-complete and fixed-parameter tractable for every fixed H. / In this thesis, we study polynomial kernels for H-free edge modification problems, as their existence depends on the structure of H. We characterise their existence completely when H is a path, cycle or 3-connected graph, almost completely when H is one edge short of a complete graph, and partially when H is a tree. / These results enhance our understanding of H-free edge modification problems significantly. Our ideas and tools can be useful to future studies and may lead eventually to a dichotomy theorem on the existence of polynomial kernels for H-free edge modification problems. / Detailed summary in vernacular field only. / Cai, Yufei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 97-99). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese. / Chapter 1 --- Preliminaries --- p.1 / Chapter 1.1 --- Edge modification problems and kernelisation --- p.2 / Chapter 1.2 --- Main results --- p.4 / Chapter 1.3 --- The lack of polynomial kernels --- p.5 / Chapter 1.4 --- Conventions and organisation --- p.8 / Chapter 2 --- Component Design --- p.11 / Chapter 2.1 --- Weighted satisficability on selective formulas --- p.12 / Chapter 2.2 --- 4-cycle --- p.15 / Chapter 2.3 --- The general scheme of component design --- p.20 / Chapter 2.4 --- Applications --- p.26 / Chapter 3 --- Local Alteration --- p.31 / Chapter 3.1 --- Bigger forbidden subgraphs from smaller ones --- p.32 / Chapter 3.2 --- Lifting the quarantine --- p.37 / Chapter 4 --- Circuit Implementation --- p.43 / Chapter 4.1 --- Monotone circuits --- p.44 / Chapter 4.2 --- Centralisation --- p.45 / Chapter 4.3 --- Implementation --- p.48 / Chapter 5 --- Kernel for Diamond-Free Edge Deletion --- p.55 / Chapter 5.1 --- Diamond-graphs --- p.56 / Chapter 5.2 --- The invariant things --- p.59 / Chapter 5.3 --- Correctness --- p.61 / Chapter 5.4 --- Lockets --- p.64 / Chapter 5.5 --- Representative systems of diamonds --- p.68 / Chapter 5.6 --- Kernel size --- p.70 / Chapter 6 --- Conclusions --- p.73 / Chapter 6.1 --- 3-connected forbidden subgraphs --- p.74 / Chapter 6.2 --- Cycles, paths and nearly complete graphs --- p.76 / Chapter 6.3 --- Trees --- p.77 / Chapter 6.4 --- Open problems --- p.79 / Chapter A --- List of Trees --- p.81 / Chapter B --- List of Problems --- p.83 / Chapter C --- Glossary --- p.87 / Chapter D --- Bibliography --- p.96

Chan Hoi-Yeung = 網絡與競爭系統的物理 : 個體為本模型中的網絡效應 / 陳凱揚. / Thesis submitted in: September 2005. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 191-197). / Text in English; abstracts in English and Chinese. / Chan Hoi-Yeung = Wang luo yu jing zheng xi tong de wu li : ge ti wei ben mo xing zhong de wang luo xiao ying / Chen Kaiyang. / Abstract --- p.i / Acknowledgments --- p.v / Contents --- p.vii / Chapter 1 --- Overview --- p.1 / Chapter I --- Networks --- p.3 / Chapter 2 --- Networks in nature --- p.4 / Chapter 2.1 --- Introduction --- p.4 / Chapter 2.2 --- Terminology of the networks studies --- p.6 / Chapter 2.2.1 --- Nodes --- p.6 / Chapter 2.2.2 --- Links --- p.6 / Chapter 2.2.3 --- Adjacency matrix --- p.9 / Chapter 2.2.4 --- Connectivity --- p.10 / Chapter 2.2.5 --- Clustering coefficient --- p.11 / Chapter 2.2.6 --- Shortest path --- p.11 / Chapter 2.2.7 --- Connectivity correlation --- p.12 / Chapter 2.3 --- Topology in the real-world networks --- p.13 / Chapter 2.3.1 --- The Internet --- p.13 / Chapter 2.3.2 --- The WWW --- p.15 / Chapter 2.3.3 --- Collaboration networks --- p.15 / Chapter 2.3.4 --- Food webs --- p.16 / Chapter 2.3.5 --- Power grids --- p.17 / Chapter 2.4 --- Discussion --- p.17 / Chapter 3 --- Review on Network Models --- p.19 / Chapter 3.1 --- Introduction --- p.19 / Chapter 3.2 --- Graph Theory --- p.20 / Chapter 3.2.1 --- Classical random graph --- p.20 / Chapter 3.3 --- Evolving networks --- p.23 / Chapter 3.3.1 --- Random growing network --- p.23 / Chapter 3.3.2 --- Fitness growing network --- p.25 / Chapter 3.3.3 --- Barabasi-Albert model --- p.27 / Chapter 3.3.4 --- Fitness model --- p.31 / Chapter 3.4 --- Lattice --- p.33 / Chapter 3.4.1 --- Regular hypercubic lattices (Periodic) --- p.33 / Chapter 3.4.2 --- Regular hypercubic lattices (Free boundary conditions) . --- p.35 / Chapter 3.5 --- Discussion --- p.35 / Chapter 4 --- Network Properties --- p.38 / Chapter 4.1 --- More derivations on existing models --- p.38 / Chapter 4.1.1 --- Classical random graphs --- p.38 / Chapter 4.1.2 --- Barabasi-Albert model --- p.40 / Chapter 4.1.3 --- Fitness Model --- p.42 / Chapter 4.1.4 --- Regular hypercubic lattices (Periodic) --- p.45 / Chapter 4.2 --- New model --- p.48 / Chapter 4.2.1 --- Fitness-BA hybrid model --- p.48 / Chapter 4.3 --- Link removal --- p.55 / Chapter 4.3.1 --- Introduction --- p.55 / Chapter 4.3.2 --- Formalism in connectivity --- p.55 / Chapter 4.3.3 --- Pruned BA Model --- p.56 / Chapter 4.4 --- Link addition --- p.58 / Chapter 4.4.1 --- Introduction --- p.58 / Chapter 4.4.2 --- Regular hypercubic lattices (Periodic) --- p.58 / Chapter 4.5 --- Discussion --- p.60 / Chapter II --- Games --- p.62 / Chapter 5 --- Review on Agent-based models of competing population --- p.63 / Chapter 5.1 --- Introduction --- p.63 / Chapter 5.2 --- The El Farol Bar attendance problem --- p.65 / Chapter 5.2.1 --- Model --- p.65 / Chapter 5.2.2 --- Strategies --- p.66 / Chapter 5.2.3 --- Discussion --- p.66 / Chapter 5.3 --- Minority game --- p.67 / Chapter 5.3.1 --- Model --- p.67 / Chapter 5.3.2 --- Strategies --- p.68 / Chapter 5.3.3 --- Attendance --- p.69 / Chapter 5.3.4 --- History and quasi-Eulerian state --- p.69 / Chapter 5.3.5 --- Success rate and Hamming distance --- p.71 / Chapter 5.3.6 --- Volatility --- p.73 / Chapter 5.3.7 --- Crowd-anticrowd theory --- p.75 / Chapter 5.3.8 --- Discussion --- p.76 / Chapter 6 --- B-A-R model : Dynamics --- p.78 / Chapter 6.1 --- Model --- p.78 / Chapter 6.2 --- Results: Plateaux and periodicity --- p.81 / Chapter 6.3 --- A microscopic view: Agents' decisions and strategy performance --- p.86 / Chapter 6.4 --- A macroscopic view: Bit-string patterns --- p.92 / Chapter 6.4.1 --- The history space --- p.92 / Chapter 6.4.2 --- Bit-string statistics of different states --- p.94 / Chapter 6.5 --- The (max = 1 states --- p.97 / Chapter 6.5.1 --- Values of wm3iX --- p.97 / Chapter 6.5.2 --- "Strategy ranking evolvement: ni, (w)" --- p.101 / Chapter 6.5.3 --- Substates . --- p.105 / Chapter 7 --- B-A-R model : Formalism --- p.108 / Chapter 7.1 --- Resource level at transitions of Cmax = 0 state --- p.108 / Chapter 7.2 --- Resource levels at transitions of Cmax 二 1 states --- p.109 / Chapter 7.2.1 --- Method --- p.109 / Chapter 7.2.2 --- Lmin for upper substate --- p.110 / Chapter 7.2.3 --- Lmin for lower substate --- p.113 / Chapter 7.3 --- Discussion --- p.116 / Chapter 8 --- B-A-R model : Statistics --- p.121 / Chapter 8.1 --- Problem --- p.121 / Chapter 8.2 --- Bit-string statistics --- p.122 / Chapter 8.2.1 --- Allowed transitions --- p.122 / Chapter 8.2.2 --- Grouping the history space --- p.122 / Chapter 8.2.3 --- "Grouping the states, Cmax" --- p.127 / Chapter 8.2.4 --- "Labelling each state, /(C)" --- p.129 / Chapter 8.3 --- Discussion --- p.130 / Chapter III --- Networked games --- p.131 / Chapter 9 --- Networked minority game --- p.132 / Chapter 9.1 --- Model --- p.132 / Chapter 9.2 --- Preliminary results: Agents' success rates --- p.133 / Chapter 9.3 --- Ranking the strategies --- p.135 / Chapter 9.3.1 --- Ranking pattern --- p.136 / Chapter 9.3.2 --- Fraction of strategies in each rank --- p.140 / Chapter 9.4 --- Number of agents using a best strategy belonging to rank r --- p.141 / Chapter 9.4.1 --- Unconnected population --- p.141 / Chapter 9.4.2 --- Networked population . --- p.142 / Chapter 9.5 --- Application: Mean success rate --- p.143 / Chapter 9.6 --- Mean success rate of agents with degree k --- p.147 / Chapter 9.7 --- Application in other networks --- p.149 / Chapter 9.8 --- Discussion --- p.151 / Chapter 10 --- Interacting agents: Networked B-A-R model --- p.154 / Chapter 10.1 --- Model --- p.154 / Chapter 10.2 --- The quasi-Eulerian state (wmax = 1/2 state) --- p.155 / Chapter 10.3 --- The emergent states --- p.159 / Chapter 10.3.1 --- General results --- p.159 / Chapter 10.3.2 --- The Cmax = 0 state --- p.160 / Chapter 10.3.3 --- The Cmax = 1 state --- p.161 / Chapter 10.4 --- Discussion --- p.162 / Chapter IV --- Conclusion --- p.164 / Chapter 11 --- Conclusion --- p.165 / Chapter V --- Appendices --- p.172 / Chapter A --- List of symbols --- p.173 / Chapter A.1 --- Networks --- p.173 / Chapter A.2 --- Games --- p.174 / Chapter A.3 --- Networked games --- p.176 / Chapter B --- Distance distribution in classical random graphs --- p.177 / Chapter B.1 --- Method --- p.177 / Chapter B.2 --- Distance distribution --- p.177 / Chapter B.3 --- Behaviour at small L --- p.178 / Chapter B.4 --- Behaviour at large L --- p.179 / Chapter C --- Co-ordination number in infinite hypercubic lattice --- p.181 / Chapter C.1 --- Method --- p.181 / Chapter C.1.1 --- ID lattice --- p.181 / Chapter C.1.2 --- 2D square lattice --- p.182 / Chapter C.1.3 --- Higher dimension hypercubic lattices --- p.183 / Chapter C.2 --- Coefficients --- p.185 / Chapter D --- Connectivity distribution in fitness-BA hybrid model --- p.187 / Chapter D.1 --- Mean field approach --- p.187 / Chapter D.2 --- Connectivity distribution --- p.188 / Chapter D.3 --- Power-law exponent --- p.190 / Bibliography --- p.191

In this thesis, we study geometric intersection representations of graphs. For a fixed class, the well-known recognition problem asks whether a given graph belongs to this class. We study a generalization of this problem called partial representation extension. Its input consists of a graph with a partial representation, so a part of the graph is pre-drawn. The problems asks whether this partial representation can be extended to a representation of the entire graph. We study this problem for classes of interval graphs, proper interval graphs, unit interval graphs and chordal graphs (in the setting of subtrees-in-tree representations). We give linear-time algorithms for the first two classes and an almost quadratic-time algorithm for unit interval graphs. For chordal graphs, we consider different versions of the problem and show that almost all cases are NP-complete. Even though the classes of proper and unit interval graphs are known to be equal, the partial representation extension problem distinguishes them. For unit interval graphs, it poses additional restrictions concerning precise positions of intervals, and we describe a new structure of unit interval representations to deal with this. 1

Ce travail de thèse présente différentes contributions pour la génération automatique de modèles représentant les Systèmes Dynamiques Hybrides (SDH) caractérisés par plusieurs modes de fonctionnement. Les composants du système (notamment les capteurs) peuvent être manuellement sélectionnée ou automatiquement exportés à partir des données de Conception Assistée par Ordinateur (CAO) ; ces éléments sont ensuite interconnectés pour reproduire le modèle complet du système industriel. Une fois le modèle créé, des schémas-blocs de simulation et de diagnostic, ainsi que la Matrice de Signature de Fautes (FSM) seront produits. Le logiciel est basé sur les Bonds Graph Hybrides ; la présence de commutations engendre des dynamiques variables (notamment des changements de causalité). Pour lever ces verrous, différents algorithmes sont proposés. En comparaison des logiciels existants, les algorithmes proposés sont valides pour les systèmes continus, discrets ou hybrides. Les théories et algorithmes développés sont appliqués sur un système ferroviaire de freinage électropneumatique. / This thesis work contributes to perform a automed model builder for Hybrid Dynamic Systems (HDS) with numerous modes. Technological components including sensors with an iconic format can be automatically export from a computer-aided design (CAD) scheme or manually drag from database and interconnected, so as to produce the overall HDS model, following industrial technological schemes. Once the model has been created, block diagram for simulation and diagnosis and a Fault Signature Matrix (FSM) could be generated.The theory and algorithm behind the software are based on Hybrid Bond Graphs (HBG). The switching behaviour engenders variables dynamics (particularly causal changes). To solve this problematic, news algorithm are performed. Compared with developed programs for automated modelling, the presented algorithm are valid for continuous, discrete and hybrid systems. The theory is illustrated by an industrial application which consists of the pneumo-electrical control of rolling stock.