ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ SITE MAP | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΕΛΛΗΝΙΚΑ | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ENGLISH
Παρασκευή, 31/10/2014   -   Ομιλίες
Σεμινάριο Τμήματος με τίτλο: Δισυνεκτικότητα Γραφημάτων
Σεμινάριο Τμήματος

Στο πλαίσιο της διοργάνωσης εβδομαδιαίων σεμιναρίων του τμήματος διοργανώνεται η τρίτη διάλεξη να πραγματοποιηθεί την Παρασκευή 31/10/2014 και ώρα 12:00 στην αίθουσα Σεμιναρίων του Τμήματος Μηχανικών Η/Υ και Πληροφορικής. Ομιλητής θα είναι ο κ. Λουκάς Γεωργιάδης και o τίτλος της διάλεξης «Δισυνεκτικότητα Γραφημάτων».

ΠΕΡΙΛΗΨΗ

Η συνεκτικότητα είναι μια από τις θεμελιώδεις έννοιες στη θεωρία γραφημάτων, η οποία συναντάται σε πολλές πρακτικές εφαρμογές. Παρόλο που έχει μελετηθεί εκτενώς στην περίπτωση των μη κατευθυνόμενων γραφημάτων, πολλά θέματα συνεκτικότητας σε κατευθυνόμενα γραφήματα παραμένουν ανεξερεύνητα. Θα αναφερθούμε σε διάφορες έννοιες δισυνεκτικότητας και θα εστιάσουμε στον υπολογισμό της ακόλουθης σχέσης μεταξύ των κόμβων ενός γραφήματος. Δύο κόμβοι v και w είναι 2-συνδεδεμένοι εάν υπάρχουν δύο μη τεμνόμενα μονοπάτια από τον ν προς τον u και δύο μη τεμνόμενα μονοπάτια από τον u προς τον v. Θα παρουσιάσουμε έναν αλγόριθμο που υπολογίζει την παραπάνω σχέση σε γραμμικό χρόνο. Επίσης, θα δείξουμε ότι η σχέση αυτή μπορεί να αναπαρασταθεί με μια δομή δεδομένων η οποία ελέγχει σε σταθερό χρόνο αν δύο κόμβοι του γραφήματος είναι 2-συνδεδεμένοι.

©2010 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING - UNIVERSITY OF IOANNINA
created by data|SCIENCE

Valid XHTML 1.0 Strict Valid CSS!