Κωδικοποίηση γράφων στην Γλώσσα της Πληροφορικής των Πανελλαδικών

Η Γλώσσα της Πληροφορικής των Πανελλαδικών δεν περιλαμβάνει μια ειδική δομή δεδομένων για τους γράφους. Ωστόσο, ένας γράφος μπορεί να κωδικοποιηθεί με χρήση ενός δισδιάστατου τετραγωνικού πίνακα – γνωστού και ως πίνακα γειτνίασης. Αυτός είναι ένας συνήθης τρόπος κωδικοποίησης, γενικότερα, σε οποιαδήποτε γλώσσα προγραμματισμού. Αξίζει να σημειωθεί ότι έχει υπάρξει θέμα πανελλαδικών εξετάσεων (βλ. παρακάτω) που χρησιμοποιεί την κωδικοποίηση ενός γράφου, όταν ακόμα δεν υπήρχε εκτενές ειδικό κεφάλαιο σχετικά με αυτήν την δομή δεδομένων στην ύλη της πληροφορικής.

Ας δούμε ένα παράδειγμα μη-κατευθυνόμενου γράφου, αρχικά. Η φιλία στο μέσο κοινωνικής δικτύωσης facebook μπορεί να αναπαρασταθεί με έναν μη-κατευθυνόμενο γράφο – αφού η φιλία στο fb είναι αμφίδρομη. Ας θωρήσουμε πέντε χρήστες του fb, την Μαρία, τον Θανάση, την Σοφία, την Τζένη και τον Αποστόλη. Οι χρήστες αυτοί θα είναι οι κορυφές του γράφου. Η ύπαρξη ακμής μεταξύ δύο κορυφών σηματοδοτεί την ύπαρξη φιλίας μεταξύ των αντίστοιχων χρηστών. Ο γράφος μας έχει την μορφή:

Προκειμένου να κωδικοποιήσουμε τον παραπάνω γράφο στην Γλώσσα με πίνακα γειτνίασης χρειαζόμαστε έναν δισδιάστατο τετραγωνικό πίνακα 5x5 ακέραιου τύπου. Οι διαστάσεις του πίνακα είναι και οι δύο ίσες με 5, όσο και το πλήθος των κορυφών του γράφου. Μετά κάνουμε μια αντιστοιχία ονομάτων και αριθμών από το 1 ως το 5, για παράδειγμα, Μαρία (1), Σοφία (2), Θανάσης (3), Αποστόλης (4), Τζένη (5).

Όπως, ίσως, ήδη παρατηρήσατε, μια τιμή 1 σε κάποια θέση του πίνακα σημαίνει ότι τα ονόματα που αντιστοιχούν στην αντίστοιχη γραμμή και στήλη του πίνακα είναι φίλοι, ενώ μια τιμή 0 σημαίνει ότι δεν είναι φίλοι. Αυτός είναι ένας συνήθης τρόπος κωδικοποίησης, χωρίς όμως να αποκλείεται οποιοσδήποτε άλλος συμβολισμός. Για παράδειγμα, η ύπαρξη φιλίας θα μπορούσε να συμβολιστεί με το 15 και η μη-ύπαρξη φιλίας με το 25 (ok, αυτό δεν συνηθίζεται!). Ή ακόμα, ο τύπος του πίνακα θα μπορούσε να ήταν λογικός με την τιμή Αληθής να σηματοδοτεί την ύπαρξη φιλίας και την τιμή Ψευδής την μη-ύπαρξη. Ή ο τύπος του πίνακα θα μπορούσε να ήταν και χαρακτήρας, π.χ. με την τιμή ‘φίλοι’ να σηματοδοτείται η φιλία και με την τιμή ‘όχι φίλοι’ η μη-ύπαρξη φιλίας. Θα μπορούσε, ακόμα, να χρησιμοποιηθεί ο “μισός” πίνακας, είτε από την κύρια διαγώνιο και πάνω, είτε από την κύρια διαγώνιο και κάτω, μιας και όταν ο γράφος είναι μη-κατευθυνόμενος οι τιμές στις θέσεις [ι, κ] και [κ,ι] είναι ίσες (για κάθε ι, για κάθε κ). Ένας τέτοιος πίνακας, μάλιστα, λέγεται συμμετρικός.

Ας δούμε τώρα την κωδικοποίηση ενός κατευθυνόμενου γράφου. Εδώ, αυτό που αλλάζει είναι ότι οι τιμές στις θέσεις [ι,κ] και [κ,ι] μπορεί να διαφέρουν και εκφράζουν συνήθως η μεν πρώτη κατεύθυνση από το όνομα που αντιστοιχεί στον αριθμό ι προς το όνομα που αντιστοιχεί στον αριθμό κ, η δε δεύτερη το αντίστροφο.

Θα εξετάσουμε το παράδειγμα του κεντρικού δόγματος της μοριακής βιολογίας. Πρόκειται για το θεμελιώδες μοντέλο της λειτουργίας του κυττάρου στην σύγχρονη βιολογία, το οποίο αναπαριστά την ροή της πληροφορίας μέσα στο κύτταρο. Το σύνηθες μονοπάτι του μοντέλου, το οποίο είναι και το πιο γνωστό, περιλαμβάνει την «μεταγραφή» του DNA σε (m)RNA, το οποίο τελικά αποτελεί το «πρόγραμμα» (αν θέλετε βγάλτε τα εισαγωγικά) με βάση το οποίο λαμβάνει χώρα η παραγωγή πρωτεϊνών μέσα στο κύτταρο! Αξίζει να σημειωθεί ότι το βασικό μοντέλο του DNA (primary structure) είναι ένα δεδομένο τύπου χαρακτήρων συμβολοσειρά (string) όπως είναι ευρύτερα γνωστός αυτός ο τύπος στην επιστήμη της πληροφορικής), το οποίο κτίζεται με ένα αλφάβητο από τέσσερα σύμβολα, A (για την νουκλεοβάση Adenine), G (για την νουκλεοβάση Guanine), C (για την νουκλεοβάση Cytosine) και T (για την νουκλεοβάση Thymine). Όχι τυχαία, η σύζευξη των επιστημών της βιολογίας και της πληροφορικής έχει δώσει ώθηση στην ανάπτυξη του κλάδου της βιοπληροφορικής!

Θεωρούμε την αντιστοιχία DNA (1), RNA (2) και ΠΡΩΤΕΪΝΗ (3) και έναν πίνακα 3×3:

Κάποιες παρατηρήσεις:

Ο κόμβος ΠΡΩΤΕΪΝΗ δεν αποτελεί αφετηρία για καμία ακμή, γεγονός που σηματοδοτείται από την ύπαρξη μόνο της τιμής 0 στην αντίστοιχη γραμμή.

Στον κόμβο DNA καταλήγουν 2 ακμές, γεγονός που σηματοδοτείται από την ύπαρξη δύο τιμών ίσων με 1 στην αντίστοιχη στήλη.

Υπάρχουν τιμές ίσες με 1 στην κύρια διαγώνιο, γεγονός που σηματοδοτεί ότι κάποιοι κόμβοι συνδέονται με τον εαυτό τους.

Ας δούμε και μια περίπτωση γράφου με “βάρηστις ακμές. Πολλές φορές οι ακμές ενός γράφου συσχετίζονται με κάποιες τιμές δεδομένων. Για παράδειγμα, στις επαναληπτικές πανελλαδικές εξετάσεις του 2018, στο θέμα Δ, ο πίνακας ΑΠ[15,15] κωδικοποιεί έναν γράφο με κορυφές 15 νησιά και βάρη τις αποστάσεις μεταξύ τους. Για χάρη απλοποίησης, στο παρακάτω σχήμα απεικονίζεται ένας γράφος με 5 νησιά (Ν1, Ν2, Ν3, Ν4, Ν5). Παρατηρείστε τις τιμές (βάρη) στις ακμές (με κόκκινο χρώμα), οι οποίες στην δεδομένη περίπτωση είναι οι αποστάσεις μεταξύ δύο νησιών.

Σ’ αυτήν την περίπτωση στον τετραγωνικό πίνακα ΑΠ[15,15] οι τιμές εκφράζουν τα βάρη. Για το συγκεκριμένο θέμα των Πανελλαδικών δεν υπήρχαν δύο νησιά που δεν σχετίζονταν με ακμή. Αν υπήρχαν, θα μπορούσε να καταχωρηθεί μια αρνητική τιμή (π.χ. -1) για αυτές τις περιπτώσεις στο πίνακα. Αξίζει να σημειωθεί, ακόμη, ότι στο συγκεκριμένο θέμα ζητήθηκε να χρησιμοποιηθεί το τμήμα του πίνακα πάνω από την κύρια διαγώνιο (αφού ο γράφος που κωδικοποιείται στην ουσία είναι μη-κατευθυνόμενος). Ο πίνακας γειτνίασης για το  παραπάνω παράδειγμα με τα 5 νησιά, με βάση την κωδικοποίηση του θέματος των επαναληπτικών Πανελλαδικών του 2018 (με χρήση μόνο των στοιχείων του πίνακα που βρίσκονται πάνω από την κύρια διαγώνιο) είναι:

*Η οπτική απεικόνιση των γράφων έγινε με την βοήθεια του πακέτου Graphviz και της Python.

Γιώργος Μπουγιούκας

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Google

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση /  Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση /  Αλλαγή )

Σύνδεση με %s

Ο ιστότοπος χρησιμοποιεί το Akismet για την εξάλειψη των ανεπιθύμητων σχολίων. Μάθετε πως επεξεργάζονται τα δεδομένα των σχολίων σας.