Graphs: Isomorphism, Cycles, Reconstruction and Randomness

DSpace Repository

Show simple item record

dc.contributor.advisor Storer, James A.
dc.contributor.author Ward, Grady
dc.date.accessioned 2016-05-17T17:12:30Z
dc.date.available 2016-05-17T17:12:30Z
dc.date.issued 2016
dc.identifier.uri http://hdl.handle.net/10192/32390
dc.description.abstract Given a graph, count the number of closed walks (called cycles) of every length that pass through each vertex in the graph. Counting the number of cycles gives us a vector which describes a kind of local resonance, a description of the localized area around each vertex within the graph. This idea is a numerical property, called an invariant, which is highly information dense–able to detect differences between graphs (or vertices) with high probability, but not sufficient to verify that two graphs (or vertices in a single graph) are the same. It turns out that we can calculate the number of Cycles very quickly, relative to how much information it gives us. The number of graphs you can create, even over a small number of vertices, is very large. However, the number is much larger if you consider different labelings of the same graph to be distinct. This difference matters in many contexts, but is made clear through examining standard random graph generators, which treat different labelings of the same graph as if they are different graphs. This is not a problem in and of itself (it makes sense in many practical contexts), but it warps theoretic arguments about the runtime of algorithms over ‘random’ graphs, in ways that we can describe through probability, algebraic proof and experimental results. It turns out that making up our own random graph generators can actually improve upon this state of affairs in a quantifiable way.
dc.format.mimetype application/pdf
dc.language English
dc.language.iso eng
dc.publisher Brandeis University
dc.relation.ispartofseries Brandeis University Theses and Dissertations
dc.rights Copyright by Grady Ward 2016
dc.title Graphs: Isomorphism, Cycles, Reconstruction and Randomness
dc.type Thesis
dc.contributor.department Department of Computer Science
dc.degree.name BS
dc.degree.level Bachelors
dc.degree.discipline Computer Science
dc.degree.grantor Brandeis University, College of Arts and Sciences


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search BIR


Browse

My Account