February 1, 2016

Ισομορφισμός του... γράφοντος



Το πρόβλημα ισομορφισμού των γράφων θέτει το ερώτημα αν ΔΥΟ γράφοι είναι ουσιαστικά ΕΝΑΣ, με την προϋπόθεση ότι υπάρχει αντιστοιχία "1-1" στους κόμβους τους, η οποία διατηρεί τους τρόπους που συνδέονται.

Με απλά λόγια, το πρόβλημα διερευνά αν δύο δίκτυα, που φαίνονται διαφορετικά, είναι ίδια, δηλαδή ισόμορφα!

Ο László Babai, ανακοίνωσε πρόσφατα ότι επινόησε έναν νέο αλγόριθμο, για το εν λόγω βασανιστικό πρόβλημα που ταλάνιζε την Επιστήμη των Υπολογιστών. Ο προτεινόμενος αλγόριθμος βρίσκει τη λύση σε ρεαλιστικό, σχεδόν-πολυωνυμικό χρόνο, ακόμα και για εξαιρετικά περίπλοκα δίκτυα, αφού φαίνεται να είναι συντριπτικά πιό αποδοτικός από τον προηγούμενο καλύτερο αλγόριθμο, ο οποίος αν και είχε το ρεκόρ τα τελευταία 30 χρόνια, τερμάτιζε σε εκθετικό χρόνο!

 Διαφορετικά σχήματα, αλλά ισόμορφοι γράφοι ! 


ΥΓ.  Προτείνω αδίστακτο κλικάρισμα στα 4 link και στις 2 εικόνες