2024-03-29T11:58:51Zhttps://www.tdx.cat/oai/requestoai:www.tdx.cat:10803/58492020-05-19T10:04:27Zcom_10803_183col_10803_185
nam a 5i 4500
Vectors propis
Valors propis
Espectre
Digraf
Digraf de Cayley
Digraf línia
Difusió
Estudi i disseny de grans xarxes d'interconnexió: modularitat i comunicació
[Barcelona] :
Universitat Politècnica de Catalunya,
2011
Accés lliure
http://hdl.handle.net/10803/5849
cr |||||||||||
AAMMDDs2011 sp ||||fsm||||0|| 0 cat|c
9788469120569
Dalfó Simó, Cristina,
autor
Tesi
Doctorat
Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística
2007
Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística
Tesis i dissertacions electròniques
Comellas Padró, Francesc, ,
1954-
supervisor acadèmic
Fiol Mora, Miguel Ángel,
supervisor acadèmic
TDX
Normalment les grans xarxes d'interconnexió o de comunicacions estan dissenyades utilitzant tècniques de la teoria de grafs. Aquest treball presenta algunes contribucions a aquest tema. Concretament, presentem dues noves operacions: el "producte Jeràrquic" de grafs i el "producte Manhattan" de digrafs. El primer és una generalització del producte cartesià de grafs i ens permet construir algunes famílies amb un alt grau de jerarquia, com l'arbre binomial, que és una estructura de dades molt utilitzada en algorísmica. El segon dóna lloc a les conegudes Manhattan Street Networks, les quals han estat extensament estudiades i utilitzades per modelar algunes classes de xarxes òptiques. En el nostre treball, definim formalment i analitzem el cas multidimensional d'aquestes xarxes. Estudiem algunes propietats dels grafs o digrafs obtinguts mitjançant les dues operacions esmentades, especialment: els paràmetres estructurals (les propietats de l'operació, els subdigrafs induïts, la distribució de graus i l'estructura de digraf línia), els paràmetres mètrics (el diàmetre, el radi i la distància mitjana), la simetria (els grups d'automorfismes i els digrafs de Cayley), l'estructura de cicles (els cicles hamiltonians i la descomposició en cicles hamiltonians arc-disjunts) i les propietats espectrals (els valors i vectors propis). En el darrer cas, hem trobat, per exemple, que la família dels arbres binomials tenen tots els seus valors propis diferents, "omplint" tota la recta real. A més a més, mostrem la relació del seu conjunt de vectors propis amb els polinomis de Txebishev de segona espècie. També hem estudiat alguns protocols de comunicació, com els enrutaments locals i els algorismes de difusió. Finalment, presentem alguns models deterministes (com les xarxes Sierpinski i d'altres), els quals presenten algunes propietats pròpies de les xarxes complexes reals (com, per exemple, Internet).
p
ES-BaCBU
cat
rda
ES-BaCBU
text
txt
rdacontent
informàtic
c
rdamedia
recurs en línia
cr
rdacarrier