TEORA DE GRAFOS

(Cdigo SAC 16887)

TERICO PRCTICO

EVALUACIN A DISTANCIA 1-2015

Nombre: ________________________________ Cdula: ______________ CAU:__________

INTRODUCCIN

La teora de grafos, enmarcada dentro de la rama de las matemticas discretas, es una

disciplina encargada del estudio de objetos discretos, es decir, finitos, o en caso de que no lo

sea son elementos bien separados entre s.

La matemtica discreta es la parte de las matemticas ms cercana a los ordenadores, tiene

una relacin bidireccional con ellos: los ordenadores son discretos

La teora de grafos surge en 1736, cuando Leonhard Euler, considerado su padre, publica un

artculo, resolviendo un caso conocido como los puentes de Kningsberg, donde se discute si

es posible o no dar un paseo por Kninsberg cruzando exactamente una vez cada uno de los

siete puentes que unen a sus dos islas.

Dentro de las aplicaciones ms comunes de la teora de grafos se encuentran: problemas rutas

entre ciudades, determinar tiempos mximos y mnimos de un proceso y flujo y control en un

programa

La teora de grafos juega un papel importante en la fundamentacin matemtica de las ciencias

de la computacin, los grafos constituyen una herramienta bsica para modelar fenmenos

discretos y son fundamentales para la comprensin de la estructura de datos y anlisis de

algoritmos.

OBJETIVO DE LA EVALUACIN

Comprender los conceptos de la teora de grafos, as como sus teoremas y aplicaciones de

mayor relevancia a fin de dar uso de esta herramienta en contextos prcticos haciendo uso de

las ventajas que conlleva el representar mediante un grafo determinados sistemas.

VALORACIN DEL ESPACIO ACADMICO

Acorde con el Reglamento Estudiantil de la VUAD en su Artculo 30. Naturaleza de las

Asignaturas: En los programas de la VUAD, la naturaleza de las asignaturas est determinada

por el nivel de conceptualizacin, contextualizacin y aplicacin del dominio del conocimiento

de acuerdo con el rea disciplinar a la que pertenezca. As:

Asignaturas Terico-Prcticas, son aquellas que por su dominio de conocimiento requieren

un desarrollo equitativo en sus niveles de conceptualizacin contextualizacin y aplicacin.

UNIVERSIDAD SANTO TOMS VICERRECTORIA GENERAL DE UNIVERSIDAD ABIERTA Y A DISTANCIA

FACULTAD DE CIENCIAS Y TECNOLOGIAS

Pgina 2 de EVALUACIN DISTANCIA 1-2015 Ingeniera en informtica

2

Artculo 33. Evaluacin total de las asignaturas: En los programas de la Facultad de

Ciencias y Tecnologas la evaluacin total de una asignatura se obtendr de la siguiente

manera:

Asignaturas Terico-Prcticas: Tendrn evaluacin presencial o virtual con un valor del 50%, evaluacin distancia que tiene un valor del 25% y evaluacin prctica que tiene un valor del 25%.

ACTIVIDADES A DESARROLLAR

1. Dadas las siguientes proposiciones, determine la veracidad o falsedad de cada una,

justifique su respuesta.

a. Todo grafo de Euler es un grafo simple

b. Todo grafo simple es un grafo de Euler

c. Todo grafo de Euler puede ser cubierto por un ciclo

d. Todo grafo de Euler puede ser cubierto por un ciclo simple

e. Todo grafo bipartito completo es un grafo de Euler

f. Todo grafo cuya suma de las grados de sus vrtices es par, es un grafo de Euler

g. Todo subgrafo de Euler es un grafo de Euler

h. Si es un grafo de Euler, entonces es un grafo semi-Euleriano

i. Si es semi-Euleriano es un grafo de Euler

j. Sean y dos subgrafos de un grafo . Si y son grafos de Euler, entonces

es un grafo de Euler

k. Sean y dos subgrafos de un grafo . Si y son grafos de Euler con

entonces es un grafo de Euler

Si es un grafo de Euler, el grafo que resulta de la fusin de dos vrtices cualquiera de sus

vrtices es un grafo de Euler

2. Justifique la veracidad o falsedad de cada una de las siguientes proposiciones:

a. Si un dgrafo es hamiltoniano entonces es fuertemente conexo

b. Si un dgrafo es fuertemente conexo es hamiltoniano

c. Si un dgrafo es hamiltoniano entonces es semi-hamiltoniano

d. Sin un dgrafo es conexo-hamiltoniano, entonces es semi-hamiltoniano

e. Si un dgrafo es conexo-hamiltoniano, entonces es fuertemente conexo.

3. Dadas las siguientes proposiciones, justifique la veracidad o falsedad de cada una de ellas

a. En todo grafo el nmero de vrtices de grado par puede ser impar

b. En todo grafo el nmero de vrtices de grado impar no siempre es par

c. En todo grafo el nmero de vrtices pendientes es par

Pgina 3 de EVALUACIN DISTANCIA 1-2015 Ingeniera en informtica

3

d. Un grafo simple con puede poseer un vrtice de grado

e. En todo grado la suma de los grados de los vrtices de grado impar es un nmero par

4. Construir, siempre que sea posible, el grafo que se pide, de no ser posible, justifique su

respuesta:

a. Un grafo y para todo

b. Un grafo simple con 5 vrtices, tal que todos sus vrtices posean un grado impar.

c. Un grafo simple , 4-regular

d. Un grafo 4-regular con 15 aristas

e. Un grafo simple con 7 vrtices, tal que todos sus vrtices tengan grado 4.

5. Realice el grafico que corresponde a la siguiente matriz de incidencia:

a b c d e

1 1 0 1 0 0 2 0 1 0 1 0 3 0 1 1 0 1 4 1 0 0 1 1

Donde, y