Es un conjunto de objetos unidos
por enlaces llamados, los objetos se
llaman nodos y los enlaces aristas, que
permiten representar relaciones entre elementos. Se representan con una letra Mayúscula. Su estudio se realiza
atraves objeto de la teoría de grafos.
Una representacion grafica sencilla
de lo que seria un grafo es:
Video: Teoria de grafos 
Un grafo F es un par ordenado F =(V,E), donde:
- V es un conjunto de vértices o nodos, y
- E es un conjunto de aristas o arcos, que relacionan estos nodos.
TIPOS:
Es un grafo donde las parejas ordenadas consisten en un conjunto de vértices ordenados, los cuales se convierten en parejas ordenadas son los mismos para A que para B. No es necesario poner Flechas.
2) Grafo dirigido
Es un grafo donde las parejas ordenadas consisten en un conjunto de vértices ordenados, los cuales se convierten en parejas ordenadas que no necesariamente son los mismos para A que para B. Es necesario poner Flechas.
FORMAS DE REPRESENTACION:
- Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista (union) y 0 en caso contrario.
- Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.
PROPIEDADES:
♦ Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
♦ Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
♦ Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso,
longitud, etc.).
♦ Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace distinguibles del resto (Nombrarlos)
GRAFOS ESPECIALES:
- Grafo nulo: aquel que no tiene vértices ni aristas..
- Grafo vacío: aquel que no tiene aristas.
- Grafo trivial: aquel que tiene un vértice y ninguna arista.
- Grafo plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas.
- Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas.
- Árbol: grafo conexo sin ciclos.
HISTORIA:
El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg.
La ciudad de Kaliningrado es famosa por sus siete puentesque unen ambas márgenes del río Pregel con dos de sus islas. Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno y regresando al mismo punto de partida?
Abstrayendo este problema y planteándolo con la teoría de grafos, Euler consigue demostrar que el grafo de puentes No tiene solución es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.
UTILIDAD:
Vida cotidiana:
Video: Utilidad grafos
Servicios Generales
ING. DE SISTEMAS:
 |
 |
