CBL - Campus del Baix Llobregat

Projecte llegit

Títol: Diàmetre unilateral en digrafs de doble pas


Estudiants que han llegit aquest projecte:


Director/a: DALFO SIMÓ, CRISTINA

Departament: MAT

Títol: Diàmetre unilateral en digrafs de doble pas

Data inici oferta: 01-02-2012     Data finalització oferta: 01-08-2012



Estudis d'assignació del projecte:
    Tipus: Individual
     
    Lloc de realització: EETAC
     
    Paraules clau:
    Digrafs, diàmetre, xarxes, problema (Delta,N), problema (Delta,D)
     
    Descripció del contingut i pla d'activitats:
    En termes generals, l'objectiu d'aquest treball és estudiar el diàmetre unilateral
    en els problemes (Delta,D) i (Delta,N) per al cas de digrafs de doble pas. Un digraf és
    una xarxa constituïda per vèrtexs i per arestes amb direcció (anomenades
    arcs). En el cas de grafs les arestes no tenen direcció. Un digraf de doble pas
    consta de N vèrtexs i un conjunt d'arcs de la forma (i,i+a) i (i,i+b), amb a i b
    enters positius anomenats "passos", és a dir, que existeixen enllaços des del
    vèrtex i cap els vèrtexs i+a i i+b (les operacions s'han d'entendre sempre
    mòdul N). Aquest digraf es denota G(N;a,b). El diàmetre d'un graf és la mínima distància
    possible que hi ha entre dos dels vèrtexs més
    allunyats entre si. En el diàmetre d'un digraf hem de tenir en compte que els arcs tenen direcció. El diàmetre unilateral d'un digraf és el mínim entre el
    diàmetre (amb direccions) del digraf i el diàmetre (amb direccions) del seu
    digraf convers (obtingut canviant totes les direccions dels arcs).

    El problemes (Delta,D) i (Delta,N) han estat molt estudiats en grafs i en digrafs, però
    no en el cas dels digrafs de doble pas considerant el diàmetre unilateral. En el
    nostre context, el primer problema consisteix a trobar el màxim nombre de
    vèrtexs N per a un diàmetre unilateral D^* i el grau Delta=2 donats, és a dir, trobar quins són els dos
    passos d'un digraf de doble pas que fan que el nombre de vèrtexs N sigui màxim per a aquests diàmetre unilateral i grau.
    El segon problema consisteix a trobar el mínim diàmetre unilateral D^* en
    digrafs de doble pas per a un nombre de vèrtexs N i el grau Delta=2 donats, és a dir, trobar quins
    són els dos passos d'un digraf de doble pas que fan que el diàmetre unilateral D^* sigui
    mínim per a aquests nombre de vèrtexs i grau.
     
    Overview (resum en anglès):
    The main objective of this research work is to study the unilateral diameter in
    the (Delta,D) and (Delta,N) problems for double-step digraphs. A digraph is a network
    consisting of vertices and directed edges (called arcs). In the case of a graph,
    edges have no direction. A double-step digraph consists in a set of N vertices
    and arcs of the forms (i,i+a) and (i,i+b), with and a and b positive integers called
    "steps", that is, there exist arcs from the vertex i to the vertices i+a and i+b
    (all the operations are modulo N). This digraph is denoted by G(N;a,b). The
    diameter of a graph is the shortest path between two of the farthest vertices. In
    the diameter of a digraph, we must consider that the edges have directions.
    The unilateral diameter of a digraph is the minimum between the diameter (with
    directions) of the digraph and the diameter (with directions) of its converse
    digraph (obtained by changing the directions of all arcs).

    The (Delta,D) and (Delta,N) problems have been extensively studied for graphs and
    digraphs, but not in the case of double-step digraphs considering the unilateral
    diameter. In our context, the first problem is to find the maximum number of
    vertices N given an unilateral diameter D^*
    and a degree Delta=2, that is, to find out
    the two steps of a double-step digraph that maximize the number of vertices
    for these unilateral diameter and degree. The second problem is to find the
    minimum unilateral diameter D^*
    for a double-step digraph given a number of
    vertices N and a degree Delta=2, namely, to find out the two steps of a double-
    step digraph that minimize the unilateral diameter D^* for these number of vertices and degree.


    © CBLTIC Campus del Baix Llobregat - UPC