University of Twente Student Theses
Experimentally finding graphs that minimize Wiener-entropy
Petrov, A.P. (2023) Experimentally finding graphs that minimize Wiener-entropy.
|
PDF
556kB |
| Abstract: | Graph entropy is a way to measure the complexity of a graph. There are many different graph entropies, but there is little work done on finding their extremal values. It is especially intriguing to find the minimal values because of the lack of analytical methods to tackle this problem. This paper will focus only on the Wiener entropy and aims to find the trees that minimize the entropy, until the possible computation limit. After that, 2 classes of graphs, referred to as "brooms" and G(n,k,j), will be inspected and the goal is to find the optimum structure that minimizes the entropy. There is one existing research paper on minimizing Wiener entropy, and the results from this experiments aim to confirm or deny the predictions made there. The experiments will be performed by brute-forcing the graphs that minimize the entropy in the respective search space. In the end, it appears that the class of brooms minimizes the entropy for trees with number of vertices(n) 16 < n < 32 and is expected to continue to minimize it for bigger trees. Furthermore, the results, for the 2 distinct classes, confirm the conjectures for brooms and discover an error in the predictions for the optimum structure of the G(n,k,j) class. The paper then defines new conjectures based on the results gathered. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics, 54 computer science |
| Programme: | Computer Science BSc (56964) |
| Link to this item: | https://purl.utwente.nl/essays/95929 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page