Προβλήματα απαρίθμησης σε γραφήματα και υπό την ύπαρξη συμμετριών

• Κύριος συγγραφέας: Κανελλοπούλου, Μαρία
• Άλλοι συγγραφείς: Καββαδίας, Δημήτριος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2017
• Θέματα: Θεώρημα απαρίθμησης Polya; Συμμετρίες; Polya's enumeration theorem; Symmetries; 511.62

Η παρούσα διπλωματική εργασία πραγματεύεται την απαρίθμηση διακριτών δομών υπό την ύπαρξη συμμετριών και την απαρίθμηση γραφημάτων. Στο πρώτο κεφάλαιο παρουσιάζουμε την έννοια της διαμέρισης ενός συνόλου και της σχέσης ισοδυναμίας μεταξύ δύο στοιχείων ενός συνόλου. Στη συνέχεια μελετάμε κάτω από ποιες συνθήκες ένα σύνολο αποτελεί ομάδα καθώς και τους ορισμούς της μετάθεσης και της ομάδας μεταθέσεων. Στην τελευταία ενότητα παραθέτουμε τις σημαντικότερες πράξεις στις ομάδες μεταθέσεων, οι οποίες παράγουν άλλες ομάδες μεταθέσεων. Στο δεύτερο κεφάλαιο ασχολούμαστε με τη θεωρία γραφημάτων παρουσιάζοντας αρχικά την ορολογία, το συμβολισμό και βασικά θεωρητικά αποτελέσματα των γραφημάτων. Έπειτα δίνουμε τον ορισμό του ισομορφισμού, του ομομορφισμού και του αυτομορφισμού γραφημάτων, καθώς και τον τρόπο εύρεσης μιας ομάδας μεταθέσεων για μερικά χαρακτηριστικά γραφήματα. Επίσης, ασχολούμαστε με την ομάδα αυτομορφισμών για ένα γράφημα, ενώ κλείνοντας το κεφάλαιο μελετάμε την ομάδα σύνθετου γραφήματος, τα γραφήματα με δοσμένη ομάδα και τα συμμετρικά γραφήματα. Στο τελευταίο κεφάλαιο αναφερόμαστε στο τι είναι, πως αναπτύσσεται και πως μπορούμε να χρησιμοποιήσουμε το Λήμμα Burnside που αφορά την απαρίθμηση διακριτών δομών όταν έχουν οριστεί συμμετρίες. Επιπρόσθετα μελετάμε το Θεώρημα Polya, το οποίο χρησιμοποιείται σε περιπτώσεις απαρίθμησης διακριτών δομών με συμμετρίες με συγκεκριμένες ιδιότητες. Επίσης πραγματευόμαστε την απαρίθμηση γραφημάτων χρησιμοποιώντας το θεώρημα Polya για να ανακαλύψουμε τον αριθμό των γραφημάτων με p κορυφές και q ακμές, να δούμε τι συμβαίνει με τα διμερή γραφήματα Κ_(m,n), όπου m≠n, την απαρίθμηση των «rooted trees» με p κορυφές και την απαρίθμηση μη-ισομορφικών γραφημάτων. Στην τελευταία υποενότητα απαντάμε τόσο θεωρητικά όσο και μέσα από παραδείγματα στην ερώτηση πόσα δέντρα υπάρχουν στο σύνολο κορυφών [n]={1,2,…,n};