Back to search

Institutional Repository of Vilnius University

Penkių kintamųjų Būlio funkcijų grafų invariantų analizė /

Abstract

dc:description

The 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.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Viskontas, Ernestas,. Penkių kintamųjų Būlio funkcijų grafų invariantų analizė /. Institutional Repository of Vilnius University, 2024. https://repository.vu.lt/VU:ELABAETD210647031&prefLang=en_US