{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2838872"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2838872","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Αλγοριθμικές Τεχνικές για προβλήματα μέτρησης σε γραφήματα","abstract":"Στην εργασία αυτή θα ασχοληθούμε με το πρόβλημα της καταμέτρησης του πλήθους των εναγομένων υπογραφημάτων με k κορυφές, ενός δοσμένου γραφήματος G, που έχουν άρτια ποσότητα ακμών, και αυτά τα υπογραφήματα τα καλούμε άρτια υπογραφήματα. Αρχικά, θα διερευνήσουμε τα δομικά χαρακτηριστικά που πρέπει να έχει ένα γράφημα ώστε να εξασφαλίζεται η ύπαρξη, ή όχι, τουλάχιστον ενός άρτιου εναγομένου υπογραφήματος k κορυφών. Με την βοήθεια φράγματος της θεωρίας Ramsey, θα καταλήξουμε ότι, για γραφήματα με μεγάλο πλήθος ακμών, η ύπαρξη τουλάχιστον ενός άρτιου εναγομένου γραφήματος k κορυφών μπορεί πολύ εύκολα να αποφασιστεί, ελέγχοντας αν το γράφημα G ανήκει σε κάποιες συγκεκριμένες οικογένειες γραφημάτων, το πλήθος των οποίων είναι πολύ μικρό, και εξετάζοντας κάποιες απλές αριθμητικές σχέσεις για το k. Χρησιμοποιώντας τα παραπάνω δεδομένα, θα κατασκευάσουμε έναν παραμετρικό αλγόριθμο, με παράμετρο το k, που θα αποφασίζει αν ένα γράφημα περιέχει ένα τέτοιο υπογράφημα με k κορυφές. Επιπλέον, συναντάμε ένα απροσδόκητο αποτέλεσμα, που μας εξασφαλίζει ότι αν ένα γράφημα n κορυφών έχει τουλάχιστον ένα άρτιο εναγόμενο υπογράφημα k κορυφών, όπου το n είναι αρκετά πιο μεγάλο από το k, τότε θα έχει ένα μεγάλο πλήθος τέτοιων υπογραφημάτων. Μάλιστα το πλήθος αυτών των υπογραφημάτων είναι επαρκώς μεγάλο ώστε η μέθοδος της τυχαίας δειγματοληψίας να παρέχει μια καλή εκτίμηση του συνολικού πλήθους τέτοιων υπογραφημάτων χωρίς απαιτούνται υπερβολικά πολλές δοκιμές. Αντίστοιχη μελέτη γίνεται για το πρόβλημα απόφασης ύπαρξης περιττών εναγομένων υπογραφημάτων k κορυφών, δηλαδή υπογραφημάτων έχουν περιττό πλήθος ακμών, όπως και για το αντίστοιχο πρόβλημα καταμέτρησης.","abstract_html":"Στην εργασία αυτή θα ασχοληθούμε με το πρόβλημα της καταμέτρησης του πλήθους των εναγομένων υπογραφημάτων με k κορυφές, ενός δοσμένου γραφήματος G, που έχουν άρτια ποσότητα ακμών, και αυτά τα υπογραφήματα τα καλούμε άρτια υπογραφήματα. Αρχικά, θα διερευνήσουμε τα δομικά χαρακτηριστικά που πρέπει να έχει ένα γράφημα ώστε να εξασφαλίζεται η ύπαρξη, ή όχι, τουλάχιστον ενός άρτιου εναγομένου υπογραφήματος k κορυφών. Με την βοήθεια φράγματος της θεωρίας Ramsey, θα καταλήξουμε ότι, για γραφήματα με μεγάλο πλήθος ακμών, η ύπαρξη τουλάχιστον ενός άρτιου εναγομένου γραφήματος k κορυφών μπορεί πολύ εύκολα να αποφασιστεί, ελέγχοντας αν το γράφημα G ανήκει σε κάποιες συγκεκριμένες οικογένειες γραφημάτων, το πλήθος των οποίων είναι πολύ μικρό, και εξετάζοντας κάποιες απλές αριθμητικές σχέσεις για το k. Χρησιμοποιώντας τα παραπάνω δεδομένα, θα κατασκευάσουμε έναν παραμετρικό αλγόριθμο, με παράμετρο το k, που θα αποφασίζει αν ένα γράφημα περιέχει ένα τέτοιο υπογράφημα με k κορυφές. Επιπλέον, συναντάμε ένα απροσδόκητο αποτέλεσμα, που μας εξασφαλίζει ότι αν ένα γράφημα n κορυφών έχει τουλάχιστον ένα άρτιο εναγόμενο υπογράφημα k κορυφών, όπου το n είναι αρκετά πιο μεγάλο από το k, τότε θα έχει ένα μεγάλο πλήθος τέτοιων υπογραφημάτων. Μάλιστα το πλήθος αυτών των υπογραφημάτων είναι επαρκώς μεγάλο ώστε η μέθοδος της τυχαίας δειγματοληψίας να παρέχει μια καλή εκτίμηση του συνολικού πλήθους τέτοιων υπογραφημάτων χωρίς απαιτούνται υπερβολικά πολλές δοκιμές. Αντίστοιχη μελέτη γίνεται για το πρόβλημα απόφασης ύπαρξης περιττών εναγομένων υπογραφημάτων k κορυφών, δηλαδή υπογραφημάτων έχουν περιττό πλήθος ακμών, όπως και για το αντίστοιχο πρόβλημα καταμέτρησης.","abstract_has_math":false,"creators":["Καλογιάννη Μαρία","Kalogianni Maria"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-11-19T05:33:26Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2838872"],"render_values":[{"text":"uoadl:2838872","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2838872","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2838872","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A2838872","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Καλογιάννη Μαρία","Kalogianni Maria"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2838872","https://pergamos.lib.uoa.gr/uoa/dl/object/2838872"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Στην εργασία αυτή θα ασχοληθούμε με το πρόβλημα της καταμέτρησης του πλήθους των εναγομένων υπογραφημάτων με k κορυφές, ενός δοσμένου γραφήματος G, που έχουν άρτια ποσότητα ακμών, και αυτά τα υπογραφήματα τα καλούμε άρτια υπογραφήματα. Αρχικά, θα διερευνήσουμε τα δομικά χαρακτηριστικά που πρέπει να έχει ένα γράφημα ώστε να εξασφαλίζεται η ύπαρξη, ή όχι, τουλάχιστον ενός άρτιου εναγομένου υπογραφήματος k κορυφών. Με την βοήθεια φράγματος της θεωρίας Ramsey, θα καταλήξουμε ότι, για γραφήματα με μεγάλο πλήθος ακμών, η ύπαρξη τουλάχιστον ενός άρτιου εναγομένου γραφήματος k κορυφών μπορεί πολύ εύκολα να αποφασιστεί, ελέγχοντας αν το γράφημα G ανήκει σε κάποιες συγκεκριμένες οικογένειες γραφημάτων, το πλήθος των οποίων είναι πολύ μικρό, και εξετάζοντας κάποιες απλές αριθμητικές σχέσεις για το k. Χρησιμοποιώντας τα παραπάνω δεδομένα, θα κατασκευάσουμε έναν παραμετρικό αλγόριθμο, με παράμετρο το k, που θα αποφασίζει αν ένα γράφημα περιέχει ένα τέτοιο υπογράφημα με k κορυφές. Επιπλέον, συναντάμε ένα απροσδόκητο αποτέλεσμα, που μας εξασφαλίζει ότι αν ένα γράφημα n κορυφών έχει τουλάχιστον ένα άρτιο εναγόμενο υπογράφημα k κορυφών, όπου το n είναι αρκετά πιο μεγάλο από το k, τότε θα έχει ένα μεγάλο πλήθος τέτοιων υπογραφημάτων. Μάλιστα το πλήθος αυτών των υπογραφημάτων είναι επαρκώς μεγάλο ώστε η μέθοδος της τυχαίας δειγματοληψίας να παρέχει μια καλή εκτίμηση του συνολικού πλήθους τέτοιων υπογραφημάτων χωρίς απαιτούνται υπερβολικά πολλές δοκιμές. Αντίστοιχη μελέτη γίνεται για το πρόβλημα απόφασης ύπαρξης περιττών εναγομένων υπογραφημάτων k κορυφών, δηλαδή υπογραφημάτων έχουν περιττό πλήθος ακμών, όπως και για το αντίστοιχο πρόβλημα καταμέτρησης.","Given a graph G, we study the problem of counting the number of even induced subgraphs with k vertices. As even graph, we call a graph that has even number of vertices. Firstly, we will present the structural results that a graph should satisfy in order to have at least one even induced subgraph with k vertices. Using a lower bound from Ramsey theory, we will conclude that, for graphs with enough large number of vertices, the existence of at least one even induced subgraph k vertices can be easily decided by checking if the graph G belongs in a certain and small group of graph families, and checking some simple arithmetic relations for k. Using the above, we design a parameterized algorithm, with k as parameter, that decides whether there is an even subgraph in the given graph in k vertices. Moreover, we find an unexpected result, which shows that if a graph G with n vertices (where n is efficiently larger than k) has at least one even subgraph, then the G will have a large number of these subgraphs. Actually, the number of these subgraphs is large enough in order the method of random sampling to give a good approximation of the total number of these subgraphs without demanding too many repetitions. Accordingly, we study the same aspects for the odd induced subgraphs with k vertices, i.e., those which have odd number of edges."]},{"key":"dc:title","label":"Title","values":["Αλγοριθμικές Τεχνικές για προβλήματα μέτρησης σε γραφήματα"]}]}],"canonical_facts":{"dc:creator":["Καλογιάννη Μαρία","Kalogianni Maria"],"dc:date":["2019"],"dc:description":["Στην εργασία αυτή θα ασχοληθούμε με το πρόβλημα της καταμέτρησης του πλήθους των εναγομένων υπογραφημάτων με k κορυφές, ενός δοσμένου γραφήματος G, που έχουν άρτια ποσότητα ακμών, και αυτά τα υπογραφήματα τα καλούμε άρτια υπογραφήματα. Αρχικά, θα διερευνήσουμε τα δομικά χαρακτηριστικά που πρέπει να έχει ένα γράφημα ώστε να εξασφαλίζεται η ύπαρξη, ή όχι, τουλάχιστον ενός άρτιου εναγομένου υπογραφήματος k κορυφών. Με την βοήθεια φράγματος της θεωρίας Ramsey, θα καταλήξουμε ότι, για γραφήματα με μεγάλο πλήθος ακμών, η ύπαρξη τουλάχιστον ενός άρτιου εναγομένου γραφήματος k κορυφών μπορεί πολύ εύκολα να αποφασιστεί, ελέγχοντας αν το γράφημα G ανήκει σε κάποιες συγκεκριμένες οικογένειες γραφημάτων, το πλήθος των οποίων είναι πολύ μικρό, και εξετάζοντας κάποιες απλές αριθμητικές σχέσεις για το k. Χρησιμοποιώντας τα παραπάνω δεδομένα, θα κατασκευάσουμε έναν παραμετρικό αλγόριθμο, με παράμετρο το k, που θα αποφασίζει αν ένα γράφημα περιέχει ένα τέτοιο υπογράφημα με k κορυφές. Επιπλέον, συναντάμε ένα απροσδόκητο αποτέλεσμα, που μας εξασφαλίζει ότι αν ένα γράφημα n κορυφών έχει τουλάχιστον ένα άρτιο εναγόμενο υπογράφημα k κορυφών, όπου το n είναι αρκετά πιο μεγάλο από το k, τότε θα έχει ένα μεγάλο πλήθος τέτοιων υπογραφημάτων. Μάλιστα το πλήθος αυτών των υπογραφημάτων είναι επαρκώς μεγάλο ώστε η μέθοδος της τυχαίας δειγματοληψίας να παρέχει μια καλή εκτίμηση του συνολικού πλήθους τέτοιων υπογραφημάτων χωρίς απαιτούνται υπερβολικά πολλές δοκιμές. Αντίστοιχη μελέτη γίνεται για το πρόβλημα απόφασης ύπαρξης περιττών εναγομένων υπογραφημάτων k κορυφών, δηλαδή υπογραφημάτων έχουν περιττό πλήθος ακμών, όπως και για το αντίστοιχο πρόβλημα καταμέτρησης.","Given a graph G, we study the problem of counting the number of even induced subgraphs with k vertices. As even graph, we call a graph that has even number of vertices. Firstly, we will present the structural results that a graph should satisfy in order to have at least one even induced subgraph with k vertices. Using a lower bound from Ramsey theory, we will conclude that, for graphs with enough large number of vertices, the existence of at least one even induced subgraph k vertices can be easily decided by checking if the graph G belongs in a certain and small group of graph families, and checking some simple arithmetic relations for k. Using the above, we design a parameterized algorithm, with k as parameter, that decides whether there is an even subgraph in the given graph in k vertices. Moreover, we find an unexpected result, which shows that if a graph G with n vertices (where n is efficiently larger than k) has at least one even subgraph, then the G will have a large number of these subgraphs. Actually, the number of these subgraphs is large enough in order the method of random sampling to give a good approximation of the total number of these subgraphs without demanding too many repetitions. Accordingly, we study the same aspects for the odd induced subgraphs with k vertices, i.e., those which have odd number of edges."],"dc:identifier":["uoadl:2838872","https://pergamos.lib.uoa.gr/uoa/dl/object/2838872"],"dc:language":["Ελληνικά","Greek"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Αλγοριθμικές Τεχνικές για προβλήματα μέτρησης σε γραφήματα"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:33:26Z"}