Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/39117Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Σταμάτης, Κωνσταντίνος | el |
| dc.date.accessioned | 2025-06-30T10:26:08Z | - |
| dc.date.available | 2025-06-30T10:26:08Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/39117 | - |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | Graphs, Comparability graphs, Permutation graphs | en |
| dc.title | Adding an Edge in Comparability and Permutation Graphs | en |
| dc.type | masterThesis | en |
| heal.type | masterThesis | el |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.dateAvailable | 2025-06-30T10:27:08Z | - |
| heal.language | en | el |
| heal.access | free | el |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή | el |
| heal.recordProvider | Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2025-06-21 | - |
| heal.abstract | Η επέκταση ενός γραφήματος 𝐺(𝑉,𝐸) μιας κλάσης 𝐶 μέσω της εισαγωγής ενός κόμβου 𝑣 ∉ 𝑉 και της σύνδεσής του με έναν κόμβο 𝑣𝑖 ∈ 𝑉 δεν παράγει απαραίτητα ένα γράφημα που ανήκει στην 𝐶. Αυτή η διατριβή αφορά την εύρεση και υλοποίηση αλγορίθμων που αποφασίζουν εάν η απλή προσθήκη μιας ακμής μεταξύ 𝑣 και 𝑣𝑖 στο 𝐺 έχει ως αποτέλεσμα ένα γράφημα που ανήκει στην 𝐶, και εάν όχι υπολογίζει το ελάχιστο πλήθος ακμών που χρειάζεται να προστεθούν στο γράφημα που προέκυψε ώστε αυτό να ανήκει στην 𝐶, όπου 𝐶 είτε αναφέρεται σε μεταβατικά (comparability) ή μεταθετικά (permutation) γραφήματα. Στην περίπτωση των μεταβατικών γραφημάτων, αποδεικνύουμε ότι το πρόβλημα ανάγεται στον υπολογισμό μιας μεταβατικής κατεύθυνσης (transitive orientation) 𝐹⃗ του 𝐺 στην οποία η 𝑣𝑖 έχει ελάχιστο out-degree, και κατασκευάζουμε έναν αλγόριθμο εκμεταλλευόμενοι το γεγονός ότι η ένωση των μεταβατικών κατευθύνσεων όλων των μεγιστικών multiplices ενός γραφήματος είναι μεταβατική κατεύθυνση του γραφήματος αυτού, που μας επιτρέπει να ενδιαφερθούμε για το out-degree της 𝑣𝑖 μόνο στα μεγιστικά multiplices στα οποία ανήκουν ακμές που την περιέχουν. Χρησιμοποιούμε το γεγονός ότι τα μεταθετικά γραφήματα είναι ακριβώς τα μεταβατικά γραφήματα με συμπλήρωμα που είναι μεταβατικό γράφημα για να μετατρέψουμε τον παραπάνω αλγόριθμο σε έναν αλγόριθμο που δίνει απάντηση για τα μεταθετικά γραφήματα. Επιπλέον, παραθέτουμε τη σχεδίαση ενός ακόμα αλγορίθμου που λύνει το πρόβλημα για μεταθετικά γραφήματα, ο οποίος βελτιώνει σημαντικά την εξαντλητική αναζήτηση κατά την οποία προστίθεται ένας αριθμός για τον νέο κόμβο 𝑣 σε κάθε μετάθεση που αναπαριστά το 𝐺 έτσι ώστε να σχηματίζεται αναστροφή με τον ακέραιο που αντιστοιχεί στoν 𝑣𝑖 . Οι αλγόριθμοι υλοποιήθηκαν στη γλώσσα προγραμματισμού Python και τα γραφήματα μοντελοποιούνται μέσω του module networkx, και εξηγούνται αναλυτικά μετά την παράθεση του κάθε αλγορίθμου. | en |
| heal.advisorName | Παληός, Λεωνίδας | el |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.committeeMemberName | Μάρκου, Ευριπίδης | el |
| heal.committeeMemberName | Νομικός, Χρήστος | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.academicPublisherID | uoi | el |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΗΥΠ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. Κωνσταντίνος Σταμάτης (2025).pdf | 1.5 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
