Teoría de los Grafos

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Rocket clouds
Teoría de los Grafos por Mind Map: Teoría de los Grafos

1. *Grafos: conjunto de vértices o nodos unidos por aristas o arcos. *Grafo acíclico: Es aquel Grafo no contiene ningún ciclo simple. *Grafo Cíclico: Se dice cíclico si tiene algún ciclo simple. *Grafo bipartido: es cualquier grado, cuyo vértices pueden ser divididos en dos conjuntos, tal que no haya aristas entre los vértices del mismo conjunto. *Grafo completo: tiene un Grafo a n-1 donde n es el número de vértice que compone el Grafo . *Grafo conexo: si es posible formar un camino desde cualquier vértice a cualquier otro Grafo. * Grafo denso: es aquel número de aristas está cercano al número de máximo de aristas. *Grafo dirigido:vértices (V) y aristas(E) tal que para cada arista perteneciente al conjunto de arista E se asocia con dos vértices en forma ordenada. *Grafo no dirigido: lados que no están orientados (no son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas. *Grafo nulo: es el Grafo cuyos conjuntos de aristas y de vértices son vacíos. *Grafo plano: es posible dibujar en el plano sin que ningún para de aristas se crucen entre sí. *Grafo ponderado: es aquel que se asocia un calor o pero a cada arista en el Grafo. *Grafo regular: cuyos vértices tienen el mismo grado. *Grafo simple: es aquel que no tiene bucles, y que ni es un multígrafo. *Grafo no simple: no tiene lados paralelos y lazos. *Grado trival: es aquel Grafo vacío con un único vértice. *Grafo vacío: cuyo conjunto de aristas es vacío.

2. Representación mediante matrices. Sintaxis : Tipo_de_variable[][]...[] Nombre_del_array= new Tipo_de_variable[dimensión1][dimensión2]...[dimensionN]; Arreglos unidimensionales: Sintaxis: TipoDatonombre[]=new TipoDato[Total de elementos];

3. La teoría de los Grafos podemos resolver diversos problemas,para circuitos secuenciales,contadores o sistemas de apertura. Un Grafo G es un para(V,E) DONDE: •V={V1,.....,Vn} es un conjunto de vértices. •E={e1,.....,em} es un conjunto de aristas. •con cada ek€{c¡,Vj}, con v¡,Vj=Vj Los vértices se repessentan como puntos y las aristas como liberas entre vértices. Ejemplo: °G= °V={a,b,c,d} °E={{a,b},{b,c},{a,c},{a,d},{d,b}}

4. "Aristas": una arista es una relación entre dos vértices de un Grafo. "Aristas Adyacentes" estás son dos aristas que se dirigen al mismos vértice y de juntan en el. "Aristas paralelas" estas son dos aristas si el vértice inicial y el final son uno mismo. "Cruce" son dos aristas que cruzan en un punto. "Grado o Valencia de un vértice" Es el número de aristas que inciden sobre un vértice. "Lazo"es una arista cuáles extremos inciden sobre el mismo vértice. "Vértice " dónde puntos o nodos con los que están conformado los Grafos. Se le dice par o impar según su grado. "Vértice adyacente" si están unidos mediante una arista. "Vértice Aislado" grado cero. "Vértice terminal" de grado 1.

5. Un Grafo (G) es un par ordenado de V y A , a dónde V es el conjunto de vértices o nodos del grado y A es un conjunto de pared de vértices e igual se le conoce como arcos o ejes del grafo. Representan conjuntos de objetos que no tiene restricción de una relación entre ellos. Pueden representar varias cosas de la vida cotidiana. Se constituyen principalmente de dos partes: aristas, vértices y los caminos del mismo grado.

6. Elementos y características

7. Componentes

8. Tipos de grafos

8.1. Simples,completos, bipartidos, planos, conexos, ponderados

9. Representación matemática de los Grafos

10. Representación computacional.

11. Algoritmos de recorrido y búsquedad.

11.1. Los más importantes son: preorden,post-orden y en-orden. Tienen tres tipos de actividades comunes: 1.visitar el nodo raíz 2.recorrer el subárbol izq. 3.recorrer el subárbol der. Estás 3 actividades llevan a cabo en distinto orden, crean sus propios recorridos del árbol. √: PREORDEN (raíz,izq,der). un árbol binario no vacío en preorden. √INORDEN (izq,raíz,der). un árbol binario no vacío en inorden(simétrico). √POSTORDEN (izq,der, raíz). un árbol binario no vacío en inorden(simétrico) Uno de los elementos de un árbol para examinar el conjunto completo. Primero se ven los algoritmos para construir el árbol.(sufijo,prefijo o posfijo) correcta cuando se da un prefijo o posfijo. 1Visitar la raiz 2Recorrer el subárbol izq en prefijo. 3Recorrer el subárbol der en prefijo. #RECORRIDO EN PREFIJO (1,2prefijo,3prefijo) #RECORRIDO EN SUFIJO (2sufijo,1,3sufijo) #RECORRIDO EN POSFIJO (2posfijo,3posfijo,1)

12. El camino más corto

12.1. Algoritmos de floyd-warshall (1959 por BERNARD ROY) 1.Permite calcular la distancia mínima entre 2 puntos de 1 Grafo. 2.Cada nodo se representa por n_A. 3.Pasos: _Asignar un valor 0 al nodo origen. _Mediante el proceso interactivo se le asignará cada nodo x¡ Un valor n igual a la longitud del camino más corto que exista desde el nodo origen al nodo xj. Algoritmo Dijkstra (1959 EDSGER DIJSKTRA) 1.Dado un V0,Dijkstra busca un conjunto D con •las menores distancias de V0 al resto de vértices 2.Al inicio , solo conocemos •las distancias de los adyacentes. •D es iniciada por a •Factor de peso para los adyacentes,infinitos para los no adyacentes 3.D va a ser mejorado sucesivamente •Escogiendo el vértice Vk no elegido antes. •Que tenga la distancia más corta V0,VK •Probamos si pasa por VK •Se puede obtener distancias más cortas de las que tenemos •Para cada vértice restante del grafo.

13. A lo ancho.

13.1. El recorrido de anchura, generalización del recorrido por niveles de un árbol. Explora sistemáticamente las aristas del grafo de forma que primero se visitan los vértices más cercanos al que estamos explorando. Consta de tres elementos: ✓contador(n) ✓vector de naturales(R) para "marcar"los vértices ya visitados y almacenar el orden de recorrido. ✓cola(Q) para gestionar los vértices no visitados.

14. Búsquedad en profundidad o DFS

14.1. 1. Se comienza en el vértice inicial (vértice con índice 1) que se marca como vértice activo. 2. Hasta que todos los vértices hayan sido visitados,en cada pasa se avanza al vecino con el menor índice siempre que se pueda , pasando este a ser el vértice activo. 3. Cuando todos los vecinos al vértice activo hayan sido visitados , se retrocede al vértice X desde el que se alcanzó el vértice activo y de prosigue siendo ahora X el vértice activo. Es equivale a un recorrido en PREORDEN de un árbol . Se elige un nodo v de partida. S e marca como visitado y se recorren los nodos ni visitados en adyacentes a v, usando recursivamente la búsquedad primero en profundidad. El recorrido puede ser para Grafos dirigidos o no dirigidos.