Identifier: TDX:2216
Authors: Estrada Moreno, Alejandro
Abstract:
En aquesta tesi s'estudia la dimensió (k,t)-mètrica dels grafs. Particularment s'emfatitza en la dimensió k-mètrica i la dimensió de k-adjacència. Al primer capítol es dedica als conceptes bàsics i les notacions emprades a la tesi. Al segon capítol es determina el més gran enter k, de manera que hi ha una base (k,t) -mètrica d'un graf. Es mostra, a més, que la complexitat temporal de calcular aquest valor de k és cúbica, pel que fa a l'ordre del graf. Al tercer capítol, s'obtenen fórmules tancades i cotes per a la dimensió (k,t) -mètrica d'alguns grafs. Així mateix, es delimita el valor de la dimensió k-mètrica en funció de paràmetres relacionats amb la distància, i es descriuen les classes de grafs en què s’aconsegueixen aquestes cotes com, per exemple, en els arbres. En particular, per a aquests últims, s'estableix una fórmula per calcular la dimensió k-mètrica de qualsevol arbre. També s'estudia la dimensió de k-adjacència de diversos grafs perquè s'ha trobat una forta relació entre la dimensió k-mètrica de productes de grafs i la dimensió de k-adjacència d'un dels seus factors. Aquesta relació permet obtenir nombrosos resultats per al producte lexicogràfic i per al producte corona. A l'últim capítol, es demostra que trobar el més gran enter k, de manera que hi hagi una base (k,t) –mètrica d’un graf, es pot resoldre en temps cúbic pel que fa a l'ordre del graf. Es prova, a més, que el problema de calcular la dimensió és NP-complex a través d'una transformació polinòmica al 3-SAT. Malgrat tot, per la fórmula obtinguda per a la dimensió k-mètrica d’arbres (que es demostra al capítol 3), es proposa un algoritme que es pot resoldre en temps lineal per determinar la dimensió k-mètrica i una base k-mètrica de qualsevol arbre.
Repositori URV