We study non-oriented simple graphs. We call a graph symmetric, if there exists a non-identical
permutation of its vertices, which leaves the graph invariant, i.e. a graph is called symmetric if the group of its
automorphisms is not trivial. A graph which is not symmetric will be called asymmetric. The degree of symmetry
of a symmetric graph is measured by the size of its group of automorphisms. We will measure the degree of asymmetry
of an asymmetric graph by the number of vertices which we have to delete to obtain a symmetric graph.
Goal
We will measure the degree of asymmetry of an asymmetric graph by the number of vertices
which we have to delete to obtain a symmetric graph.
Proposal of the structure of the thesis
Introduction
Preliminaries (e.g. including concepts from Graph Theory and Theory of symmetries (automorphism groups))
Existing softwares/libraries (e.g. more detailed studying GAP, Naughty and Grape systems)
Implementation
Results
Summary
Future work
Timeline
Oct./Nov. 2021 Studying literature from student's books
1.11.2021 Bachelor thesis website
9.11.2021 Bachelor thesis timeline
Nov. 2021 Revision concepts and terms
Nov. 2021 More detailed studying of graph isomorphism
30.11.2021 Collecting resources and presenting them
Dec. 2021 Testing ideas and concepts with small examples
Jan. 2022 Studying professional articles
Jan./Mar. 2022 Design algorithms and programs
Apr./May 2022 Finishing writing a bachelor thesis, proofreading
20.5.2022 Submission of the bachelor thesis
Diary
Week14.2.2022 - 20.2.2022
Supplement to the chapter Preliminaries by Prim's and Kruskal's Algorithm.
Programming class Bipartite whose function isBipartite can determine if a given graph is bipartite and testing this function on minimal asymmetric graphs.
Week21.2.2022 - 27.2.2022
Modification of the chapter Preliminaries and addition of the Induced Subgraph to this section.
Use of Kruskal's algorithm in finding minimal asymmetric graphs.
Week28.2.2022 - 6.3.2022
Supplement to the chapter Implementation by unsuccessful code and finding its solution.
Print graphs to a text file in a format used by GAP.
Week7.3.2022 - 13.3.2022
Programming of minimal asymmetric graphs and graphs with one less edge/vertex.
Programming the user interface to the console.
Week14.3.2022 - 20.3.2022
Drawing minimal asymmetric graphs and graphs with fewer edges/vertices using GAP.
Programming of minimal asymmetric graphs and graphs with any less edges/vertices.
Week21.3.2022 - 27.3.2022
Writing a chapter Introduction.
Programming of minimal asymmetric graphs with one more edge.
Week28.3.2022 - 3.4.2022
Testing and debugging the program, later fixing small errors.
Adding the work progress to the chapter Implementation.
Week4.4.2022 - 10.4.2022
Creation of the Catalogue of minimal asymmetric graphs with iterativly removed vertices.
Abstract writing for the thesis.
Week11.4.2022 - 17.4.2022
Filtering isomorphic graphs using GAP.
Description of all program functions in the Implementation chapter.
Week18.4.2022 - 24.4.2022
Downloading data from the program to analyze the results of work.
Describing the results of the work in the chapter Results.
Week25.4.2022 - 1.5.2022
Summary of work results in the chapter Summary.
Editing all the text of the bachelor thesis including Catalogue.
Week2.5.2022 - 8.5.2022
Writing README, instructions for using the program.
Writing and drawing a class diagram for the program.
Week9.5.2022 - 15.5.2022
Editing and correcting the text, including editing the chapters Preliminaries, Implementation and Results.
Refactoring and code testing for bachelor thesis.
Week16.5.2022 - 22.5.2022
Editing and correcting the text, including editing the chapters Introduction, Summary and Abstract.