Back to search

National and Kapodistrian University of Athens

Αλγοριθμικές Τεχνικές για προβλήματα μέτρησης σε γραφήματα

Abstract

dc:description

Στην εργασία αυτή θα ασχοληθούμε με το πρόβλημα της καταμέτρησης του πλήθους των εναγομένων υπογραφημάτων με k κορυφές, ενός δοσμένου γραφήματος G, που έχουν άρτια ποσότητα ακμών, και αυτά τα υπογραφήματα τα καλούμε άρτια υπογραφήματα. Αρχικά, θα διερευνήσουμε τα δομικά χαρακτηριστικά που πρέπει να έχει ένα γράφημα ώστε να εξασφαλίζεται η ύπαρξη, ή όχι, τουλάχιστον ενός άρτιου εναγομένου υπογραφήματος k κορυφών. Με την βοήθεια φράγματος της θεωρίας Ramsey, θα καταλήξουμε ότι, για γραφήματα με μεγάλο πλήθος ακμών, η ύπαρξη τουλάχιστον ενός άρτιου εναγομένου γραφήματος k κορυφών μπορεί πολύ εύκολα να αποφασιστεί, ελέγχοντας αν το γράφημα G ανήκει σε κάποιες συγκεκριμένες οικογένειες γραφημάτων, το πλήθος των οποίων είναι πολύ μικρό, και εξετάζοντας κάποιες απλές αριθμητικές σχέσεις για το k. Χρησιμοποιώντας τα παραπάνω δεδομένα, θα κατασκευάσουμε έναν παραμετρικό αλγόριθμο, με παράμετρο το k, που θα αποφασίζει αν ένα γράφημα περιέχει ένα τέτοιο υπογράφημα με k κορυφές. Επιπλέον, συναντάμε ένα απροσδόκητο αποτέλεσμα, που μας εξασφαλίζει ότι αν ένα γράφημα n κορυφών έχει τουλάχιστον ένα άρτιο εναγόμενο υπογράφημα k κορυφών, όπου το n είναι αρκετά πιο μεγάλο από το k, τότε θα έχει ένα μεγάλο πλήθος τέτοιων υπογραφημάτων. Μάλιστα το πλήθος αυτών των υπογραφημάτων είναι επαρκώς μεγάλο ώστε η μέθοδος της τυχαίας δειγματοληψίας να παρέχει μια καλή εκτίμηση του συνολικού πλήθους τέτοιων υπογραφημάτων χωρίς απαιτούνται υπερβολικά πολλές δοκιμές. Αντίστοιχη μελέτη γίνεται για το πρόβλημα απόφασης ύπαρξης περιττών εναγομένων υπογραφημάτων k κορυφών, δηλαδή υπογραφημάτων έχουν περιττό πλήθος ακμών, όπως και για το αντίστοιχο πρόβλημα καταμέτρησης.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Καλογιάννη Μαρία
  • Kalogianni Maria

Subjects

dc:subject × 2

Rights

Language dc:language
Ελληνικά, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:2838872

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Καλογιάννη Μαρία; Kalogianni Maria. Αλγοριθμικές Τεχνικές για προβλήματα μέτρησης σε γραφήματα. 2019. https://pergamos.lib.uoa.gr/uoa/dl/object/2838872