introducción a la teoría de grafos

REPUBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL
POLITECNICA DE LA FUERZA ARMADA
NUCLEO ZULIA
CATEDRA: TEORIA DE GRAFOSPROFESOR: PEREZ ANGEL

TEORIA DE GRAFOS

3.1 GRAFOS

1

EQUIPO IV
• Johnny Delgado
• Yordany Pírela

Puntos relevantes de la exposición

grafos
Partes
propiedades
tipos
ejemplosHISTORIA DE LA TEORIA DE GRAFOS
El origen de la teoría de grafos se remonta al siglo
XVIII con el problema de los puentes de
Königsberg, el cual consistía en encontrar un
camino que recorriera los sietepuentes del río
Pregel ( en la ciudad de Königsberg, de modo que
se recorrieran todos los puentes pasando una sola
vez por cada uno de ellos. El trabajo de Leonhard
Euler para la resolución deese problema dio
origen a la teoría de grafos.

El problema de los puentes que dio paso a los grafos
Euler determinó, en el contexto del problema,
que los puntos intermedios de un recorridoposible necesariamente han de estar
conectados a un número par de líneas

introducción a la TEORIA DE GRAFOS

GRAFOS:

es un conjunto de objetos llamados
vértices o nodos unidos por enlacesllamados aristas o arcos, que
permiten representar relaciones
binarias entre elementos de un
conjunto. Son objeto de estudio de
la teoría de grafos.
Ejemplo de un grafo

partes que componen ungrafo

Vértices
vértice es un punto en una
figura geométrica donde se
interceptan las aristas.

Aristas
una arista corresponde a
una relación entre dos
vértices

ejemplo

Partes quecomponen un grafo

Grado de un vértice
En Teoría de grafos, el grado o valencia de
un vértice es el número de aristas
incidentes al vértice.

Ejemplos

partes que componen un grafo

lazo
Es unaarista cuyos extremos
inciden sobre el mismo vértice

ejemplo

Lado paralelo
Dos aristas son paralelas si
tienen los mismos vértices
en común o inciden sobre
los mismos vértices.

ejemplo...