grafo




TALLER TEORÍA DE GRAFOS








1. Del grafo A obtener un subgrafo maximal y determinar:


A

a. Todos los ciclos simples de longitud mayor que 5.
b. El ciclo de mayorlongitud del subgrafo.
c. Un subgrafo del subgrafo maximal y hallar la excentricidad de los vértices.

Solución:

Del grafo A se toman los vértices v1, v2, v3, v4, v5, v6 y v11, a partir de ellos seobtiene el siguiente subgrafo maximal.

P

a. Los ciclos encontrados con longitud mayor a 5 son:
CIS1= V3 a18 V6 a22V4a23V5a13V2a8V11a14V3 L(CIS1)= 6
CIS 2= V3a18V6a28V11a8V2a13V5a4V1a6V3L(CIS2)= 6
CIS 3= V3a18V6a28V11a8V2a13V5a23V4a5V1a6V3 L(CIS3)= 7
CIS 4=V3a14V11a28V6a22V4a23V5a4V1a6V3 L(CIS4)= 6
CIS 5= V3a14V11a8V2a13V5a23V4a5V1a6V3 L(CIS5)= 6
CIS6=V2a8V11a14V3a18V6a22V4a23V5a13V2 L(CIS6)= 6
CIS 7= V2a13V5a4V1a6V3a18V6a28V11a8V2 L(CIS7)= 6
CIS 8= V2a13V5a23V4a5V1a6V3a18V6a28V11a8V2 L(CIS8)= 7
CIS 9= V2a13V5a23V4a5V1a6V3a14V11a8V2 L(CIS9)= 6
CIS 10=V4a23V5a13V2a8V11a14V3a18V6a22V4 L(CIS10)= 6
CIS 11= V4a5V1a6V3a18V6a28V11a8V2a13V5a23V4 L(CIS11)= 7
CIS 12= V4a23V5a4V1a6V3a14V11a28V6a22V4 L(CIS12)= 6
CIS 13= V4a5V1a6V6a14V11a8V2a13V5a23V4L(CIS13)= 6
CIS 14= V4a23V5a13V2a8V11a14V3a6V1a5V4 L(CIS14)= 6
CIS 15= V5a13V2a8V11a14V3a18V6a22V4a23V5 L(CIS15)= 6
CIS 16= V5a4V1a6V3a18V6a28V11a8V2a13V5 L(CIS16)= 6
CIS 17=V5a23V4a5V1a6V3a18V6a28V11a8V2a13V5 L(CIS17)= 7
CIS 18= V5a4V1a6V3a14V11a28V6a22V4a23V5 L(CIS18)= 6
CIS 19= V5a23V4a5V1a6V3a14V11a8V2a13V5 L(CIS19)= 6
CIS 20= V5a13V2a8V11a14V3a6V1a5V4a23V5L(CIS20)= 6
CIS 21= V6a22V4a23V5a13V2a8V11a14V3a18V6 L(CIS21)= 6
CIS 22= V6a28V11a8V2a13V5a4V1a6V3a18V6 L(CIS22)= 6
CIS23= V6a28V11a8V2a13V5a23V4a5V1a6V3a18V6 L(CIS23)= 7
CIS24=V6a22V4a23V5a4V1a6V3a14V11a28V6 L(CIS24)= 6
CIS25=V11a14V3a18V6a22V4a23V5a13V2a8V11 L(CIS25)= 6
CIS26= V11a8V2a13V5a4V1a6V3a18V6a28V11 L(CIS26)= 6
CIS 27= V11a8V2a13V5a23V4a5V1a6V3a18V6a28V11 L(CIS27)= 7...