Υλοποίηση αλγορίθμων ελέγχου ισοζύγισης προσημασμένων γραφών.

Abstract

Στην πτυχιακή αυτή θα υλοποιηθούν τυχαίοι προσημασμένοι γράφοι και θα ελεγχθούν ως προς την ισοζύγιση με τη χρήση ήδη ανεπτυγμένων αλγορίθμων από τη βιβλιογραφία. Ένας τέτοιος αλγόριθμος έχει δημοσιευθεί στο περιοδικό International Journal of Computer Mathematics, με τίτλο "A dynamic programming algorithm to test a signed graph for balance." Στον αλγόριθμο αυτόν γίνεται διάσχιση του γράφου χρησιμοποιώντας τεχνική BFS. Θα αναπτυχθεί αντίστοιχος αλγόριθμος για έλεγχο ισοζύγισης του γράφου χρησιμοποιώντας μία τεχνική μορφής DFS.

In this thesis random signed graphs will be generated and balance checked with the use of already developed algorithms from the bibliography. Such an algorithm has been published on International Journal of Computer Mathematics, named “A Dynamic Programming Algorithm To Test a Signed Graph for Balance”. This algorithm uses a BFS technique to traverse the graph. Respectively, another algorithm using a DFS technique will be implemented.