CBL - Campus del Baix Llobregat

Projecte llegit

Títol: El problema (Delta,N) en les xarxes Manhattan

Estudiants que han llegit aquest projecte:

Director/a: DALFO SIMÓ, CRISTINA

Departament: MAT

Títol: El problema (Delta,N) en les xarxes Manhattan

Data inici oferta: 18-04-2012     Data finalització oferta: 18-12-2012


Estudis d'assignació del projecte:
    Tipus: Conjunt     Nombre d'estudiants per realitzar-ho: 1-2
     
    Lloc de realització: EETAC
     
    Paraules clau:
    Grafs, digrafs, xarxes Manhattan, diàmetre, problema (Delta,D), problema (Delta,N)
     
    Descripció del contingut i pla d'activitats:
    En termes generals, l’objectiu d’aquest treball és estudiar el problema (Delta,N) (o problema grau-nombre de vèrtexs) per al cas del digraf Manhattan.

    Un digraf és una xarxa constituïda per vèrtexs i per arestes dirigides anomenades arcs (en el cas de grafs, les arestes no tenen direcció). 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ó.
    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). Un graf de doble pas G(N;+-a,+-b) també consta de N vèrtexs, però les arestes són de la forma (i,i+-a) i (i,i+-b), amb passos a i b (enters positius), per tant, existeixen enllaços des del vèrtex i cap els vèrtexs i+a, i-a, i+b i i-b (mod N).

    En un digraf Manhattan els arcs tenen les direccions com les dels carrers i les avingudes de Manhattan (o de l'Eixample de Barcelona), és a dir, si un arc va cap a la dreta, el "següent" va cap a l'esquerra i si un arc va cap a dalt, el "següent" va cap a baix.

    El problema (Delta,N) consisteix a trobar el diàmetre mínim d'un graf o digraf fixats el nombre de vèrtexs N i el grau màxim Delta. Com que aquest problema ha estat resolt per al cas de grafs de doble pas G(N;+-a,+-b), hem expandit aquests grafs transformant cada vèrtex en un cicle dirigit
    de 4 vèrtexs i cada aresta en dos arcs de sentits oposats, de manera que obtenim un digraf Manhattan.

    En aquest treball trobem la relació entre els passos del graf de doble pas G(N;+-a,+-b) i els del digraf Manhattan M. A més, hem fet un programa que calcula el diàmetre del digraf anomenat New Amsterdam NA, que està relacionat amb el Manhattan M, a partir dels paràmetres del graf original G(N;+-a,+-b).
     
    Overview (resum en anglès):
    Generally speaking, the aim of this work is to study the
    problem (Delta,N) (or the degree-number of vertices problem) for the case of a Manhattan digraph.

    A digraph is a network formed by vertices and directed edges called arcs (in the case of graphs the edges have no direction). The diameter of a graph is the minimum distance that exists between two of the farthest vertices. In the diameter of a digraph we must take into account that arcs have direction.

    A double-step digraph consists of N vertices and a set of arcs of the form (i,i+a) and (i,i+b), with a and b positive integers called ‘steps’, that is, there are connections from vertex i to vertices i+a and i+b (operations are modulo N). This digraph is denoted by
    G(N;a,b). A double-step graph G(N;+-a,+-b) consists of N vertices, but the edges are of the form (i,i+-a) and
    (i,i+-b), with steps a and b (positive integers), therefore, there are connections from vertex i to vertices i+a, i-a, i+b and i-b (mod N).

    In a Manhattan digraph, the arcs have directions like the ones of the streets and avenues of Manhattan (or l’Eixample in Barcelona), that is, if an arc goes to the right, the ‘next one’ goes to the left and if an arc goes upwards, the ‘next one’ goes downwards.

    The (Delta,N) problem consists in finding the minimum diameter of a graph or digraph given the number of vertices N and the maximum degree Delta. As this problem has been solved for the case of double-step graphs G(N;+-a,+-b), we expand these graphs transforming every vertex into a
    directed cycle of order 4 and every edge into two arcs in opposite directions, so that we obtain a Manhattan digraph M.

    In this work we find the relation between the steps of the double-step graph G(N;+-a,+-b) and the ones of the Manhattan digraph M. Moreover, we made a program that calculates the diameter of the so-called New Amsterdam digraph NA, related to the Manhattan digraph M, from the parameters of the original graph G(N;+-a,+-b).

    © CBLTIC Campus del Baix Llobregat - UPC