Grafos

Multigrafos. Pseudografos. Grafos isomorfos. Mapas. Matriz de adyacencia

  • Enviado por: El remitente no desea revelar su nombre
  • Idioma: castellano
  • País: España España
  • 2 páginas
publicidad
publicidad

Sea M el mapa de la figura Grafos

1.

M se puede colorear con tres colores diferentes

2.

M necesita cuatro colores para ser coloreado

3.

Son necesarios más de cuatro colores para colorear M

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,

1.

Existe un camino con tres vértices entre v2 y v3

2.

Hay tres aristas con extremos los vértices v2 y v3

3.

Hay tres vértices adyacentes con v2 y v3

Dado el grafo Grafos

1.

Es hamiltoniano

2.

Es euleriano

3.

Es bipartito

¿Cuál de las siguientes afirmaciones es correcta?

1.

Un grafo es bipartito si y sólo si no tiene ciclos de longitud impar

2.

Un grafo es bipartito si y sólo si tiene un número par de vértices

3.

Un grafo es bipartito si y sólo es un grafo completo con un número par de vértices

Grafos

1.

Es plano

3.

Es completo

2.

No es plano

Dado el grafo G con matriz de adyacencia: Grafos
, entonces:

1.

G es un grafo completo

2.

G no es conexo

3.

G es un pseudografo

Grafos

1.

Son isomorfos pues tienen el mismo número de aristas y de vértices

2.

Son isomorfos pues se puede establecer un isomorfismo entre ellos

3.

No son isomorfos

Sea G un grafo y M un mapa que representa a G. Supongamos que el grado de todos los vértices de G es 4 y que G tiene 12 aristas. Entonces el número de regiones de M es:

1.

12

2

9

3

10

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

1.

El pseudografo dual es bipartito

2.

Todas las caras son polígonos con un número par de lados

3.

No existen tales mapas

Grafos

se aplica el algoritmo de Dijkstra partiendo del vértice s. Se designa por d(s,w) la distancia entre s y cualquier otro vértice w. ¿Cuál de los siguientes resultados es cierto?

1.

d(s,a)=18, d(s,b)=27, d(s,c)=15, d(s,d)=22, d(s,t)=55

2.

d(s,a)=18, d(s,b)=27, d(s,c)=15, d(s,d)=22, d(s,t)=57

3.

d(s,a)=18, d(s,b)=29, d(s,c)=15, d(s,d)=22, d(s,t)=57

Sea M la matriz de adyacencia de un grafo G con p>1 vértices. Sea C=Mp-1+Mp-2+M.

1.

Si C tiene alguna entrada no nula, entonces el grafo es conexo.

2.

Si la entrada (i,j) de C es igual a 1, entonces existe una arista entre el vértice i y el vértice j

3.

Si el grafo es conexo, entonces todas las entradas de C son no nulas

Sea Kr el grafo completo de r vértices, (r>2). Entonces su matriz de adyacencia es:

1.

aii=1, aij=1 (i distinto de j)

2.

aii=1, aij=0 (i distinto de j)

3.

aii=0, aij=1 (i distinto de j)

Sea G un grafo con matriz de adyacencia A. ¿Cuál de las siguientes informaciones dan los elementos de la diagonal principal de A2?

1.

Los grados de los vértices de G

2.

Los ciclos con a lo más dos aristas

3.

Ninguna de las anteriores

Sea K6 el grafo completo de 6 vértices. Entonces:

1.

Es bipartito ya que tiene un número par de vértices

2.

Es hamiltoniano

3.

Es euleriano

Sea G un grafo y M un mapa con r regiones que representa a G. Si el grado de todos los vértices es 5 y G tiene 20 aristas, entonces r es:

1.

12

2.

14

3.

18

¿Cuál es el número de veces que se debe levantar el lápiz para dibujar la figura sin repetir ninguna arista? 1- ninguna 2- una 3-dos
Grafos

GRAFOS

Sea G un grafo con siete vértices y C={v1,v3,v2, v4,v5,v7,v6,v1} un camino en G. Entonces:

1.

C es un camino euleriano

2.

C es un ciclo hamiltoniano

3.

C no está bien definido

¿Cuál de las siguientes afirmaciones es falsa?

1.

Todo grafo tiene un número de vértices de grado par

2.

Todo grafo tiene un número par o cero de vértices de grado impar

3.

la suma de los grados de los vértices de un grafo es par

Sea G el grafo formado por los vértices y aristas de un tetraedro T más el centro de T y las aristas que unen dicho centro con los vértices de T. Entonces:

1.

G es bipartito

2.

G es euleriano

3.

G no es hamiltoniano

En el grafo de la figura sea L(vi ) la longitud del camino más corto entre los vértices u y vi .

Grafos
Entonces

1.

L(v4) = 6   y   L(v2

2.

L(v3) = 2   y   L(v4  ) = 3

3.

L(v3) = 3   y   L(v4  ) = 4