Στη διπλωματική εργασία προς παρουσίαση, πραγματευόμαστε ένα νέο είδος γραφημάτων, τα χρονικά γραφήματα, και διάφορες παραλλαγές τους. Ένα χρονικό γράφημα είναι μια διατεταγμενη τριάδα 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.

Parmi les évolutions majeures de l'informatique, nous distinguons l'émergence des technologies mobiles sans fil. Le développement actuel de ces technologies permet de réaliser des communications ad-hoc directes entre de nombreux types d'entités mobiles, comme des véhicules, des robots terrestres ou des drones. Dans un réseau de tels équipements, l'ensemble des liens de communication qui existe à un instant donné dépend des distances entre les entités et la topologie du réseau change continuellement lorsque les entités se déplacent. Les hypothèses habituelles sur la connexité du réseau n'ont pas leur place ici, néanmoins, une autre forme de connexité appelée connexité temporelle est souvent disponible à travers le temps et l'espace. L'objectif de cette thèse a été de développer des algorithmes pour les flottes d'appareils dans le cas des réseaux tolérant aux délais (DTN). De manière simplifiée, les réseaux tolérants aux délais sont des réseaux pour lesquels certaines parties peuvent se retrouver isolées pendant un moment sans que cela pose problème. Nous nous intéressons, en particulier, au cas où ces appareils sont organisés sous la forme de groupes, et où la notion de groupe elle même survit à ces déconnexions transitoires. Ainsi, une grande partie de la thèse s'articule autour de la notion des groupes tolérant aux délais (groupe DTN). Dans notre cas cet éloignement est limité dans le temps et nous parlons alors de "diamètre temporel borné" au sein du groupe. Le fait de borner le diamètre temporel du groupe lui permet de distinguer entre l'éloignement temporaire d'un noeud et sa perte définitive (crash ou autre). / Among the major developments in computer science, we distinguish the emergence of mobile wireless technologies. The current development of these technologies allows for direct ad-hoc communications between many types of mobile entities, such as vehicles, land robots or drones. In a network of such devices, the set of communication links that exists at a given instant depends upon the distances between the entities. As a result, the topology of the network changes continuously as the entities move. The common assumption on connectivity may not be relevant in this case, but another kind of connectivity called temporal connectivity is often alvailable over time and space. The goal of this thesis has been the development of algorithms for fleets of mobile devices in the case of delay-tolerant networks. In a simpler way, the delay-tolerant networks are networks where some parts can be isolated during a certain time without problems. We are interested, in particular, in the case where the devices are organised as groups, and where the notion of group itself survives to these deconnections. Hence, a big part of this thesis relates to the notion of delay-tolerant groups (DTN groups). In our case, these deconnections are limited in time and we speak of a "bounded temporal diameter" within the group. The fact of limiting the temporal diameter of the group enables it to distinguish between temporary deconnections and final loss (crash or other) of some nodes.