Certificado

GRAFOS


1. La matriz de adyacencia del grafo G es
[pic]
entonces,

G es un pseudografo

A) G es un grafo completo

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 de adyacencia dada se observa que
m11=1, un lazo en v1
m22=1, un lazoen v2
m33=1, un lazo en v3
m44=1, un lazo en v4
Se trata de un pseudografo.


2. 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 tres vértices adyacentes con v2 y v3
Solución: en los multigrafos sedefine 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


3. Sea G un grafo con 7 vértices y C=(v1,v3,v2,v4,v5,v7,v6,v1) un camino en G.
A) C es un camino hamiltoniano

C es un ciclo hamiltoniano

B) C no está bien definido
Solución: dibujando el subgrafo asociado al caminoVemos 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 contiene todos 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








Eshamiltoniano

A) Es euleriano

Es bipartito

Solución: el subgrafo de la figura siguiente contiene un ciclo hamiltoniano






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 cicloasociado a la figura anterior es de longitud impar.

5. 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

Ninguno de los anteriores

Solución: el subgrafo asociado al camino es el de la figura.
Un camino euleriano es un camino que contiene todas las aristas apareciendo cada una de ellasexactamente una vez.
En nuestro caso desconocemos todas las aristas del grafo, no podemos asegurar que sea euleriano.
Tampoco es un ciclo hamiltoniano, puesto que debe pasar por todos los vértices sin repetir repetir ninguno.

6. Sea M un mapa cuyas regiones se pueden colorear con sólo dos colores:

El pseudomultigrafo dual es bipartito

A) Todas las caras son polígonos con un número par delados.
B) No existen tales mapas.
Solución: veamos dos ejemplos de tales mapas





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 quepara las aristas asociadas por 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









¿Cuál es la distancia entre x e y?
A) ( B) 5 C)12
Solución: siguiendo el algoritmo de Dijkstra y colocando en cada vértice la distancia desde x, obtenemos:











8. Dadas las matrices deadyacencia A, B y C de tres grafos
[pic]
A) A y B son isomorfos
B) A y C son isomorfos

B y C son isomorfos

Solución: el grado 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...