Dissertations / Theses on the topic 'Geodetic graphs'

How many equivalence classes of geodesic rays does a graph contain? How many bounded automorphisms does a planar graph have? Neimayer and Watkins studied these two questions and answered them for a certain class of graphs. Using the concept of excess of a vertex, the class of graphs that Neimayer and Watkins studied are extended to include graphs with positive excess at each vertex. The results of this paper show that there are an uncountable number of geodesic fibers for graphs in this extended class and that for any graph in this extended class the only bounded automorphism is the identity automorphism.

In this thesis we are interested in the problem of counting pairs of closed geodesics in metric graphs. We start with counting pairs of closed geodesics ordered by their word length on the metric graph and such that the difference of their geometric lengths is in a prescribed interval. Then we study a similar problem but where the interval is now allowed to shrink at a specific rate as the word length tends to infinity. Next we study a variant on this problem where we fix a set of generators for the fundamental group of the graph and then order the closed geodesics by the word length of the corresponding conjugacy class with respect to these generators. Again we may also allow the interval to shrink at an appropriate rate. We also study a restricted version of our first problem where we only count null homologous closed geodesics. The final counting problem we study differs from the previous ones by counting pairs of geodesic paths instead of pairs of closed geodesics. These geodesic paths are also ordered by their word lengths in the metric graph and again the difference between the geometric lengths of these geodesic paths lies in a fixed interval. The techniques we use in our study include coding metric graphs by subshifts of finite type and the concepts from the thermodynamic formalism that appear in the ergodic theory of these systems. In particular, we use the spectral properties of transfer operators and their relationship to pressure and entropy.

The aim of this thesis is creation of 3D model by a selected program. In the introduction of the thesis is a brief description of chosen object – St. Václav's temple in Brno. Next follows preparation works before measuring, creating of measuring net by GNSS and measuring of object by tachymetric method. In the following chapters is briefly described 2D and 3D computer graphic and program AutoCAD Civil 3D, which was used for create resulting model of the object.

The medial axis is an important shape representation and the computation of the medial axis is a fundamental research problem in computer graphics. Practically, the medial axis is widely used in various aspects of computer graphics, such as shape analysis, image segmentation, skeleton extraction and mesh generation and so forth. However, the applications of the medial axis have been limited by its sensitivity to boundary perturbations. This characteristic may lead to a number of noise branches and increase the complexity of the medial axis. To solve the sensitivity problem, it is critical to simplify the medial axis. This thesis first investigates the algorithms for computing medial axes of different input shapes. Several algorithms for the filtration of medial axes are then reviewed, such as the local importance measurement algorithms, boundary smoothness algorithms, and the global algorithms. Two novel algorithms for the simplification of the medial axis are proposed to generate a stable and simplified medial axis as well as its reconstructed boundary. The developed Global Geodesic Slope(GGS) algorithm for the medial axis simplification is based on the global geodesic slope defined in this thesis, which combines the advantages of the global and the local algorithms. The GGS algorithm prunes the medial axis according to local features as well as the relative size of the shape. It is less sensitive to boundary noises than the local algorithms, and can maintain the features of the shape in highly concave regions while the global algorithms may not. The other simplification algorithm we propose is the Accumulated Hyperbolic Distance(AHD) algorithm. It directly uses the evaluation criterion of the error, accumulated hyperbolic distance defined in this thesis, as the pruning measurement in the filtration process. It guarantees the upper bound of the error between the reconstructed shape and the original one within the defined threshold. The AHD algorithm avoids sudden changes of the reconstructed shape as the defined threshold changes.<br>published_or_final_version<br>Computer Science<br>Master<br>Master of Philosophy

Made available in DSpace on 2014-06-11T19:22:25Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-04-24Bitstream added on 2014-06-13T19:06:24Z : No. of bitstreams: 1 magnajr_jp_me_prud.pdf: 1562358 bytes, checksum: 707020e37c54b516d7377926b9cefee2 (MD5)<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)<br>Os avanços tecnológicos nos métodos de posicionamento, sobretudo os sistemas de posicionamento por satélite, fizeram com que diversos países atualizassem e/ou revisassem suas estruturas geodésicas fundamentais. Na busca de explorar a total potencialidade das novas tecnologias, as principais mudanças convergiram para a adoção de referenciais geocêntricos, de caráter global e cuja origem coincide com o centro de massa da Terra. A atualização de uma rede geodésica implica na mudança de coordenadas e, consequentemente, alteração da geometria da rede, evidenciando as distorções nela existentes. Para manter a integridade e topologia da rede geodésica é necessário que se proceda a uma modelagem das distorções. Neste contexto, este trabalho apresenta uma metodologia de modelagem de distorções entre realizações de sistemas de referência geodésicos, baseada na utilização de grades regulares. Amplamente utilizada, a modelagem baseada em grades é uma forma padronizada de se realizar a conversão entre referenciais sem a necessidade de aplicação de modelos complexos por parte dos usuários. Nessa dissertação, foram geradas grades de distorção com diferentes espaçamentos, cobrindo todo o território brasileiro, para a modelagem das distorções entre as redes SAD 69 (realização de 1996) e SIRGAS 2000. A geração e aplicação das grades esta pautada no desenvolvimento de aplicativos computacionais com utilização do método de Shepard na geração da grade e da função bilinear na interpolação das distorções a partir dos pontos da grade. A metodologia foi avaliada através de estações de teste, onde os resultados mostraram-se promissores. Nos melhores casos, houve redução de aproximadamente 50% no erro médio quadrático das coordenadas após a modelagem com um indicador médio de precisão de 0,179m.<br>The technological advances in the positioning methods, mainly in the satellite positioning systems conduced several countries to update and review their fundamental geodetic networks. In order to explore the full potential of these new technologies, the main changes converged to the adoption of geocentric reference systems, that are global and whose origin coincides with the Earth mass center. The geodetic network update implies in coordinate changes and, consequently, the network geometry changes, evidencing the existent distortions. To preserve the data set integrity and topology it is required a modeling of the distortions. In this context, this work presents a distortion modeling methodology between reference frames based on regular grids. Widely used, the modeling based on grids is a standardized and less complex way to accomplish the conversion between frames without the necessity to apply rigorous models by the user. In this research, distortion grids were generated with different sizes and covering all Brazilian s territory to model the distortion between the SAD 69 (1996) and SIRGAS 2000 frames. The grid generation and application are based on computational software development by the use of the Shepard s method in the grid generation and the bilinear function in the distortion interpolation from the grid points. The methodology was evaluated through test stations where the results were promising. In the best cases, the root mean squared error in the coordinates was reduced 50% after the modeling with an average precision indicator of 0,179m.

Cette thèse porte sur le problème de la couverture d'ensembles finis dans une structure discrète. Cette problématique très générale permet de nombreuses approches et nous faisons l'étude de certaines d'entre elles. Le premier chapitre introduit les notions qui seront indispensables à la bonne compréhension de cette thèse et fait un bref état de l'art sur certains problèmes de couvertures, en particulier le problème de domination dans les graphes. Le second chapitre aborde la domination de puissance, une variante du problème de domination qui a la particularité qu'on lui adjoint un phénomène de propagation. Nous étudions ce problème pour les grilles triangulaires et les grilles carrées de dimension 3. Dans le troisième chapitre, nous revenons à la domination classique mais dans un contexte ludique, avec le jeu de domination Maker-Breaker. Nous étudions la complexité du problème consistant à décider quel joueur gagne, la durée minimale d'une partie si les deux joueurs jouent parfaitement, et dérivons ce jeu pour la domination totale et dans une version Avoider-Enforcer. Le quatrième chapitre traite du nombre géodésique fort, un problème qui a la particularité de se couvrir à l'aide de plus courts chemins dans le graphe. Nous étudions le nombre géodésique fort de plusieurs classes de graphes ainsi que son comportement en relation avec le produit cartésien. Enfin, dans le cinquième chapitre, nous quittons le domaine des graphes pour étudier l'identification de points dans le plan par des disques. En plus de couvrir chaque point d'un certain ensemble par des disques, nous souhaitons que l'ensemble des disques couvrants chaque point soit unique. Nous donnons des résultats dans certains cas particuliers, des bornes dans le cas général et étudions la complexité du problème quand le rayon des disques est fixé<br>This PhD thesis concerns the problem of covering finite sets in a discrete structure. This very general issue allows numerous approaches and we study some of them. The first chapter introduces the notions that are essentials to the understanding of this thesis and makes a brief state of the art on some covering problems, including the domination problem. The second chapter addresses the power dominating problem, a variation of the dominating problem with a propagation process. We study this problem on triangular grids and square grids of dimension 3. In the third chapter, we come back to the classical domination but in the context of a game, with the Maker-Breaker domination game. We study the complexity of the problem of deciding which player has a winning strategy and the minimum duration of a game if both players play perfectly. We also derive this problem for total domination and for an Avoider-Enforcer version. The fourth chapter is about the strong geodetic number: a problem with the distinctive characteristic that the covering is made by shortest paths in the graph. We study the strong geodetic number of several graph classes and its behaviour for the Cartesian product. Lastly, in the fifth chapter, we leave the realm of graphs to study the identification of points using disks. More than just covering every point of a certain set, the subset of disks covering each point must be unique to that point. We give results on particular configurations, bounds on the general case and we study the complexity of the problem when the radius of the disks is fixed

Vários métodos tradicionais de segmentação de imagens, como a transformada de watershed de marcado- res e métodos de conexidade fuzzy (Relative Fuzzy Connectedness- RFC, Iterative Relative Fuzzy Connected- ness - IRFC), podem ser implementados de modo eficiente utilizando o método em grafos da Transformada Imagem-Floresta (Image Foresting Transform - IFT). No entanto, a carência de termos de regularização de fronteira em sua formulação fazem com que a borda do objeto segmentado possa ser altamente irregular. Um modo de contornar isto é por meio do uso de restrições de forma do objeto, que favoreçam formas mais regulares, como na recente restrição de convexidade geodésica em estrela (Geodesic Star Convexity - GSC). Neste trabalho, apresentamos uma nova restrição de forma, chamada de Faixa de Restrição Geodésica (Geodesic Band Constraint - GBC), que pode ser incorporada eficientemente em uma sub-classe do fra- mework de corte em grafos generalizado (Generalized Graph Cut - GGC), que inclui métodos pela IFT. É apresentada uma prova da otimalidade do novo algoritmo em termos de um mínimo global de uma função de energia sujeita às novas restrições de borda. A faixa de restrição geodésica nos ajuda a regularizar a borda dos objetos, consequentemente melhorando a segmentação de objetos com formas mais regulares, mantendo o baixo custo computacional da IFT. A GBC pode também ser usada conjuntamente com um mapa de custos pré estabelecido, baseado em um modelo de forma, de modo a direcionar a segmentação a seguir uma dada forma desejada, com grau de liberdade de escala e demais deformações controladas por um parâmetro único. Essa nova restrição também pode ser combinada com a GSC e com as restrições de polaridade de borda sem custo adicional. O método é demonstrado em imagens naturais, sintéticas e médicas, sendo estas provenientes de tomografias computadorizadas e de ressonância magnética.<br>In this work, we present a novel boundary constraint, which we denote as the Geodesic Band Constraint (GBC), and we show how it can be efficiently incorporated into a subclass of the Generalized Graph Cut framework (GGC). We include a proof of the optimality of the new algorithm in terms of a global minimum of an energy function subject to the new boundary constraints. The Geodesic Band Constraint helps regularizing the boundary, and consequently, improves the segmentation of objects with more regular shape, while keeping the low computational costs of the Image Foresting Transform (IFT). It can also be combined with the Geodesic Star Convexity prior, and with polarity constraints, at no additional cost.

Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2016-12-09T16:43:52Z No. of bitstreams: 2 Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)<br>Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-12-13T19:11:50Z (GMT) No. of bitstreams: 2 Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)<br>Made available in DSpace on 2016-12-13T19:11:50Z (GMT). No. of bitstreams: 2 Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-11-30<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES<br>In this work, we consider the parameter hull number in two graph convexities, the P3- convexity and the geodetic convexity. In the P3-convexity, we present results on the P3- hull number on the Cartesian product, strong product and lexicographic product of graphs. In special, regarding to the Cartesian product, we proved a complexity result, in which we show, given a graph G resulting of a Cartesian product of two graphs and a positive integer k, is NP-complete to decide whether the P3-hull number of G is less than or equal k. We also consider the P3-hull number on complementary prisms GG of connected graphs G and G, in which we show a tighter upper bound than that found in the literature. In the geodetic convexity, we show results of the hull number on complementary prisms GG when G is a tree, when G is a disconnected graph and when G is a cograph. Finally, we also show that in the geodetic convexity, the hull number on the complementary prism GG is unlimited on connected graphs G and G, unlike what happens in the P3-convexity<br>Nesta dissertação, consideramos o parâmetro número envoltório em duas convexidades em grafos, a convexidade P3 e a convexidade geodética. Na convexidade P3, obtivemos resultados do número envoltório P3 para o produto Cartesiano, produto forte e produto lexicográfico de grafos. Em especial, em relação ao produto Cartesiano, obtivemos um resultado de complexidade, no qual mostramos que, dado um grafo G, resultante de um produto Cartesiano de dois grafos e um inteiro positivo k, é NP-completo decidir se o número envoltório P3 de G é menor ou igual a k. Também consideramos o número envoltório P3 para prismas complementares GG de grafos G e G conexos, em que mostramos um limite superior um pouco mais justo do que o encontrado na literatura. Na convexidade geodética, mostramos resultados do número envoltório para prismas complementares GG quando G é uma árvore, quando G é um grafo desconexo e quando G é um cografo. Por fim, também mostramos que na convexidade geodética o número envoltório do prisma complementar GG pode ser ilimitado para grafos G e G ambos conexos, diferentemente do que ocorre na convexidade P3.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-01-02T14:12:29Z No. of bitstreams: 2 Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)<br>Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-03T09:39:46Z (GMT) No. of bitstreams: 2 Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)<br>Made available in DSpace on 2017-01-03T09:39:46Z (GMT). No. of bitstreams: 2 Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-12-01<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES<br>From Carathéodory’s theorem arises the definition of the Carathéodory number for graphs. This number is well-known for monophonic and triangle-path convexities. It is limited for some classes of graphs on P3 and geodesic convexities but is known to be unlimited only on P3-convexity. Driven by open questions in geodesic convexity, in this work we study the Carathéodory number in this convexity. For general graphs and cartesian product, we prove that the Carathéodory number is unlimited. We characterize the Carathéodory number for trees, cographs, for the complementary prisms of cographs and simple graphs Kn, Pn and Cn, for the complement and the complementary prism of the graph KnKn and for the cartesian products PnxPm, KnxKm and PnxKm.<br>Do Teorema de Carathéodory da geometria surge a definição do número de Carathéodory para grafos. Este número é bem determinado na convexidade monofônica e na convexidade de caminho de triângulos. Ele é limitado para algumas classes de grafos nas convexidades P3 e geodésica, mas só foi provado ser ilimitado na convexidade P3. Motivados pelas questões em aberto na convexidade geodosésica, neste trabalho estudamos o número de Carathéodory nesta convexidade. Para grafos gerais e para produtos cartesianos, provamos que o número de Carathéodory é ilimitado. Determinamos o número de Carathéodory para árvores, cografos, para o prisma complementar de cografos e dos grafos simples Kn, Pn e Cn, para o complemento e prisma complementar do grafo KnKn e para os produtos cartesianos PnxPm, KnxKm e PnxKm.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico<br>In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P&#8727; 3 . We show a relation between the geodetic convexity and the P&#8727; 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P&#8727; 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P&#8727; 3 in graphs with few P4âs.<br>In this dissertation we present complexity results related to the hull number and the convexity number for P3 convexity. We show that the hull number and the convexity number are NP-hard even for bipartite graphs. Inspired by our research in convexity based on paths, we introduce a new convexity, where we defined as convexity of induced paths of order three or P&#8727; 3 . We show a relation between the geodetic convexity and the P&#8727; 3 convexity when the graph is a join of a Km with a non-complete graph. We did research in geometric convexity and from that we characterized graph classes under some convexities such as the star florest in P3 convexity, chordal cographs in P&#8727; 3 convexity, and the florests in TP convexity. We also demonstrated convexities that are geometric only in specific graph classes such as cographs in P4+-free convexity, F free graphs in F-free convexity and others. Finally, we demonstrated some results of geodesic convexity and P&#8727; 3 in graphs with few P4âs.

Segmentar uma imagem consiste em particioná-la em regiões relevantes para uma dada aplicação, como para isolar um objeto de interesse no domínio de uma imagem. A segmentação é um dos problemas mais fundamentais e desafiadores em processamento de imagem e visão computacional. Ela tem desempenhado um papel importante, por exemplo, na pesquisa em neurologia, envolvendo imagens de Ressonância Magnética (RM), para fins de diagnóstico e tratamento de doenças relacionadas com alterações na anatomia do cérebro humano. Métodos de segmentação baseados na transformada imagem- floresta (IFT, Image Foresting Transform), com funções de conexidade suaves, possuem resultados ótimos, segundo o critério da otimalidade dos caminhos descrito no artigo original da IFT, e têm sido usados com sucesso em várias aplicações, como por exemplo na segmentação de imagens RM de 1.5 Tesla. No entanto, esses métodos carecem de restrições de regularização de borda, podendo gerar segmentações com fronteiras muito irregulares e indesejadas. Eles também não distinguem bem entre bordas similares com orientações opostas, e possuem alta sensibilidade à estimativa dos pesos das arestas do grafo, gerando problemas em imagens com efeitos de inomogeneidade. Nesse trabalho são propostas extensões da IFT, do ponto de vista teórico e experimental, através do uso de funções de conexidade não suaves, para a segmentação interativa de imagens por região. A otimalidade dos novos métodos é suportada pela maximização de energias de corte em grafo, ou como o fruto de uma sequência de iterações de otimização de caminhos em grafos residuais. Como resultados principais temos: O projeto de funções de conexidade mais adaptativas e flexíveis, com o uso de pesos dinâmicos, que permitem um melhor tratamento de imagens com forte inomogeneidade. O uso de grafos direcionados, de modo a explorar a polaridade de borda dos objetos na segmentação por região, e o uso de restrições de forma que ajudam a regularizar a fronteira delineada, favorecendo a segmentação de objetos com formas mais regulares. Esses avanços só foram possíveis devido ao uso de funções não suaves. Portanto, a principal contribuição desse trabalho consiste no suporte teórico para o uso de funções não suaves, até então evitadas na literatura, abrindo novas perpectivas na pesquisa de processamento de imagens usando grafos.<br>Segmenting an image consist in to partition it into relevant regions for a given application, as to isolate an object of interest in the domain of an image. Segmentation is one of the most fundamental and challenging problems in image processing and computer vision. It has played an important role, for example, in neurology research, involving images of Magnetic Resonance (MR), for the purposes of diagnosis and treatment of diseases related to changes in the anatomy of the human brain. Segmentation methods based on the Image Foresting Transform (IFT), with smooth connectivity functions, have optimum results, according to the criterion of path optimality described in the original IFT paper, and have been successfully used in many applications as, for example, the segmentation of MR images of 1.5 Tesla. However, these methods present a lack of boundary regularization constraints and may produce segmentations with quite irregular and undesired boundaries. They also do not distinguish well between similar boundaries with opposite orientations, and have high sensitivity to the arc-weight estimation of the graph, producing poor results in images with strong inhomogeneity effects. In this work, we propose extensions of the IFT framework, from the theoretical and experimental points of view, through the use of non-smooth connectivity functions for region-based interactive image segmentation. The optimality of the new methods is supported by the maximization of graph cut energies, or as the result of a sequence of paths optimizations in residual graphs. We have as main results: The design of more adaptive and flexible connectivity functions, with the use of dynamic weights, that allow better handling of images with strong inhomogeneity. The use of directed graphs to exploit the boundary polarity of the objects in region-based segmentation, and the use of shape constraints that help to regularize the segmentation boundary, by favoring the segmentation of objects with more regular shapes. These advances were only made possible by the use of non-smooth functions. Therefore, the main contribution of this work is the theoretical support for the usage of non-smooth functions, which were until now avoided in literature, opening new perspectives in the research of image processing using graphs.

Dans les domaines de l’imagerie médicale et de la vision par ordinateur, la segmentation joue un rôle crucial dans le but d’extraire les composantes intéressantes d’une image ou d’une séquence d’images. Elle est à l’intermédiaire entre le traitement d’images de bas niveau et les applications cliniques et celles de la vision par ordinateur de haut niveau. Ces applications de haut niveau peuvent inclure le diagnostic, la planification de la thérapie, la détection et la reconnaissance d'objet, etc. Parmi les méthodes de segmentation existantes, les courbes géodésiques minimales possèdent des avantages théoriques et pratiques importants tels que le minimum global de l’énergie géodésique et la méthode bien connue de Fast Marching pour obtenir une solution numérique. Dans cette thèse, nous nous concentrons sur les méthodes géodésiques basées sur l’équation aux dérivées partielles, l’équation Eikonale, afin d’étudier des méthodes précises, rapides et robustes, pour l’extraction de structures tubulaires et la segmentation d’image, en développant diverses métriques géodésiques locales pour des applications cliniques et la segmentation d’images en général<br>In the fields of medical imaging and computer vision, segmentation plays a crucial role with the goal of separating the interesting components from one image or a sequence of image frames. It bridges the gaps between the low-level image processing and high level clinical and computer vision applications. Among the existing segmentation methods, minimal geodesics have important theoretical and practical advantages such as the global minimum of the geodesic energy and the well-established fast marching method for numerical solution. In this thesis, we focus on the Eikonal partial differential equation based geodesic methods to investigate accurate, fast and robust tubular structure extraction and image segmentation methods, by developing various local geodesic metrics for types of clinical and segmentation tasks. This thesis aims to applying different geodesic metrics based on the Eikonal framework to solve different image segmentation problems especially for tubularity segmentation and region-based active contours models, by making use of more information from the image feature and prior clinical knowledges. The designed geodesic metrics basically take advantages of the geodesic orientation or anisotropy, the image feature consistency, the geodesic curvature and the geodesic asymmetry property to deal with various difficulties suffered by the classical minimal geodesic models and the active contours models. The main contributions of this thesis lie at the deep study of the various geodesic metrics and their applications in medical imaging and image segmentation. Experiments on medical images and nature images show the effectiveness of the presented contributions

碩士<br>國立臺灣大學<br>數學研究所<br>93<br>All graphs in this thesis are simple, i.e., finite, undirected, loopless and without multiple edges. For any two vertices u and v of a graph G, a u-v geodesic is a path of length d(u, v). The set I(u, v) consists of all vertices lying on some u-v geodesic of G.. If S is a subset of V(G), then I(S) is the union of all sets I(u, v) for u and v in S. The geodetic number g(G) is the minimum cardinality among the subset S of V(G) with I(S)=V(G). In section 1, we introduce some definitions, which is used in this thesis. In section 2, we discuss geodetic numbers on Cartesian products of graphs. The main result is g(G) ≦ g(G□H) for any two graphs G and H. And g(G)=g(G□H) for some H with some special condition. In section 3, we discuss an upper bound of geodetic numbers of cographs. A 2-N-dominating set of a graph G is a vertex subset D such that every vertex not in D is adjacent to two distinct non-adjacent vertices in D. Denote by g2(G) the minimum cardinality of a 2-N-dominating set in G. And we discuss the relation between geodetic numbers and 2-N-domination numbers. In section 4, we define tree-cographs and term f-domination. And we design an algorithm to find the 2-N-domination number of a tree-cograph.

碩士<br>東海大學<br>數學系<br>91<br>For two vertices u and v in an oriented graph D, a u-v geodesic is a directed path of minimum length from u to v. Let I(u,v) denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. If A is a subset of V(D), then I(A) is the union of all I(u,v) for u,v \in A. The geodetic number g(D) is the minimum cardinality of the subset A of V(D) with I(A)=V(D). For a nontrivial connected graph G, the geodetic spectrum of G is the set of geodetic numbers among the all orientations of G and the strong geodetic spectrum of G is the set of geodetic numbers among the all strongly connected orientations of G. In this paper, we investigate geodetic spectra and strong geodetic spectra of graphs. For the geodetic spectra of graphs, we demonstrate that for every two integers n and m with $1\leq n-1\leq m\leq (_2^n)$, there exists a connected graph G of order n and size m such that $S(G)=\{2,3,\ldots,n\}$. We also determine the geodetic spectra of complete r-partite graphs, cycles and trees. These results provide answers to a conjecture and two problems given by Chartrand and Zhang [9]. For the strong geodetic spectra of graphs, we show that the strong geodetic spectrum of each graph is the subset of $\{2, 3, \cdots , n-2\}$ and for every positive integers n, m, k with $2 \le k \le n-3$ and $n+k \le m\le {n \choose 2}-k$, we can construct a strongly connected oriented graph $D$ of order n and size m such that g(D)=k.

博士<br>國立中央大學<br>資訊工程研究所<br>89<br>In this dissertation, several geodetic problems in graphs are considered. The motivation of studying geodetic connectivity and hinge vertices in a graph arises naturally from network design and analysis. We first look at the algorithmic complexities of computing geodetic connectivity and finding all hinge vertices in a graph. We present an O(nm) time algorithm for solving this problem in an arbitrary graph. In particular, we are interested to know if there exist special classes of graphs with special properties such that the time complexity of determining whether a graph has geodetic connectivity k can be reduced. We investigate this topic on some special classes of chordal graphs. Linear time algorithms are developed for strongly chordal graphs, ptolemaic graphs, and interval graphs, and an O(n^2) time algorithm is proposed for undirected path graphs. Because many interconnection networks can be constructed using line graph iterations, we also study how to recognize line graphs without hinge vertices. Moreover, we provide several operations of graphs that allow a graph to expand in scale without destroying geodetically connectivity. Next, we deal with the topic on constructing a specific vertex ordering of an AT-free graph. We show that every connected AT-free graph admits a vertex ordering that we call a 2-cocomparability ordering. The ordering presented here can be defined by using the term of distance metric, and can be exploited for algorithmic purposes. Two techniques called involutive sequence and 2-sweep LexBFS are introduced for constructing such an ordering for AT-free graphs. This ordering generalizes the cocomparability ordering achievable for cocomparability graphs. According to this ordering, we show that every power of an AT-free graph is indeed a cocomparability graph. Also, it leads to that the distance k-domination, k-stability, and the graph k-clustering problems for k>=2 on AT-free graphs can be solved in a more efficient way. In particular, the vertex ordering produced from the 2-sweep LexBFS can be used for constructing a tree 4-spanner of an AT-free graph and for recognizing a class of special AT-free graphs called bipartite permutation graphs in linear time. Besides, we study the characterization of chordal bipartite graphs and show that the all-pairs-shortest-length problem on chordal bipartite graphs can be solved in O(n^2) optimal time. We further investigate the algorithmic complexity of a graph clustering problem that determine whether there is a partition of a graph into certain number clusters of vertices such that the diameter of subgraph induced by each cluster does not exceed a prespecified bound. Some NP-complete and polynomial results are derived for several classes of special graphs.

碩士<br>國立中山大學<br>應用數學系研究所<br>104<br>A u − v geodesic in G is a shortest path between u and v in G. The geodetic interval I_G[u,v] is the set of all vertices which are lying on some u − v geodesic. A geodetic set S of G is a subset of vertices in G such that ∪_ u,v∈S I_G[u,v] = V (G). The geodetic number is the minimum cardinality of a geodetic set in G, denoted by g(G). Let F be a subset of the vertex set of G. A Steiner tree of F in G is a minimum acyclic connected subgraph of G containing F. The Steiner interval of F in G is the collection of vertices lying on some Steiner trees of F in G, denoted by S_G[F]. A Steiner set is the subset F of vertices in G which satisfies S_G[F] = V (G). We call that F is a Steiner set of G. The Steiner number s(G) of G is the minimum cardinality of a Steiner set of G. In [9], there is a conjecture: For integers r ≥ 3 and a ≥ b ≥ 3, there exists a connected graph G with rad(G) = diam(G) = r, s(G) = b, and g(G) = a. We study the conjecture and consider the constraint diam(G) = rad(G)+1. In this thesis, we prove the following results: (1) There exists a graph G of order 4k + 9 with k ≥ 2, diam(G) = rad(G) = 4, g(G) = 3 + k, and s(G) = 3. (2) There exists a graph G of order 4k + 25 with k ≥ 1, diam(G) = rad(G) = 5, g(G) = 4 + k, and s(G) = 3. (3) There exists a graph G of order 6k + 12 with k ≥ 1, diam(G) = rad(G) + 1 = 6, g(G) = 2 + k, and s(G) = 3. (4) There exists a graph G of order 9k + 15 with k ≥ 1, diam(G) = rad(G) + 1 = 7, g(G) = 3 + k, and s(G) = 3. (5) There exists a graph G of order 9k + 12 with k ≥ 1, diam(G) = rad(G) + 1 = 6, g(G) = 2 + 2k, and s(G) =3. Keywords: geodetic number; Steiner number; diameter; radius

博士<br>國立臺灣科技大學<br>資訊工程系<br>95<br>A graph G is a finite nonempty vertex set V(G), together with an (possible empty) edge set E(G) of 2-element subset of V (G). A shortest path connecting two vertices u and v is called a u-v geodesic. The distance between u and v in a graph G, denoted by dG(u,v), is the number of edges in a u-v geodesic. A graph G with n vertices is edge-pancyclic if every edge of G belongs to an l-cycle for every 3<=l<=n. G is called panconnected if, for each pair of vertices u,v in V(G) and for each integer l with dG(u,v)<=l<=n−1, there is a path of length l in G that connects u and v. Clearly, all panconnected graphs are indeed edge-pancyclic. We introduce geodesic-pancyclicity inspired with the property of edge-pancyclicity in graphs. A graph G is geodesic-pancyclic if, for each pair of vertices u,v in V(G), every u-v geodesic lies on every cycle of length l satisfying max{2dG(u,v),3}<=l<=n. Since there is no cycle with odd length in bipartite graphs, we discuss the geodesic-bipancyclicity of bipartite graphs. A bipartite graph G with n vertices is geodesic-bipancyclic if, for each pair of vertices u,v in V(G), every u-v geodesic lies on every even cycle of length l satisfying max{2dG(u,v),4}<=l<=n. In this dissertation, we first analyze the relationship between these Hamiltonianlike properties, especially for panconnectivity and geodesic-pancyclicity. Then, we discuss geodesic-pancyclicity on two cube-like graphs. We prove that hypercube Qk is geodesic-bipancyclic with dimension k<=2, and augmented cube AQk is geodesic-pancyclic with dimension k<=2. We also discuss fault-tolerant panconnectivity of AQk. We show that AQk−f is panconnected if f is a vertex or an edge of AQk with dimension k>=3. Furthermore, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs also hold true on geodesic-pancyclic graphs.

Given a hyperbolic surface, the set of all closed geodesics whose length is minimal form a graph on the surface, in fact a so called fat graph, which we call the systolic graph. The central question that we study in this thesis is: which fat graphs are systolic graphs for some surface -we call such graphs admissible. This is motivated in part by the observation that we can naturally decompose the moduli space of hyperbolic surfaces based on the associated systolic graphs. A systolic graph has a metric on it, so that all cycles on the graph that correspond to geodesics are of the same length and all other cycles have length greater than these. This can be formulated as a simple condition in terms of equations and inequations for sums of lengths of edges. We call this combinatorial admissibility. Our first main result is that admissibility is equivalent to combinatorial admissibility. This is proved using properties of negative curvature, specifically that polygonal curves with long enough sides, in terms of a lower bound on the angles, are close to geodesics. Using the above result, it is easy to see that a subgraph of an admissible graph is admissible. Hence it suffices to characterize minimal non-admissible fat graphs. Another major result of this thesis is that there are infinitely many minimal non-admissible fat graphs (in contrast, for instance, to the classical result that there are only two minimal non-planar graphs).

Given a hyperbolic surface, the set of all closed geodesics whose length is minimal form a graph on the surface, in fact a so called fat graph, which we call the systolic graph. The central question that we study in this thesis is: which fat graphs are systolic graphs for some surface -we call such graphs admissible. This is motivated in part by the observation that we can naturally decompose the moduli space of hyperbolic surfaces based on the associated systolic graphs. A systolic graph has a metric on it, so that all cycles on the graph that correspond to geodesics are of the same length and all other cycles have length greater than these. This can be formulated as a simple condition in terms of equations and inequations for sums of lengths of edges. We call this combinatorial admissibility. Our first main result is that admissibility is equivalent to combinatorial admissibility. This is proved using properties of negative curvature, specifically that polygonal curves with long enough sides, in terms of a lower bound on the angles, are close to geodesics. Using the above result, it is easy to see that a subgraph of an admissible graph is admissible. Hence it suffices to characterize minimal non-admissible fat graphs. Another major result of this thesis is that there are infinitely many minimal non-admissible fat graphs (in contrast, for instance, to the classical result that there are only two minimal non-planar graphs).

No<br>Both prominent feature points and geodesic distance are key factors for mesh segmentation. With these two factors, this paper proposes a graph cut based mesh segmentation method. The mesh is first preprocessed by Laplacian smoothing. According to the Gaussian curvature, candidate feature points are then selected by a predefined threshold. With DBSCAN (Density-Based Spatial Clustering of Application with Noise), the selected candidate points are separated into some clusters, and the points with the maximum curvature in every cluster are regarded as the final feature points. We label these feature points, and regard the faces in the mesh as nodes for graph cut. Our energy function is constructed by utilizing the ratio between the geodesic distance and the Euclidean distance of vertex pairs of the mesh. The final segmentation result is obtained by minimizing the energy function using graph cut. The proposed algorithm is pose-invariant and can robustly segment the mesh into different parts in line with the selected feature points.