Θεωρία γράφων

Αναπαράσταση γράφου όπου οι κύκλοι είναι οι κόμβοι και τα ευθύγραμμα τμήματα είναι ακμές.

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

Οι γράφοι βρίσκουν αρκετές εφαρμογές στην πληροφορική, στις επιστήμες μηχανικών, στη χημεία, στην κοινωνιολογία κ.α. Για παράδειγμα, στα συστήματα πλοήγησης το οδικό δίκτυο μοντελοποιείται ως γράφος, όπου οι δρόμοι είναι οι ακμές και διασταυρώσεις είναι οι κόμβοι. Σε αυτόν τον γράφο, χρησιμοποιώντας διάφορους αλγορίθμους όπως αυτός του Ντάικστρα, μπορεί να βρει κανείς το συντομότερο μονοπάτι μεταξύ δύο σημείων.

Ένα (ψεύτικο) οδικό δίκτυο.

Οι διασταυρώσεις στο οδικό δίκτυο είναι οι κόμβοι του γράφου

Ο γράφος που αναπαριστά το οδικό δίκτυο.

Το συντομότερο μονοπάτι μεταξύ δύο κορυφών.

Γράφος που αναπαριστά το κοινωνικό δίκτυο μίας παρέας, οι κόμβοι είναι άνθρωποι και οι ακμές υπάρχουν μεταξύ δύο ανθρώπων που είναι φίλοι μεταξύ τους. Εδώ, η Μαρία είναι φίλη με τον Γιώργο και την Δέσποινα, ο Γιώργος με τον Αντώνη, την Μαρία και την Δέσποινα, η Δέσποινα με την Μαρία, τον Γιώργο και την Ελένη, η Ελένη με την Δέσποινα και ο Αντώνης με τον Γιώργο.

Ένα άλλο παράδειγμα είναι οι σχέσεις φιλίας σε ένα κοινωνικό δίκτυο (όπως το Facebook) που μπορούν να αναπαρασταθούν ως ένας (μη κατευθυνόμενος) γράφος, όπου οι κόμβοι είναι οι χρήστες και οι ακμές δηλώνουν αν υπάρχει φιλία μεταξύ τους. Σε άλλα δίκτυα όπως το X, ο γράφος μεταξύ των ακόλουθων είναι κατευθυνόμενος, καθώς ο χρήστης Γιώργος μπορεί να ακολουθεί την Μαρία, αλλά η Μαρία μπορεί να μην ακολουθεί τον Γιώργο.

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

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

Γράφος

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

Μη κατευθυνόμενος γράφος

Ένας μη κατευθυνόμενος γράφος είναι ένα διατεταγμένο ζεύγος $G=(V,E)$, όπου

• $V$ το σύνολο των κόμβων,
• $E$ είναι το σύνολο των ακμών, όπου για κάθε $e\in E$ υπάρχουν δύο κόμβοι $v_{1},v_{2}$ ώστε $e=\{v_{1},v_{2}\}$.

Στους μη κατευθυνόμενους γράφους κάθε ακμή είναι ένα σύνολο με (το πολύ) δύο στοιχεία αποτελούμενο από τους δύο κόμβους που ενώνονται από την εκάστοτε ακμή. Αν οι δύο κόμβοι είναι ίδιοι τότε το σύνολο αποτελείται από ένα στοιχείο και η ακμή είναι βρόγχος.

Αναπαράσταση του γράφου του παραδείγματος.

Παράδειγμα

Ο γράφος στην δεξιά εικόνα αναπαριστά τον $G=(V,E)$ με

• κόμβους $V=\{1,2,3,4,5,6,7\}$,
• ακμές $E=\left\{\{1,2\},\{1,4\},\{1,5\},\{2,3\}\{2,4\},\{2,5\},\{4,5\},\{5,8\},\{6,7\},\{7,8\}\right\}$.

Παρατηρήστε ότι με τον ορισμό αυτό η ακμή $\{1,2\}$ είναι η ίδια με την ακμή $\{2,1\}$.

Βασικές έννοιες

Βαθμός κόμβου

Η γειτονιά $N(u)$ ενός κόμβου $u$ είναι το σύνολο των κόμβων που είναι συνδεδεμένοι με τον $u$ μέσω μίας ακμής, δηλαδή

$N(u)=\{v:\{u,v\}\in E\}$.

Ο βαθμός ενός κόμβου είναι το πλήθος των γειτόνων ενός κόμβου, και συμβολίζεται ως $\operatorname {deg} (u)=|N(u)|$, από τα αρχικά της αγγλικής λέξης degree.

Στον παραπάνω γράφο, ισχύει ότι $\operatorname {deg} (1)=3$ και $\operatorname {deg} (5)=4$, καθώς $N(1)=\{2,4,5\}$ και $N(5)=\{1,2,4,8\}$.

Μονοπάτι

Ένα μονοπάτι σε έναν γράφο είναι μία ακολουθία κόμβων $u_{1},u_{2},\ldots ,u_{k}$, ώστε για κάθε $i=1,\ldots ,k-1$ ισχύει ότι η ακμή $\{u_{i},u_{i+1}\}$ ανήκει στο $E$. Ένα μονοπάτι λέγεται απλό αν κάθε κόμβος εμφανίζεται το πολύ μία φορά στο μονοπάτι.

Στον παραπάνω γράφο, η ακολουθία $(5,4,6,7)$ είναι ένα απλό μονοπάτι και η ακολουθία $(2,5,4,2,3)$ είναι ένα μη-απλό μονοπάτι (καθώς ο κόμβος $2$ επαναλαμβάνεται).

Συνεκτικότητα

Δύο κόμβοι $v$ και $w$ ενός γράφου είναι συνδεδεμένοι αν υπάρχει ένα μονοπάτι $(u_{1},\ldots ,u_{k})$ με $u_{1}=v$ και $u_{k}=w$. Ένας γράφος λέγεται συνεκτικός αν κάθε ζεύγος κόμβων του γράφου είναι συνδεδεμένοι.

Συνεκτικός γράφος

Μη-συνεκτικός γράφος

Μη-συνεκτικός γράφος

Κατευθυνόμενος γράφος

Ένας κατευθυνόμενος γράφος είναι ένα διατεταγμένο ζεύγος $G=(V,E)$, όπου:

• $V$ είναι το σύνολο των κορυφών,
• $E$ είναι το σύνολο των ακμών, όπου για κάθε $e\in E$ υπάρχουν δύο κόμβοι $v_{1}$, $v_{2}$ ώστε $e=(v_{1},v_{2})$, ώστε $e=(v_{1},v_{2})$.

Εδώ κάθε ακμή είναι ένα διατεταγμένο ζεύγος αποτελούμενο από δύο κορυφές, οι οποίες αποκαλούνται τερματικές κορυφές (κόμβοι) και δεν είναι απαραίτητα διαφορετικές μεταξύ τους. Η διαφορά ανάμεσα σε έναν μη κατευθυνόμενο και έναν κατευθυνόμενο γράφο είναι ότι στην πρώτη περίπτωση έχουμε διμελές σύνολο, ενώ στη δεύτερη διατεταγμένο ζεύγος, δηλαδή για $v_{1}\neq v_{2}$ η ακμή $(v_{1},v_{2})$ έχει την αντίθετη φορά από την $(v_{2},v_{1})$.

Παράδειγμα

Αναπαράσταση του κατευθυνόμενου γράφου του παραδείγματος.

Ο γράφος στην δεξιά εικόνα αναπαριστά τον $G=(V,E)$ με

• κόμβους $V=\{1,2,3,4,5,6,7,8\}$,
• ακμές $E=\left\{(1,5),(2,1),(3,2),(4,1),(4,2),(4,5),(4,6),(5,2),(5,4),(5,7),(5,8),(6,7),(7,8)\right\}$.

Παρατηρήστε ότι η ακμή $(4,5)$ είναι διαφορετική από την ακμή $(5,4)$.

Βασικές έννοιες

Βαθμός κόμβου

Σε αντίθεση με τους μη κατευθυνόμενους γράφους, εδώ κάθε κόμβος έχει δύο ειδών ακμές στις οποίες ανήκει, αυτές που ξεκινούν από αυτόν και αυτές που τερματίζουν σε αυτόν.

Η έσω γειτονιά $N_{-}(u)$ ενός κόμβου $u$ ορίζεται ως το σύνολο των κόμβων με ακμή προς τον $u$, δηλαδή

$N_{-}(u)=\{v\in V:(v,u)\in E\}$.

Ο έσω βαθμός του κόμβου ορίζεται ως $d_{-}(u)=|N_{-}(u)|$.

Αντίστοιχα, η έξω γειτονιά $N_{+}(u)$ ενός κόμβου $u$ ορίζεται ως το σύνολο των κόμβων με ακμή που ξεκινάει από τον $u$, δηλαδή

$N_{+}(u)=\{v\in V:(u,v)\in E\}$.

Ο έξω βαθμός του κόμβου ορίζεται ως $d_{+}(u)=|N_{+}(u)|$.

Για παράδειγμα, για τον κόμβο $5$ ισχύει ότι $N_{-}(5)=\{1,4\}$ και $N_{+}(5)=\{2,4,7,8\}$, και επομένως $d_{-}(5)=2$ και $d_{+}(5)=4$.

Μονοπάτι

Ένα μονοπάτι σε έναν γράφο είναι μία ακολουθία κόμβων $u_{1},u_{2},\ldots ,u_{k}$, ώστε για κάθε $i=1,\ldots ,k-1$ ισχύει ότι η ακμή $(u_{i},u_{i+1})$ ανήκει στο $E$.

Για παράδειγμα, στον παραπάνω γράφο η ακολουθία $(4,2,1,5,7)$ είναι ένα μονοπάτι, ενώ το $(6,7,5,2,1)$ δεν είναι καθώς δεν υπάρχει η ακμή $(7,5)$.

Συνεκτικότητα

Ένας κόμβος $w$ είναι προσβάσιμος από τον κόμβο $v$, αν υπάρχει μονοπάτι $(u_{1},\ldots ,u_{k})$ στον γράφο με $u_{1}=v$ και $u_{k}=w$. Σε αντίθεση με τους μη κατευθυνόμενους κόμβους δεν ισχύει πάντα ότι όταν ο $v$ είναι προσβάσιμος από τον $w$, τότε και ο $w$ είναι προσβάσιμος από τον $v$.

Ένας κατευθυνόμενος γράφος είναι ισχυρά συνεκτικός αν κάθε κόμβος είναι προσβάσιμος από οποιονδήποτε άλλον. Επίσης, είναι αδύναμα συνδεδεμένος αν ο αντίστοιχος υποκείμενος γράφος είναι συνδεδεμένος.

Ένας αδύναμα συνδεδεμένος γράφος που δεν είναι ισχυρά συνδεδεμένος, καθώς ο κόμβος $3$ δεν είναι προσβάσιμος από τον κόμβο $8$.

Ένας ισχυρά συνδεδεμένος γράφος, καθώς κάθε κόμβος είναι προσβάσιμος από κάθε άλλον.

Ειδικές κατηγορίες γράφων

Πλήρης γράφος με 6 κόμβους, όπου κάθε κόμβος συνδέεται με ακμή με κάθε άλλο κόμβο.

Παράδειγμα δέντρου, δηλαδή μη κατευθυνόμενου γράφου χωρίς κύκλους.

Κύκλος με 7 κόμβους.

Αστεροειδής γράφος με 7 κόμβους.

Γράφος-μονοπάτι με 5 κόμβους.

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

Ιστορία της θεωρίας γράφων

Πρόβλημα της γέφυρας της Καίνιξμπεργκ.

Διαδραστική αναπαράσταση του περίπατου του αλόγου σε μία σκακιέρα 5 × 5.

Η εργασία του Λέοναρντ Όιλερ για τις επτά γέφυρες του Καίνιξμπεργκ που δημοσιεύτηκε το 1736, θεωρείται η πρώτη εργασία στην ιστορία της θεωρίας γράφων. Αυτή η εργασία, καθώς επίσης και αυτή του Αλέξιος-Θεόφιλος Βαντερμόντ για το πρόβλημα του περίπατου ενός αλόγου σε μία σκακιέρα, έγιναν χρησιμοποιώντας ανάλυση θέσης (analysis situs) του Λάιμπνιτς. Ο τύπος του Όιλερ, σχετικά με τον αριθμό των ακμών, των κορυφών και των εδρών ενός κυρτού πολυέδρου μελετήθηκε από τον Ωγκυστέν-Λουί Κωσύ και τον Σιμόν Αντουάν Ζαν Λ' Ουιγιέ (Simon Antoine Jean L'Huillier) και θεωρείται ως η αρχή της τοπολογίας.

Σχεδόν εκατό χρόνια μετά την εργασία του Όιλερ και την εισαγωγή της τοπολογίας από τον Γιόχαν Μπένεντικτ Λίστινγκ (Johann Benedict Listing), ο Άρθουρ Κέιλι μελέτησε μια ιδιαίτερη κατηγορία γράφων, τα δέντρα. Η μελέτη αυτών των ιδιαίτερων γράφων είχε πολλές εφαρμογές στη θεωρητική χημεία. Οι τεχνικές που αναπτύχθηκαν είχαν να κάνουν κυρίως με την απαρίθμηση γράφων που παρουσίαζαν κάποιες ιδιαίτερες ιδιότητες. Η απαριθμητική θεωρία γράφων ήταν ένα από τα αποτελέσματα της εργασίας του Κέιλι και δημοσιεύσεων του Τζορτζ Πόλια (George Pólya) μεταξύ του 1935 και 1937. Αυτά γενικεύθηκαν από τον ντε Μπρούιν το 1959. Ο Κέιλι συνέδεσε τα συμπεράσματά του για τα δέντρα με τις σύγχρονες μελέτες για τη χημική σύνθεση. Η σύνθεση των μαθηματικών και των χημικών εννοιών οδήγησαν σε μεγάλο μέρος της σύγχρονης τυπικής ορολογίας της θεωρίας γράφων.

Ο Τζέιμς Τζόσεφ Συλβέστερ εισήγαγε τον όρο "γράφο" σε μία δημοσίευσή του το 1878 στο περιοδικό Nature, όπου κάνει μία αναλογία μεταξύ των "invariants" και των "co-variants" της άλγεβρας και των μοριακών διαγραμμάτων:

"[…] Κάθε invariant και co-variant επομένως μπροεί να εκφραστεί ως ένας γράφος που είναι ακριβώς ο ίδιος με ένα διάγραμμα Kekulé ή έναν χημικογράφο. […] Δίνω έναν κανόνα για τον γεωμετρικό πολλαπλασιασμό των γράφων, δηλαδή για την κατασκευή ενός γράφου για το γινόμενο των in- ή co-variants των οποίων ο γράφος είναι δοσμένος. […]"

Το πρώτο βιβλίο για την θεωρία γράφων γράφτηκε από τον Dénes Kőnig, και δημοσιεύτηκε το 1936. Ένα άλλο βιβλίο από τον Frank Harary, δημοσιεύτηκε το 1969, και "θεωρούταν ως το απόλυτο βιβλίο στο αντικείμενο", και επέτρεψε σε μαθηματικούς, χημικούς, ηλεκτρολόγους μηχανικούς και κοινωνικούς επιστήμονες να μιλάνε μεταξύ τους. Ο Harary δώρισε όλα τα δικαιώματα για να χορηγήσει το Βραβείο Pólya.

Χρωματισμός του χάρτη των ΗΠΑ με τέσσερα χρώματα (αγνοώντας τις λίμνες).

Ένα από τα πιο διάσημα προβλήματα την θεωρία γράφων είναι το θεώρημα των τεσσάρων χρωμάτων, δηλαδή ότι κάθε επίπεδος χάρτης μπορεί να χρωματιστεί με το πολύ τέσσερα χρώματα, έτσι ώστε όλες οι γειτονικές περιοχές να έχουν διαφορετικό χρώμα. Η εικασία φαίνεται να διατυπώθηκε για πρώτη φορά από τον Francis Guthrie.

Πολλές λανθασμένες αποδείξεις έχουν προταθεί, συμπεριλαμβανομένων αυτές των Κέιλι, Kempe, και άλλων. Η μελέτη και η γενίκευση αυτού του προβλήματος από τους Tait, Heawood, Ramsey και Hadwiger οδήγησαν στην μελέτη των χρωματισμών γράφων σε επιφάνειες οποιουδήποτε γένους. Η αναδιατύπωση του Tait δημιούργησε μία νέα κλάση προβλημάτων, τα προβλήματα παραγοντοποίησης, ειδικά αυτών που μελετήθηκαν από τον Petersen και τον Kőnig. Οι εργασίες του Ramsey στους χρωματισμούς και πιο συγκεκριμένα στα αποτελέσματα που βρήκε ο Turán το 1941 οδήγησαν στην δημιουργία ενός άλλου κλάδου της θεωρίας γράφων, της ακραίας θεωρίας γράφων.

Το πρόβλημα των τεσσάρων χρωμάτων έμεινε ανοιχτό για πάνω από έναν αιώνα. Το 1969, ο Heinrich Heesch δημοσίευσε μία μέθοδο για την επίλυση του προβλήματος με την χρήση υπολογιστών. Η απόδειξη με τη βοήθεια υπολογιστή από τους Kenneth Appel και Wolfgang Haken το 1976 κάνει σημαντική χρήση της έννοιας του "discharging" που αναπτύχθηκε από τον Heesch. Για την απόδειξη χρειάστηκε να ελεγχθούν οι ιδιότητες 1,936 καταστάσεων με την χρήση υπολογιστή, και κάποιοι μαθηματικοί δεν την δέχτηκαν πλήρως λόγο της πολυπλοκότητάς της. Μία πιο απλή απόδειξη που ελέγχει μόνο 633 καταστάσεις παρουσιάστηκε από τους Robertson, Seymour, Sanders and Thomas.

Η ανεξάρτητη ανάπτυξη της τοπολογίας από το 1860 έως το 1930 συνδυάστηκε με την θεωρία γράφων μέσα από τα έργα των Jordan, Kuratowski και Whitney. Άλλος ένας σημαντικός παράγοντας για την κοινή ανάπτυξη της θεωρίας γράφων και της τοπολογίας ήταν λόγω της χρήσης τεχνικών της μοντέρνας άλγεβρας. Το πρώτο παράδειγμα τέτοιας χρήστης ήταν στο έργο του φυσικού Γκούσταβ Κίρχοφ, ο οποίος το 1845 δημοσίευσε τους κανόνες του Κίρχοφ για τον υπολογισμό της διαφοράς δυναμικού και του ηλεκτρικού ρεύματος σε ένα ηλεκτρικό κύκλωμα.

Η εισαγωγή πιθανοτικών μεθόδων στην θεωρία γράφων, ειδικά μέσω της δουλειάς των Πολ Έρντος και Rényi για την ασυμπτωτική πιθανότητα της συνδεσιμότητας γράφων, οδήγησε σε άλλον έναν κλάδο, την θεωρία τυχαίων γράφων.

Περαιτέρω ανάγνωση

Online κείμενα

• Νικολόπουλος, Σταύρος· Γεωργιάδης, Λουκάς· Παληός, Λεωνίδας. Αλγοριθμική θεωρία γραφημάτων. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. ISBN 978-960-603-365-0. 
• Η θεωρία γράφων με εφαρμογές (1976) - Bondy and Murty
• Εισαγωγή στους Γράφους (2006) Hartmann and Weigt
• Διγράφοι: Θεωρία αλγόριθμοι και εφαρμογές 2007 - Jorgen Bang-Jensen and Gregory Gutin
• Θεωρία γράφων - Reinhard Diestel

Σημειώσεις

• Θηλυκός, Δημήτριος Μ. (2021). «Σημειώσεις στη θεωρία γραφημάτων» (PDF). Τμήμα Μαθηματικών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών. Ανακτήθηκε στις 15 Οκτωβρίου 2023. 

Βιβλιογραφία

• Biggs, Norman· Lloyd, Edward Keith· Wilson, Robin J.· Wilson, Robin James (1986). Graph theory: 1736 - 1936 (1η έκδοση). Oxford: Clarendon Press. ISBN 978-0-19-853916-2. 
• Cauchy, A.L. (1813). «Recherche sur les polyèdres - premier mémoire». Journal de l'Ecole Polytechnique 16 (9): 66–86. 
• Cayley, A. (1875). «Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen». Berichte der deutschen Chemischen Gesellschaft (8): 1056–1059. 
• L'Huillier, S.-A.-J. (1861). «Mémoire sur la polyèdrométrie». Annales de Mathématiques (3): 169–189. 
• Μαυρονικόλας, Μάριος (2002). Διακριτά Μαθηματικά και Μαθηματική Λογική: Θεωρία Γράφων. Πάτρα: Ε.Α.Π. ISBN 960-538-461-2. 
• Λευτέρης Κυρούσης· Χρήστος Μπούρας· Παύλος Σπυράκης· Γιάννης Σταματίου (2004). Εισαγωγή στους Γράφους Θεωρία, προβλήματα και λύσεις (2η έκδοση). Gutenberg. ISBN 978-960-01-0815-6. 

Εξωτερικοί σύνδεσμοι

• Εγχειρίδιο θεωρίας γράφων Αρχειοθετήθηκε 2012-01-16 στο Wayback Machine.
• Φωτοθήκη: γράφοι
• Συνοπτικός κατάλογος πηγών για τη θεωρία γράφων
• Graph Theory Software Αρχειοθετήθηκε 2013-03-13 στο Wayback Machine.

Ελληνικά άρθρα

• Χριστόπουλος, Παναγιώτης Π. (Απριλίου 2019). «Οι επτά γέφυρες και τα γραφήματα». Ευκλείδης Β΄ (114): 4-8. http://www.hms.gr/sites/default/files/subsites/problems/material/EYKLEIDHS_B_114_EYKLEIDHS_2019.pdf.