Zusammenfassung der Ressource
Teoría de Grafos
- 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