Teoría de Grafos

Teoría de Grafos

1. 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)

2. 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

3. 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).

4. Si todos los vértices tienen el mismo grado, el grafo al que pertenecen se llama grafo regular. (Uruguay)

5. 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)

6. ¿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)

7. ¿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

Imágenes y archivos del mapa