Teoria de Grafos
Páginas: 3 (650 palabras)
Publicado: 23 de septiembre de 2014
Grafo
Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. Para simplificar, notaremos la arista {a, b}como ab.
En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sóloimporta a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro. Generalmente, se considera que colocar los vértices en forma depolígono regular da grafos muy legibles.
Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado.
Técnicas Básicas deBúsqueda:
BÚSQUEDA EN GRAFOS
Para efectuar una búsqueda de los vértices de un grafo, se pueden emplear dos estrategias diferentes:
Búsqueda en profundidad (BEP): Se comienza en cualquier vértice yen cada paso se avanza a un nuevo vértice adyacente siempre que se pueda. Cuando todos los adyacentes a X hayan sido visitados, se retrocede al vértice desde el que se alcanzó X y se prosigue. Así seconsigue etiquetar (visitar) todos los vértices de la componente conexa en que se encuentre el vértice inicial.
Esta técnica se utiliza cuando necesitamos encontrar respuesta a un problema sobre ungrafo sin condiciones de optimización.
La idea en general de la búsqueda en profundidad comenzando en un nodo A es la siguiente:
Primero examinamos el nodo inicial A. Luego examinamos cada nodo N deun camino P que comience en A; a sea, procesamos un vecino de A, luego un vecino de un vecino de A y así sucesivamente, hasta llegar a un punto muerto o final del camino P, y de aquí volvemos atráspor P hasta que podamos continuar por otro camino P´ y así sucesivamente.
Este algoritmo es similar al del recorrido inorden de un árbol binario, y también a la forma en que se debe pasar a través...
Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. Para simplificar, notaremos la arista {a, b}como ab.
En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sóloimporta a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro. Generalmente, se considera que colocar los vértices en forma depolígono regular da grafos muy legibles.
Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado.
Técnicas Básicas deBúsqueda:
BÚSQUEDA EN GRAFOS
Para efectuar una búsqueda de los vértices de un grafo, se pueden emplear dos estrategias diferentes:
Búsqueda en profundidad (BEP): Se comienza en cualquier vértice yen cada paso se avanza a un nuevo vértice adyacente siempre que se pueda. Cuando todos los adyacentes a X hayan sido visitados, se retrocede al vértice desde el que se alcanzó X y se prosigue. Así seconsigue etiquetar (visitar) todos los vértices de la componente conexa en que se encuentre el vértice inicial.
Esta técnica se utiliza cuando necesitamos encontrar respuesta a un problema sobre ungrafo sin condiciones de optimización.
La idea en general de la búsqueda en profundidad comenzando en un nodo A es la siguiente:
Primero examinamos el nodo inicial A. Luego examinamos cada nodo N deun camino P que comience en A; a sea, procesamos un vecino de A, luego un vecino de un vecino de A y así sucesivamente, hasta llegar a un punto muerto o final del camino P, y de aquí volvemos atráspor P hasta que podamos continuar por otro camino P´ y así sucesivamente.
Este algoritmo es similar al del recorrido inorden de un árbol binario, y también a la forma en que se debe pasar a través...
Leer documento completo
Regístrate para leer el documento completo.