Unidad I: Introducción a la Teoría de Gráficas

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Rocket clouds
Unidad I: Introducción a la Teoría de Gráficas por Mind Map: Unidad I: Introducción a la Teoría de Gráficas

1. Tema 1.1

1.1. Gráficas

1.1.1. Es un conjunto de nodos y arcos sin dirección

1.2. Digráfica

1.2.1. Es un conjunto de nodo y arcos con dirección

1.3. Multidigrafo

1.3.1. Es un grafo que contiene múltiples aristas

1.4. Seudodigrafo

1.4.1. Es un grafo que contiene múltiples aristas y bucles

2. Tema 1.2

2.1. Incidencia

2.1.1. Cuando un nodo es terminal de un arco

2.2. Adyacencia

2.2.1. Cuando dos nodos comparten un arco en comun o dos arcos comparten un nodo

3. Tema 1.3

3.1. Grado de un vertice

3.1.1. Es el numero de lineas que inciden en un nodo

4. Tema 1.4

4.1. Lema del Apretón de Manos

4.1.1. Una grafica tiene bucles y tiene "e" lineas y "n" vertices, entonces la sumatoria de los vertices es igual a 2 veces las lineas.

4.2. Numero de Vertices impares en un gráfica

4.2.1. Numero de Vértices impares en un gráfica siempre es par.

4.3. Algoritmo de Havel-Hakimi

4.3.1. Una secuencia de enteros d1>=d2>=...>=dv>=0 es gráfica sí, y sólo sí también lo es la lista: d2-1. d3-1, ...d(d1+1)-1,d(d1+2), ... dv, que resulta de eliminar el primer elemento y restar una unidad a los siguientes d1 valores de la lista.

5. Tema 1.5

5.1. Tipos de Lineas Dirigidas y No Dirigidas

5.1.1. Adyacentes: Si dos arcos comparten un mismo nodo o 2 nodos comparten un mismo arco

5.1.2. Paralelas: 2 lineas que comparten un mismo nodo inicial y terminal

5.1.3. Bucles: Una linea que termina en un nodo donde termino

5.1.4. En serie: Dos arcos son adyacentes y su(s) vertice(s) en comun es de grado 2

6. Tema 1.6

6.1. Tipos de gráficas

6.1.1. Nula: No tiene Aristas

6.1.2. Simple o General: No tiene bucles ni lineas paralelas

6.1.3. Regular: Donde todos los nodos tienen el mismo grado

6.1.4. Conectada: Si al menos existe un camino que une a cada par de nodos

6.1.5. Bipartida: El conjunto de vértices puede dividirse en 2 subconjuntos

6.1.6. Completa: Donde cualquier par de nodos son adyacentes

6.1.7. Árbol: Es una gráfica conectada sin circuitos

6.1.8. Bosque: Conjunto de Gráficas de Árbol

6.1.9. Multigrafo: Tiene multiples aristas, donde 2 nodos pueden estar conectado por 2 o mas aristas

6.1.10. Seudografo: Con varias aristas entre cada par de nodos y tambien puede haber bucles.

6.1.11. Seudodigrafo: Es dirigido con múltiples aristas y bucles

6.1.12. Multidigrafo: Dirigido con multiples aristas

6.1.13. Subgráficas: Parte parcial de una gráfica

7. Tema 1.7

7.1. Ismorfismo

7.1.1. Es cuando dos digráficas que tienen los mismos nodos, aristas y relación de incidencia

8. Tema 1.8

8.1. Recorridos

8.1.1. Paseos: Es una secuencia finita y alterna nodos y arcos, comenzando y terminando en un nodo de cada linea tal que sea incidente con los vértices anteriores y posteriores

8.1.1.1. Abierto: Termina en un nodo distinto al que inicio

8.1.1.2. Cerrado: Aquel que termina en el mismo nodo donde inicio

8.1.2. Trayectoria: Es un paseo abierto donde no se repiten lineas y no llevan bucles

8.1.3. Circuito: Es un paseo cerrado donde el único nodo que se repite es el del inicio y el del final, tambien lo conocemos como ciclo