Scribd
Cargar
16 vistas4 páginas

Guia 2

El documento presenta un análisis de grafos, incluyendo aplicaciones de incidencia y grados de vértices. Se discute la imposibilidad de que un grafo simple con 15 vértices tenga grado 5 en cada vértice debido a la suma impar de los grados. Además, se evalúan diferentes pares de grafos para determinar si son isomorfos, concluyendo que no lo son debido a diferencias en la adyacencia de los vértices.

Cargado por

Danny Josue Lopez Reyes
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
16 vistas4 páginas

Guia 2

El documento presenta un análisis de grafos, incluyendo aplicaciones de incidencia y grados de vértices. Se discute la imposibilidad de que un grafo simple con 15 vértices tenga grado 5 en cada vértice debido a la suma impar de los grados. Además, se evalúan diferentes pares de grafos para determinar si son isomorfos, concluyendo que no lo son debido a diferencias en la adyacencia de los vértices.

Cargado por

Danny Josue Lopez Reyes
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

a)

V={A,B,C,D}

A={1,2,3,4,5,6,7}

Aplicación de incidencia

1=(A,A)

2=(A,B)
A B C D
3=(A,D) 1 2 0 0 0
2 1 1 0 0
4=(B,C) 3 1 0 0 1
5=(C,A) 4 0 1 1 0
5 1 0 1 0
6=(D,B) 6 0 1 0 1
7 0 0 1 1
7=(D,C)

Grados

Grado de A=5

Grado de B=3

Grado de C=3

Grado de D=3
b)

V={A,B,C,D}

A={1,2,3,4,5,6,7}

Aplicación de incidencia

1=(A,A)

2=(A,B)

3=(A,D)

4=(B,C)

5=(C,A)

6=(D,B)

7=(D,C)
A B C D
1 2 0 0 0
2 1 1 0 0
Grados
3 0 1 1 0
Grado de A=4 4 1 0 1 0
5 0 0 2 0
Grado de B=3 6 0 0 1 1
Grado de C=5 7 0 1 0 1

Grado de D=2

No, no es posible que un grafo simple con 15 vértices tenga grado 5 en cada vértice, ya que la suma de los grados no es
un número par, lo cual impide que el número de aristas sea un número entero.
A)

B)
a) tienen la misma secuencia de grados l,l,l,l,2,2,3,3
R// vl tiene grado l, su homólogo tiene que ser un vértice con grado l. Vl es adyacente a un vértice con grado 2, su
homólogo tiene que ser adyacente a un vértice con grado 2. En el segundo grafo ninguno de los cuatro vértices de
grado l es adyacente a vértices de grado 2, todos los son a un vértice de grado 3. No pueden ser isomorfos

b) Ambos grafos tienen la misma secuencia de grados:

1, 1, 2, 2, 2, 3

R// Un vértice tiene grado 1, por lo que su homólogo debe ser un vértice con grado 1. En el Grafo 1, vi está
adyacente a un vértice con grado 2, por lo que su homólogo en el segundo grafo debe estar adyacente a un vértice
con grado 2. Sin embargo, en el Grafo 2, ninguno de los vértices con grado 1 está adyacente a vértices de grado 2;
todos están adyacentes a vértices con grado 3.

Por lo tanto, los grafos no pueden ser isomorfos.

c) Ambos grafos tienen la misma secuencia de grados:

R// Un vértice tiene grado 2, por lo que su homólogo debe ser un vértice con grado 2. En el Grafo 1, está adyacente
a un vértice con grado 3, por lo que su homólogo en el segundo grafo debe estar adyacente a un vértice con grado
3. Sin embargo, en el Grafo 2, los vértices con grado 2 tienen una distribución de conexiones diferente.

Por lo tanto, los grafos no pueden ser isomorfos.

d) Ambos grafos tienen la misma secuencia de grados:

2, 2, 3, 3, 3, 3

R// Un vértice tiene grado 2, por lo que su homólogo debe ser un vértice con grado 2. En el Grafo 1, vi está
adyacente a dos vértices con grado 3, por lo que su homólogo en el segundo grafo también debe estar adyacente a
dos vértices con grado 3. Sin embargo, en el Grafo 2, los vértices con grado 2 tienen una estructura de adyacencia
diferente.

Por lo tanto, los grafos no pueden ser isomorfos.

También podría gustarte