Institutional Repository of Vilnius University
Penkių kintamųjų Būlio funkcijų grafų invariantų analizė /
Abstract
dc:descriptionThe analysis of the effectiveness of graph invariants when applied to graphs constructed from boolean functions. A graph invariant is some information (which could be a single number or a complicated structure) that doesn't change with respect to different isomorphic graphs of the same graph. The graph's vertices are the set of variable vectors with which the function value equates to one, and the graph has edges between two vertices if the Hamming distance between them is one (however, graphs with other Hamming distances were also somewhat considered). Then the following invariants were tested: * Graph diameter * Graph radius * Degree list * Edge count * Wiener index * Vertex count * Path length list * Proximity layers * Component count * Eccentricity list * Neighborhood degree list And a final invariant was introduced, which is the proximity layers invariant, with the vertices being represented as the set of distances to all other vertices. The final invariant performed the best according to the collision count metric (having just 6 collisions out of 753,617) when it came to testing whether or not the graphs derived from Boolean functions can be separated into their own isomorphism groups. Also, some ideas for Boolean function invariants were presented.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Viskontas, Ernestas,
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD210647031&prefLang=en_US