Paràmetres relacionats amb la seqüència iterada de digrafs excèntrics

Abstract

La memòria que es presenta s'emmarca dins de l'àrea de la teoria de grafs. En concret el projecte es basa en la implementació i estudi de la seqüència iterada de l'operador digraf excèntric, així com els diferents paràmetres relacionats amb aquesta seqüència: Donat un digraf G, el seu digraf excèntric ED(G) és aquell que te'ls mateixos vèrtexs que G i on hi ha un arc d'un vèrtex u a un vèrtex v si, i només si, v és un vèrtex excèntric de u (és a dir, v és el vèrtex més allunyat de u a G). La seqüència de digrafs G;ED(G);ED2(G); ··· ;EDk(G); ··· on EDk(G) = ED(EDk-1(G)) resulta ser finita i es defineixen la cua t i el període p de la seqüència com els enters positius més petits pels quals EDt(G) = EDt+p(G). Anàlogament es defineixen la isocua t' i el isoperíode p' com els enters positius més petits tals que EDt'(G) ' EDt'+p'(G), on ' denota l'isomorfisme de digrafs. Hi ha diversos problemes oberts envers aquesta temàtica. Es marca com objectius: implementar en Python les eines necessàries per obtenir la seqüència iterada de digrafs excèntrics, calcular la seqüència iterada de tots els digrafs d'ordres petits i calcular els paràmetres associats a aquesta seqüència i donar resultats per a l'estudi d'algunes qüestions obertes.