Grafo. Conjunto de objetos
unidos por vértices
o nodos, que
permiten
representar
relaciones binarias
entre elementos de
un conjunto
(Wikipedia, 2016)
Vértice. Los vértices son los dos
elementos que forman un grafo.
Aristas. Son las lineas con las que
se unen los vértices de un grafo,
los vértices a y b son los extremos.
(Uruguay)
Grafos completos. Para todo par de vértices de
G, existe por lo menos una arista que los une.
Por lo tanto, un grafo completo de n vértices es
aquel que tiene sus n vértices mutuamente
adyacentes. (Uruguay)
Pueden ser:
Grafo no dirigido. Cuando no
importa la dirección de una
arista, el grafo se denomina no
dirigido (Uruguay)
Grafo dirigido. Un grafo es
orientado, cuando sus
aristas tienen asignadas
direcciones, o sea cuando
existe una relación de
precedencia entre los
elementos (Uruguay)
En aquellas aplicaciones en las
que intervienen costos o
propiedades propias de la relación
entre los elementos del sistema,
estamos ante un Grafo
Ponderado: (Uruguay), las
ponderación son costos.
Grafo nulo. Aquel que
no tiene vértices ni
aristas
Camino. Un camino en un grafo es una
sucesión finita en la que aparecen
alternadamente vértices y aristas de dicho
grafo. (Blogspot, 2011)
»Longitud del Camino: Está dada por
número de aristas, parecido al
tamaño. (Blogspot, 2011)
Circuito. Es un camino que inicia y termina en el
mismo nodo, no se recorre dos veces por la
misma arista (Agalia, 2012).
Si todos los vértices tienen el mismo grado, el grafo al
que pertenecen se llama grafo regular. (Uruguay)
Ciclos de Euler y Hamilton “Hacer el
recorrido sin levantar el lápiz del
papel…”
Puentes de Königsberg El problema consiste en recorrer toda la ciudad
partiendo de cualquier lugar (A, B, C o D) caminando sobre cada puente
exactamente una vez y regresar a la posición inicial. ¿Es posible? 7 Puentes 2
Islas: B y C 2 Orillas: A y D. Euler ideó los grafos para ver si era posibleRecorrer
toda la ciudad sin cruzar c/u de los puentes más de una sola vez. (Agalia, 2012)
Camino de Euler. Ciclo Euleriano es aquel que incluye
todas las aristas del grafo una sola vez sin repetirse, conteniendo
cada vértice por lo menos una vez y se pueden repertir. (Uruguay)
Camino de Hamilton. Inicia y termina en el mismo
vértice, recorre TODOS los VÉRTICES sin repetirlos
(excepto el vértice del cual parte y al cual llega).
(Agalia, 2012)
¿Por qué se estudian Grafos?
Porque permiten estudiar
interrelaciones entre elementos que
interactúan unos con otros. Dado un
escenario donde ciertos objetos se
relacionan se puede “modelar el grafo”
y luego aplicar algoritmos para resolver
diversos problemas. (Agalia, 2012)
¿Qué podemos representar con
un Grafo?
- Red de Computadoras
-Conexiones de vuelo de una
aereolínea -Carreteras que
unen ciudades Impresora
-Actividades de un proyecto
-Circuitos electrónico
-Representación de un mapa