Spelling suggestions: "subject:"adjacency"" "subject:"adjacencys""
1 |
Graphs with prescribed adjacency propertiesAnanchuen, Watcharaphong January 1993 (has links)
A graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices there are at least k other vertices, each of which is adjacent to the first m vertices but not adjacent to any of the latter n vertices. The class of graphs having property P(m.n,k) is denoted by ζ(m,n,k). The problem that arises is that of characterizing the class ζ(m,n,k). One particularly interesting problem that arises concerns the functionP(m,n,k) = min{υ(G) : G є ζ(m,n,k) }.In Chapter 2, we establish some important properties of graphs in the class ζ(m,n,k) and a lower bound on p(m,n,k). In particular, we prove thatp(n,n,k) ≥ 4n-1 (2(n+k) + ½ (3 = (-1)n+k+1} + 1/3 l 1/3One of the results in Chapter 2 is that almost all graphs have property P(m,n,k). However, few members of ζ(m,n,k) have been exhibited. In Chapter 3. we construct classes of graphs having property P(l,n,k) . These classes include the cubes, "generalized" Petersen graphs and "generalized" Hoffman-Singleton graphs.An important graph in the study of the class ζ(m,n,k) is the Paley graph Gq defined as follows. Let q = l(mod 4) be a prime power. The vertices of Gq are the elements of the finite field IFq. Two vertices a and b are joined by an edge if and only if their difference is a quadratic residue, that is a - b = y2 for some y є IFq. In chapter 4, we prove that for a prime p = l(mod 4), all sufficiently large Paley graphs GP satisfy property P(m.n,k). This is established by making use of results from prime number theory.In Chapter 5 , we establish, by making use of results from finite fields, the adjacency properties of Paley graphs of order q = pd , with p a prime.For directed graphs, there is an analogue of the above adjacency property concerning tournaments. A tournament Tq of order q is said to have property Q(n,k) if every subset of n vertices of Tq is dominated (if there is an arc directed from ++ / a vertex u to a vertex v, we say that u dominates v and that v is dominated by u) by at least k other vertices.Let q = 3(mod 4) is a prime power. The Paley tournament Dq is defined as follows. The vertices of Dq are the elements of the finite field IFq. Vertex a is ioined to vertex b by an arc if and only if a - b is a quadratic residue in Fq. In Chapter 6, we prove that the Paley tournament Dq has property Q(n,k) wheneverq > {(n - 3)2n-1 + Z}G + kZn - 1. A graph G is said to have property P*(rn,n,k) if for any set of rn + n distinct vertices of G there are exactly k other vertices, each of which is adjacent to the first m vertices of the set but not adjacent to any of the latter n vertices. The class of graphs having property P*(m.n,k) is denoted by S*(m,n.k). The class S*(m,n,k) has been studied when one of m or n is zero. In Chapter 7, we show that, for m = n = 1, graphs with this property (k + t)' + 1, are the strongly regular graphs with parameters ( k + t,t - 1,t) for some positive integer t. For rn 2 1, n 2 1, and m + n 2 3, we show that, there is no graph having property P*(m.n,k), for any positive integer k. The first Chapter of this thesis provides the motivation, terminology. general concepts and the problems concerning the adjacency properties of graphs. In Chapter 8 . we present some open problems.
|
2 |
Colour-based object recognitionMatas, J. January 1995 (has links)
This thesis studies the use of colour information for object recognition. A new representation for objects with multiple colours - the colour adjacency graph (CAG) - is proposed. Each node of the CAG represents a single chromatic component of the image defined as a set of pixels forming a unimodal cluster in the chromatic scattergram. Edges encode information about adjacency of colour components and their reflectance ratio. The CAG is related to both the histogram and region adjacency graph representations. It is shown to be preserving and combining the best features of these two approaches while avoiding their drawbacks. The proposed approach is tested on a range of difficult object recognition and localisation problems involving complex imagery of non rigid 3D objects under varied viewing conditions with excellent results.
|
3 |
The Singular Values of the Exponientiated Adjacency Matrixes of Broom-Tree GraphsPowell, Tracy 01 May 2006 (has links)
In this paper, we explore the singular values of adjacency matrices {An} for a particular family {Gn} of graphs, known as broom trees. The singular values of a matrix M are defined to be the square roots of the eigenvalues of the symmetrized matrix MTM. The matrices we are interested in are the symmetrized adjacency matrices AnTAn and the symmetrized exponentiated adjacency matrices BnTBn = (eAn − I)T(eAn − I) of the graphs Gn. The application of these matrices in the HITS algorithm for Internet searches suggests that we study whether the largest two eigenvalues of AnTAn (or those of BnTBn) can become close or in fact coincide. We have shown that for one family of broom-trees, the ratio of the two largest eigenvalues of BnTBn as the number n of nodes (more specifically, the length l of the graph) goes to infinity is bounded below one. This bound shows that for these graphs, the second largest eigenvalue remains bounded away from the largest eigenvalue. For a second family of broom trees it is not known whether the same is true. However, we have shown that for that family a certain later eigenvalue remains bounded away from the largest eigenvalue. Our last result is a generalization of this latter result.
|
4 |
Ontology Slice Generation and Alignment for Enhanced Life Science Literature SearchBergman Laurila, Jonas January 2009 (has links)
<p>Query composition is an often complicated and cumbersome task for persons performing a literature search. This thesis is part of a project which aims to present possible queries to the user in form of natural language expressions. The thesis presents methods of ontology slice generation. Slices are parts of ontologies connecting two concepts along all possible paths between them. Those slices hence represent all relevant queries connecting the concepts and the paths can in a later step be translated into natural language expressions. Methods of slice alignment, connecting slices that originate from different ontologies, are also presented. The thesis concludes with some example scenarios and comparisons to related work.</p>
|
5 |
Ontology Slice Generation and Alignment for Enhanced Life Science Literature SearchBergman Laurila, Jonas January 2009 (has links)
Query composition is an often complicated and cumbersome task for persons performing a literature search. This thesis is part of a project which aims to present possible queries to the user in form of natural language expressions. The thesis presents methods of ontology slice generation. Slices are parts of ontologies connecting two concepts along all possible paths between them. Those slices hence represent all relevant queries connecting the concepts and the paths can in a later step be translated into natural language expressions. Methods of slice alignment, connecting slices that originate from different ontologies, are also presented. The thesis concludes with some example scenarios and comparisons to related work.
|
6 |
Do-it-yourself networks: a novel method of generating weighted networksShanafelt, D. W., Salau, K. R., Baggio, J. A. 22 November 2017 (has links)
Network theory is finding applications in the life and social sciences for ecology, epidemiology, finance and social-ecological systems. While there are methods to generate specific types of networks, the broad literature is focused on generating unweighted networks. In this paper, we present a framework for generating weighted networks that satisfy user- defined criteria. Each criterion hierarchically defines a feature of the network and, in doing so, complements existing algorithms in the literature. We use a general example of ecological species dispersal to illustrate the method and provide open- source code for academic purposes.
|
7 |
CloneCompass: visualizations for code clone analysisWang, Ying 05 May 2020 (has links)
Code clones are identical or similar code fragments in a single software system or across multiple systems. Frequent copy-paste-modify activities and reuse of existing systems result in maintenance difficulties and security issues. Addressing these problems requires analysts to undertake code clone analysis, which is an intensive process to discover problematic clones in existing software. To improve the efficiency of this process, tools for code clone detection and analysis, such as Kam1n0 and CCFinder, were created.
Kam1n0 is an efficient code clone search engine that facilitates assembly code analysis. However, Kam1n0 search results can contain millions of function-clone pairs, and efficiently exploring and comprehensively understanding the resulting data can be challenging. This thesis presents a design study whereby we collaborated with analyst stakeholders to identify requirements for a tool that visualizes and scales to millions of function-clone pairs. These requirements led to the design of an interactive visual tool, CloneCompass, consisting of novel TreeMap Matrix and Adjacency Matrix visualizations to aid in the exploration of assembly code clones extracted from Kam1n0.
We conducted a preliminary evaluation with the analyst stakeholders, and we show how CloneCompass enables these users to visually and interactively explore assembly code clones detected by Kam1n0 with suspected vulnerabilities. To further validate our tool and extend its usability to source code clones, we carried out a Linux case study, where we explored the clones in the Linux kernel detected by CCFinder and gained a number of insights about the cloning activities that may have occurred in the development of the Linux kernel. / Graduate
|
8 |
LayeringAnderson, Kenneth John 18 August 2009 (has links)
The understanding of a space is a diverse and limitless endeavor. My investigations leading up to this design proposal addressed three(3), admittedly broad, notions of spatial adjacency and relation:path, threshold, and layering. / Master of Architecture
|
9 |
Cospectral graphs : What properties are determined by the spectrum of a graph?Sundström, Erik January 2023 (has links)
This paper was written as a bachelor thesis in mathematics. We study adjacency matrices and their eigenvalues to investigate what properties of the corresponding graphs can be determined by those eigenvalues, the spectrum of the graph. The question of which graphs are uniquely determined by their spectra is also covered. Later on we study some methods of finding examples of graphs with shared spectra, also referred to as cospectral graphs.
|
10 |
Designing the debate turns: microanalysis of the 2008 U.S. presidential debatesHan, Ji Won, 1978- 24 August 2010 (has links)
This thesis examines interactional dimensions of the 2008 U.S. presidential debates based on the conversation analytic concepts of sequence organization and turn management. Drawing on the video recordings of the three 2008 presidential debates, I investigate features of turn design and interactional strategies that candidates employ during the debates and compare stylistic differences between John McCain and Barack Obama. I first examine how candidates design their first-turn responses to the moderator’s question in terms of placement of two different actions, answer and attack. Secondly, I focus on design of the second-turn responses and examine how candidates show responsiveness to both the moderator’s question and the opponent’s prior turn by incorporating multiple actions (e.g., attack, defense, and answer) in their second turns. I also examine direct exchanges between McCain and Obama, particularly concerning their strategic use of the record and their interactional practices in claiming turns and managing overlapping talk in confrontation sequences.
My analysis shows that some stylistic differences exist between McCain’s and Obama’s turns. I provide detailed description of how Obama makes a systematic transition from answer to attack in his first-turn responses, which is distinguished from McCain’s first turns in which attacks are inserted in his answer as relevant topics are brought up. My analysis of the second-turn responses shows that McCain frequently produces an attack at turn beginning or responds to an attack with a reciprocal attack before producing a defense, while Obama tends to produce a defense first and then move to an attack. Lastly, I discuss how both Obama and McCain manage their turns and use turn-taking techniques to avoid direct references to their own record and shift the focus of the talk to the opponent’s stance on a related issue. / text
|
Page generated in 0.0362 seconds