Projecte llegit
Títol: Diàmetre unilateral en digrafs de doble pas
Estudiants que han llegit aquest projecte:
- GOMIS GARCIA, MIREIA (data lectura: 29-06-2012)
- Cerca aquest projecte a Bibliotècnica
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. |