Στη διπλωματική εργασία προς παρουσίαση, πραγματευόμαστε ένα νέο είδος γραφημάτων, τα χρονικά γραφήματα, και διάφορες παραλλαγές τους.
Ένα χρονικό γράφημα είναι μια διατεταγμενη τριάδα G={V,E,L}, όπου V ένα μη κενό πεπερασμένο σύνολο που καλείται σύνολο κορυφών, E ένα σύνολο m στοιχείων, καθένα από τα οποία είναι δισύνολο στοιχείων του V (καλείται σύνολο ακμών), και L= {L_e, για κάθε e στοιχείο του E} = {L_e_1, L_e_2, ..., L_e_m}, όπου L_e_i, i = 1,..., m, σύνολο θετικών ακεραίων τιμών που αντιστοιχίζονται στην ακμή e_i του συνόλου E (καλείται ανάθεση χρονικών ετικετών ή απλώς ανάθεση).
Οι τιμές που αντιστοιχίζονται σε κάθε ακμή του γραφήματος καλούνται χρονικές ετικέτες της ακμής και δηλώνουν τις χρονικές στιγμές, κατά τις οποίες έχουμε τη δυνατότητα να τη διασχίσουμε (από το ένα της άκρο προς το άλλο).
Για να αντιληφθεί κανείς το ενδιαφέρον των χρονικών γραφημάτων, μπορεί να σκεφτεί τη δυνατότητα εφαρμογής τους στην καθημερινότητα. Για παράδειγμα, οι χρονικές ετικέτες που ανατίθενται σε μία ακμή ενός κατευθυνόμενου χρονικού γραφήματος μπορούν να παραλληλιστούν με τις ώρες, στις οποίες γίνονται αναχωρήσεις αεροπλάνων από μία πόλη προς μια άλλη. Έτσι, η μελέτη των χρονικών γραφημάτων θα μπορούσε να συμβάλει στην οργάνωση των πτήσεων ενός αεροδρομίου.
Ένα χρονικό μονοπάτι (ή «ταξίδι») σε ένα χρονικό γράφημα είναι ένα μονοπάτι, στις ακμές του οποίου μπορούμε να βρούμε αυστηρά αύξουσα σειρά χρονικών ετικετών.
Στην εργασία, μεταξύ άλλων, γίνεται μελέτη της συνδετικότητας στα χρονικά γραφήματα, καθώς και κατασκευή και μελέτη αλγορίθμων εύρεσης χρονικών μονοπατιών («ταξιδίων») που φθάνουν το δυνατόν συντομότερα στον προορισμό τους (τελική κορυφή μονοπατιού). Επιπλέον, μελετώνται στατιστικά τα Χρονικά Γραφήματα, με επικέντρωση στο αναμενόμενο πλήθος χρονικών μονοπατιών σε ένα γράφημα, καθώς και στη Χρονική Διάμετρο ενός γραφήματος, όπως αυτή ορίζεται στην εργασία. / In the thesis, we are dealing with a new type of graphs,called Temporal Graphs, and several variants.
A temporal graph is an ordered triplet G={V,E,L}, where V stands for a nonempty finite set (called set of vertices), E stands for a set of m elements, each of which are 2-element subsets of V (called set of edges), and L= {L_e, for all e in E} = {L_e_1, L_e_2, ..., L_e_m}, where L_e_i, i = 1, ..., m, is a set of positive integers mapped to edge e_i in E (called assignment of time labels or simply assignment).
The values assigned to each edge of the graph are called time labels of the edge and indicate the times at which we can cross it (from one end to the other).
In order to understand the interest of temporal graphs, one may think their applicability to everyday life. For example, the time labels assigned to an edge of a directed temporal graph can be paralleled to the flight departure times from one city to another. Therefore, the study of temporal graphs could contribute to the organization of flights at an airport.
A temporal path (or «journey») in a temporal graph is a path, on the edges of which we can find strictly ascending time labels.
In the thesis, among others, we study the connectivity of temporal graphs and we construct and study several algorithms that find temporal paths which arrive the soonest possible at their destination (final vertice of the path).
Furthermore, we examine temporal graphs statistically, focusing on the expected number of temporal paths in a graph as well as in the Temporal Diameter of a graph, also defined in the thesis.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/6277 |
| Date | 04 September 2013 |
| Creators | Ακρίδα, Ελένη |
| Contributors | Σπυράκης, Παύλος, Akrida, Eleni, Σπυράκης, Παύλος, Ζαγούρας, Χαράλαμπος, Αλεβίζος, Φίλιππος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0027 seconds