Το πρόβλημα ισομορφισμού των γράφων θέτει το ερώτημα αν ΔΥΟ γράφοι είναι ουσιαστικά ΕΝΑΣ, με την προϋπόθεση ότι υπάρχει αντιστοιχία "1-1" στους κόμβους τους, η οποία διατηρεί τους τρόπους που συνδέονται.
Με απλά λόγια, το πρόβλημα διερευνά αν δύο δίκτυα, που φαίνονται διαφορετικά, είναι ίδια, δηλαδή ισόμορφα!
Ο László Babai, ανακοίνωσε πρόσφατα ότι επινόησε έναν νέο αλγόριθμο, για το εν λόγω βασανιστικό πρόβλημα που ταλάνιζε την Επιστήμη των Υπολογιστών. Ο προτεινόμενος αλγόριθμος βρίσκει τη λύση σε ρεαλιστικό, σχεδόν-πολυωνυμικό χρόνο, ακόμα και για εξαιρετικά περίπλοκα δίκτυα, αφού φαίνεται να είναι συντριπτικά πιό αποδοτικός από τον προηγούμενο καλύτερο αλγόριθμο, ο οποίος αν και είχε το ρεκόρ τα τελευταία 30 χρόνια, τερμάτιζε σε εκθετικό χρόνο!
Διαφορετικά σχήματα, αλλά ισόμορφοι γράφοι !
ΥΓ. Προτείνω αδίστακτο κλικάρισμα στα 4 link και στις 2 εικόνες
☮
ΥΓ. Προτείνω αδίστακτο κλικάρισμα στα 4 link και στις 2 εικόνες
☮
No comments:
Post a Comment