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

1. Definición

1.1. Los grafos son estructuras de datos

1.2. Representan relación entre objetos

2. Aplicaciones

2.1. Química

2.2. Geografía

2.3. Ing. Eléctrica e industrial

2.4. Modelado de redes

2.4.1. De alcantarillado

2.4.2. Electricas

3. Operaciones

3.1. Añadir un nuevo vértice.

3.2. Eliminar un vértice existente.

3.3. Unión de dos vértices.

3.4. Eliminar un arco.

3.5. Conocer si dos vértices sin o no adyacente.

4. Tipos

4.1. Dirigidos

4.1.1. Definición

4.1.1.1. Si los pares de nodos tienen un sentido.

4.1.1.2. Existe un camino preestablecido

4.1.1.3. También llamado digrafo, grafo directo.

4.1.2. Conectividad

4.1.2.1. Fuertemente conexo

4.1.2.1.1. Existe un camino entre cualquier par de nodos.

4.1.2.2. Conexo (débilmente enlazado)

4.1.2.2.1. Existe una cadena entre cualquier par de nodos.

4.2. No dirigidos

4.2.1. Definición

4.2.1.1. Si los pares de nodos no tienen un sentido

4.2.2. Conectividad

4.2.2.1. Conexo

4.2.2.1.1. Existe un camino entre cualquier par de nodos.

4.3. Multigrafo

4.3.1. Aristas múltiples

4.3.2. Bucles

5. Recorridos

5.1. Profundidad

5.1.1. Busca caminos que parten desde el nodo de salida hasta que ya no es posible avanzar más, después volver atrás en busca de caminos alternativos inexplorados.

5.2. Anchura

5.2.1. Recorre el grafo en niveles (de los nodos más cercanos a los más lejanos).

6. Grados de un nodo

6.1. Grafo dirigido

6.1.1. Grado de entrada, Graden (V)

6.1.1.1. Número de arcos que llegan a V.

6.1.2. Grado de Salida, Gradsal(V)

6.1.2.1. Número de arcos que salen de V.

6.2. Grafo no dirigido

6.2.1. Grado (V)

6.2.1.1. Número de aristas que contiene a V.

7. Representación

7.1. Estática

7.1.1. Matriz de Adyacencia

7.1.1.1. Los vértices se representan por índices (0...n)

7.1.1.2. Las relaciones de los vértices se almacenan en una matriz.

7.2. Dinámica

7.2.1. Lista de Adyacencia

7.2.1.1. Los vértices firman una lista.

7.2.1.2. Cada vértice tiene una lista para representar sus relaciones (arcos).

8. Conceptos básicos

8.1. Arista

8.1.1. Es un arco de un grafo no dirigido.

8.2. Vértice adyacente

8.2.1. Vértices unidos por un arco

8.3. Factor de peso

8.3.1. Valor que se puede asociar con un arco.

8.4. Ciclos

8.4.1. Es un recorrido que vuelve al nodo de partida.

8.5. Caminos

8.5.1. Trayectoria de un punto a otro.

8.6. Recorrido

8.6.1. Es una lista ordenada de nodos.

8.7. Longitud

8.7.1. El número de ramas en el recorrido.