δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
(EL)
Κιαφζέζι, Ιωάννα
(EL)
Ο κεντρικός στόχος της παρούσης διατριβής είναι η παρουσίαση και ανάλυση σε ϐάθος του προβλήματος της εύρεσης ενός μη συνεκτικού διαχωριστή σε συνεκτικά γραφήματα: δοθέντος ενός συνεκτικού γραφήματος G, ϑέλουμε να υπολογίσουμε ένα υποσύνολο κορυφών S (το οποίο καλείται διαχωριστής) ,τέτοιο ώστε τα δύογραφήματα G\S και G [S] να είναι μη-συνεκτικά γραφήματα. Με άλ λα λόγια το πρόβλημα αποσκοπεί στην εύρεση ενός μη-συνεκτικού διαχωριστή. Μελετάμε την υπολογιστική πολυπλοκότητα του προβλήματος που συναντάται στη σύγχρονη ϐιβλιογραφία. Πιοσυγκεκριμένα, η διατριβή αποτελείται από πέντε κεφάλαια. Στο πρώτο κεφάλαιο αναφέρονται εισαγωγικές έννοιες της ϑεωρίας γραφημάτων καθώς και η έννοια της υπολογιστικής πολυπλοκότητας.Το δεύτερο κεφάλαιο είναι αφιερωμένο στον ορισμό του προβλήματος του μη συνεκτικού διαχωριστή και σε προβλήματα ισοδύναμα με αυτό.Στο τρίτο κεφάλαιο αναλύεται η υπολογιστική πολυπλοκότητα του προβλήματος στις περιπτώσεις όπου το γράφημα έχει διάμετρο ίση με δύο και διάμετρο διάφορη του δύο. Στο επόμενο κεφάλαιο αναφέρουμε τις κλάσεις γραφημάτων όπου το πρόβλημα ε πιδέχεται πολυωνυμική λύση, εστιάζοντας στα H-free γραφήματα.Στο πέμπτο και τελευταίο κεφάλαιο παρουσιάζουμε τα συμπεράσματα αυτής της διατριβής και επίσης επεκτείνουμε τα ήδη γνωστά πολυωνυμικά αποτελέσματα, σχεδιάζο ντας τον πρώτο πολυωνυμικό αλγόριθμο για την κλάση των distance-hereditary γραφημάτων.
(EL)
The principal aim of this thesis is to present an extended analysis of the problem of finding a disconnected cut within a connected graph: given a connected graph G, our task is to find a set S of vertices such that both graphs G\S and G [S] are disconnected. Therefore, the goal of the problem is to find a disconnected cut of a given connected graph .We study the computational complexity of disconnected cut problem, which can be found in the modern literature. More specifically, the thesis consists of five chapters. In the first chapter mentioned some basic concepts in graph theory and the definition of computational complexity .The second chapter is devoted to the definition of disconnected cut problem and some polynomially equivalent problems .In the third chapter we analyze the computational complexity of disconnected cut to graphs of diameter2 and to graphs of diameter 1 or at least 3.Inthenext chapter we mention several graph classes where the disconnected cut problem has polynomial-time algorithms. We are focused on H-free graphs. In the fifth and last chapter we present the conclusions of this thesis and also extend the already known polynomial results, constructing the first polynomial algorithm for distance-hereditary graphs.
(EN)
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
(EL)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
