Graph isomorphism detection program
This thesis mainly revolves around the topic of graph isomorphism. A computer program is developed to determine whether the two graphs given by the user are isomorphic or not. If they are determined to be isomorphic, then the corresponding vertex mappings are displayed. If they are not isomorphic...
Saved in:
Main Author: | |
---|---|
Format: | text |
Language: | English |
Published: |
Animo Repository
1993
|
Subjects: | |
Online Access: | https://animorepository.dlsu.edu.ph/etd_bachelors/16101 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | De La Salle University |
Language: | English |
Summary: | This thesis mainly revolves around the topic of graph isomorphism. A computer program is developed to determine whether the two graphs given by the user are isomorphic or not. If they are determined to be isomorphic, then the corresponding vertex mappings are displayed. If they are not isomorphic, then the user is given an option to view a graph isomorphic to either of the two graphs.The algorithm used in determining isomorphism involves the partitioning of the vertices into subsets or classes according to a graph property that is invariant under isomorphism. This method is selected due to the significant decrease in time it would take to compute and conclude if there exists an isomorphism between two graphs. |
---|