Η παρούσα διπλωματική εργασία μελετά το θεμελιώδες πρόβλημα της απαρίθμησης κύκλων άρτιου μήκους υπό το πρίσμα της ακραίας θεωρίας γραφημάτων. Κεντρική ιδέα είναι ότι η δομική πληροφορία για τον αριθμό των κύκλων άρτιου μήκους σε διμερή γραφήματα μπορεί να μετατραπεί σε φράγματα για τον χρόνο εκτέλεσης αλγορίθμων απαρίθμησης κύκλων.
Κύριο αποτέλεσμα της εργασίας είναι μια ασθενής μορφή της Εικασίας Μη Ισορροπημένου Υπερκορεσμού για άρτιους κύκλους. Αποδεικνύουμε ότι ένα διμερές γράφημα \(G=(A\cup B,E)\) με επαρκώς πολλές ακμές ως προς το κατώφλι \( \max\{|A|,|B|\}\cdot\min\{|A|,|B|\}^{1/k} \) πρέπει να περιέχει πολλές εμφανίσεις \(C_{2k}\). Παρότι το αποτέλεσμα αυτό αποτελεί ένα βήμα προς την πλήρη εικασία, παρέχει ήδη επαρκή πληροφορία για τις αλγοριθμικές εφαρμογές που εξετάζονται στην παρούσα εργασία.
Χρησιμοποιώντας αυτό το ακραίο φράγμα, επανεξετάζουμε το πλαίσιο ανάλυσης των Williams και Westover για την απαρίθμηση άρτιων κύκλων. Αυτό οδηγεί σε μια βελτιωμένη ανάλυση του χρόνου εκτέλεσης, η οποία ισοφαρίζει την τρέχουσα βέλτιστη επίδοση για την απαρίθμηση \(C_6\), αποφεύγοντας όμως τη χρήση υπολογιστή. Επιπλέον, βελτιώνει το προηγουμένως γνωστό βέλτιστο φράγμα για την απαρίθμηση \(C_{2k}\) για κάθε \(k\ge 4\), το οποίο οφείλεται στους Alon, Yuster και Zwick.
Επεκτείνουμε επίσης τη συζήτηση στα υπεργραφήματα. Το γράφημα πρόσπτωσης δίνει μια γενική αναγωγή από την απαρίθμηση κύκλων Berge σταθερού μήκους \(\ell\) στην απαρίθμηση κύκλων μήκους \(2\ell\) σε απλά γραφήματα. Επιπλέον, δίνουμε μια άμεση αναγωγή μέσω του επισημασμένου \(2\)-σκειώδες γραφήματος για την απαρίθμηση όλων των κύκλων Berge μήκους \(\ell\) που περνούν από μια προκαθορισμένη κορυφή του υπεργραφήματος.