LOS PUENTES DE Koenigsberg
Leonardo Euler estudió el asunto, representó las distintas zonas A, B, C y D por medio de puntos, mientras que los puentes estaban representados por líneas que unían estos puntos.
A la figura la llamó grafo, a los puntos los llamó vértices y a las líneas las denominó aristas.
Euler estudió si una figura lineal se podía dibujar con un solo trazo, y sin pasar dos veces por el mismo sitio. Llegó a la siguiente conclusión:
1. Es imposible si hay más de dos vértices impares.
2. Es posible cuando:
a) Todos los vértices son pares y el punto de partida puede ser cualquiera.
b) Cuando no hay más de dos vértices impares y en este caso el comienzo del recorrido comienza en uno de ellos y termina en el otro.
Euler demostró que hay un camino que comienza en un vértice, pasa por todas las aristas una sola vez y vuelve al punto de partida sí y sólo sí el grado de cada vértice es par (circuito Euleriano).
GRAFOS
“Un grafo G es un par (V(G), A(G)), donde V(G) es un conjunto no vacío de elementos llamados vértices, y A(G) es una familia finita de pares no ordenados de elementos de V(G) llamados aristas”.
-Se permite la posibilidad de aristas múltiples en el grafo, más de una arista con el mismo par de vértices como origen y destino.
-Se permite la existencia de aristas bucles, con inicio y destino el mismo vértice”
DEFINICIONES FUNDAMENTALES
Bucle: Toda arista de la forma (v, v)
Vértices adyacentes: se dice que 2 vértices son adyacentes si están unidos por una arista.
Aristas adyacentes :se dice que 2 aristas son adyacentes cuando tiene un vértice en común.
Se dice que un vértice es aislado si no es adyacente a ningún otro vértice.
Se dice que un grafo es simple si no tiene bucles ó aristas múltiples.
Tipos de Grafos
a) Grafo Regular: Si G=(V,A), de grado “n”, si todos sus vértices tiene grado “n”.
b) Grafo dirigido o dígrafo: Es un par G=(V,A), consistente en un conjunto finito no vacío V, cuyos miembros se llaman vértices y una familia finita A de pares ordenados de vértices a cuyos extremos llamaremos arista ó arcos.
Las aristas de los dígrafos tienen sentido
Representación de Grafos
- Matriz de adyacencia
- Matriz de incidencia
- Listas
“Sea un grafo G=(V,A), con n- vértices {v1, v2, v3, ……,vn}, su matriz de adyacencia es la matriz de orden nxn, M(G)=(aij), donde aij es el número de aristas que unen los vértices vi y vj”
Matriz de incidencia
“Es determinable cuando no existen vértices con aristas del tipo (v,v)”
Las matrices de incidencia sólo contienen ceros y unos
Matriz de adyacencia-Dígrafos
“Dado un dígrafo D=(V,E), con n-vértices {v1, v2, v3, ……,vn}, su matriz de adyacencia es la matriz de orden nxn, M(D )=(aij), donde aij es el número de arcos que tienen a vi de inicio y a vj de fin”
Matriz de incidencia-Dígrafos
“Cada fila representa a cada uno de los nodos del grafo, y las columnas las aristas, en la casilla M(i,j), aparecerá un 1 cuando el nodo de la fila i es inicial, y un -1 cuando el nodo i es final”
Exploración e Grafos: Recorridos
- Recorrido en profundidad.
- Recorrido en anchura.
Recorrido en profundidad
Profundidad : 1-2-3-4
Recorrido en anchura o niveles
Recorrido en anchura o niveles
Anchura : 1-2-4-3
0 comentarios:
Publicar un comentario