Grafos

GRAFOS
1. La matriz de adyacencia del grafo G es

1

1
1

0


1
1
0
1

1
0
1
1

0

1
1

1


entonces,
A) G es un pseudografo
B) G es un grafo completo
A) G no es conexo
Solución: Supongamos V={v1,v2,v3,v4} son los
vértices del grafo. En los pseudografo están
permitidas las aristas cuyos extremos coinciden, es
decir, los lazos.
En la matriz deadyacencia dada se observa que
m11=1, un lazo en v1
m22=1, un lazo en v2
m33=1, un lazo en v3
m44=1, un lazo en v4
Se trata de un pseudografo.
Sea A la matriz de adyacencia de un multigrafo
G con vértices {v1, v2,...,vn} y sea a23=3 una de
las entradas de A. Entonces,
A) Existe un camino con tres vértices entre v2 y
v3.
B) Hay tres aristas con extremos los vértices
v2 y v3.
C) Hay tresvértices adyacentes con v2 y v3
Solución: en los multigrafos se define la matriz de
adyacencia:
aij=número de aristas cuyos vértices son vi y vj, i≠j
aii=0
Por tanto si a23=3 entonces hay 3 aristas con
vértices extremos v2 y v3

Vemos que se trata de un ciclo hamiltoniano.
Ciclo es un camino cerrado donde los únicos
vértices repetidos son el primero y el último
Cuando un ciclo contienetodos los vértices del
grafo se llama ciclo hamiltoniano.
Nuestro grafo contiene siete vértices, y el camino
en cuestión los recorre todos sin repetir vértice, es
por tanto ciclo hamiltoniano.
4. Dado el grafo de la figura

A) Es hamiltoniano
B) Es euleriano
3. Es bipartito
Solución: el subgrafo de la figura siguiente
contiene un ciclo hamiltoniano

2.

Sea G un grafo con 7 vértices yC=(v1,v3,v2,v4,v5,v7,v6,v1) un camino en G.
A) C es un camino hamiltoniano
2. C es un ciclo
hamiltoniano
C) C no está bien definido
Solución: dibujando el subgrafo asociado al
v1
camino
v2
v7
3.

v3

v6
v5

v4

Un grafo que contiene un ciclo hamiltoniano se
denomina grafo hamiltoniano.
No es euleriano porque hay seis vértices que tienen
grado 3, es decir grado impar.Recuérdese que si
un grafo es euleriano todo vértice tiene grado par.
No es bipartito porque el ciclo asociado a la figura
anterior es de longitud impar.
Sea G un grafo conexo cuyos vértices son {v1,
v2, v3, v4, v5}. La sucesión (v1,v2,v3,v5,v1,) es:
A) Un camino euleriano
B) Un ciclo hamiltoniano
C) Ninguno de los anteriores
Solución: el subgrafo
v1
asociado al camino es el de la
v2
figura.Un camino euleriano es un
v3
camino que contiene todas las
aristas apareciendo cada una
v4
v5
de ellas exactamente una vez.
En nuestro caso
desconocemos todas las aristas del grafo, no
podemos asegurar que sea euleriano.
5.

Tampoco es un ciclo hamiltoniano, puesto que debe
pasar por todos los vértices sin repetir repetir
ninguno.

8. Dadas las matrices de adyacencia A, B y C detres grafos

0

1
A= 
0

0


Ambos mapas se pueden colorear con dos colores.
Entendiendo que “caras” se refiere a “regiones”,
el grado de las regiones internas es 3 y 4
respectivamente.
Si un mapa se puede colorear con dos colores,
regiones adyacentes tendrán asociados colores
diferentes; manteniendo la misma coloración para
las regiones que para las aristas asociadaspor la
transformación dual, las aristas conectaran
vértices que provienen de regiones adyacentes y
por tanto tendrán distintos colores.
7. Dado el digrafo etiquetado

1
0
1
1

1
1
0
1

0

1
1

1


1

1
1

0


1
0
0
0

1

0
;
1

0


1
0
0
1

A) A y B son isomorfos
B) A y C son isomorfos
C) B y C son isomorfos
Solución: elgrado de un vértice se obtiene
sumando los elementos de la fila.
Matriz A: gr(v1)=1; gr(v2)=3; gr(v3)=2; gr(v4)=2
Matriz B: gr(v1)=3; gr(v2)=1; gr(v3)=2; gr(v4)=2
Matriz C: gr(v1)=3; gr(v2)=3; gr(v3)=3; gr(v4)=3
No se puede establecer un isomorfismo entre A y C,
ni entre B y C, puesto que no se pueden hacer
corresponder los grados de los vértices.
Entre A y B se puede establecer el...