Anells cordals: propietats estructurals i models de comunicacions

• Autores: Lali Barrière
• Directores de la Tesis: Josep Fàbrega Canudas (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2007
• Idioma: catalán
• ISBN: 978-84-690-8972-9
• Depósito Legal: B.51288-2007
• Enlaces
  • Tesis en acceso abierto en: TDX
• Resumen

  • En els darrers anys hi ha hagut un gran desenvolupament de la recerca en làrea de les xarxes informàtiques. En aquest context, la utilització dels grafs com a models per a les xarxes, on els nodes són ordinadors o processadors interconnectats, que shan de comunicar entre ells de la manera més eficaç possible, ha donat lloc a gran quantitat de treballs. Quan es tracta de xarxes dinterconnexió, en què el nivell dintegració és elevat, es solen considerar models amb bones propietats de simetria, que permeten definir i analitzar els algorismes amb més facilitat. Per exemple, els grafs de Cayley són grafs definits a partir de loperació dun grup. Això permet utilitzar lestructura algèbrica subjacent per a la resolució dels problemes.

    Aquesta tesi tracta de les propietats duna família de grafs, els anells cordals de grau 3, que són grafs de Cayley sobre el grup de simetries dun polígon regular o grup dièdric. Aquest grup no és commutatiu, però els seus elements satisfan bones relacions. A més, està molt relacionat amb el grup cíclic, i això fa que els anells cordals tinguin molt a veure amb els grafs circulants.

    Una part important del treball és lestudi de les propietats estructurals dels anells cordals, mentre que en una segona part es donen algorismes de comunicació punt a punt, o encaminaments, amb bones propietats, i dintercanvi dinformació entre tots els nodes, o gossiping. Aquestes dues parts del treball estan interrelacionades, ja que les propietats estructurals dels grafs sutilitzen en les definicions i en lanàlisi dels algorismes que es proposen en la segona part i, a la vegada, lestudi de problemes de comunicacions ha motivat el plantejament de problemes de caire més teòric, com la classificació per isomorfisme dels anells cordals, la caracterització del seu grup dautomorfismes o el càlcul de laresta bisecció.

    Part de linterès daquest treball és lús de les tessel.lacions per a la representació dels grafs. Aquesta eina sha revelat molt útil en lestudi de propietats mètriques i de problemes en què shan destablir camins entre els nodes, ja que en facilita la visualització. Les altres famílies de grafs que han estat estudiades per diversos autors mitjançant tessel.lacions del pla són, sobretot, els grafs circulants de grau 4, en què sutilitzen quadrats per representar els vèrtexs, i de grau 6, en què sutilitzen hexàgons. Per als anells cordals de grau 3 shan utilitzat triangles. En particular es veu com la tessel.lació determina totalment el graf, i les propietats del graf es tradueixen en propietats de la tessel.lació.

    Es poden citar com a problemes oberts la generalització dels resultats a altres famílies de grafs, i lestudi daltres problemes de comunicacions. En particular, per al problema del càlcul de líndex òptic, es tenen alguns resultats en el cas danells cordals aresta transitius, que utilitzen la caracterització del grup dautomorfismes i la definició dencaminaments amb bones propietats presentats en aquesta tesi.