Introducción a la "Teoría de Gráficas" Unidad 1

Get Started. It's Free
or sign up with your email address
Rocket clouds
Introducción a la "Teoría de Gráficas" Unidad 1 by Mind Map: Introducción a la "Teoría de Gráficas" Unidad 1

1. Tipos de gráficas

1.1. Nula

1.1.1. No contiene aristas (Nn (n # de nodos))

1.2. Simple

1.2.1. No contiene bucles ni lineas paralelas

1.3. Regular

1.3.1. Es una gráfica simple y todos los nodos tienen el mismo grado. Lineas: n(r)/2

1.4. Conectada

1.4.1. Todos los nodos están conectado

1.4.1.1. .

1.5. Bipartida

1.5.1. El conjunto de vertices puede dividirse en 2 subconjuntos y cada linea de la gráfica uno un nodo de los dos subconjuntos.

1.5.1.1. .

1.5.1.2. Cuando todos los nodos de un subconjunto están unidos a todos los del otro se le llama: Bipartida Completa (Krs)

1.5.1.2.1. .

1.6. Completa

1.6.1. Tiene n nodos, cualquier de los nodos son adyacentes

1.6.1.1. .

1.7. Árbol

1.7.1. Gráfica conectada, sin circuitos y deberá ser un grafo simple

1.7.1.1. .

1.8. Bosque

1.8.1. Un bosque es un conjunto de árboles

1.9. Seudografo

1.9.1. Puede haber varias aristas entre cada par de nodos y tambien puede haber bucles.

1.9.1.1. .

1.10. Multigrafo

1.10.1. Tiene multiples aristas (Dos nodos pueden estár conectados por más de 2 aristas)

1.10.1.1. .

1.11. Subgráficas

1.11.1. Una gráfica "g" es subgráfica de "G" si TODOS los vertices de "g" están contenidos en G. -Cada linea de "g" dtiene los mismos vertices terminales que en "G"

1.11.1.1. .

2. Partes de una gráfica

2.1. Nodos (vertices)

2.1.1. Grado

2.1.1.1. Es el número de lineas que inciden en un nodo.

2.1.2. Aislado

2.1.2.1. Tiene grado 0

2.1.3. Colgante

2.1.3.1. Un nodo de grado 1

2.2. Aristas (Lineas)

2.2.1. Tipos

2.2.1.1. Paralelas

2.2.1.1.1. 2 Lineas que comparten nodo inicial y terminal

2.2.1.2. Bucles

2.2.1.2.1. Linea que termina en mismo nodo en el que empezó

2.2.1.3. En serie

2.2.1.3.1. Dos arcos son adyacentes y sus vertices en común tienen grado 2 d(v1)=2 e1, e2

2.2.2. Con dirección -------> Sin direccion ---------

3. Teoremas

3.1. Lema de Apretón de manos

3.1.1. Una gráfica son bucles tiene "e" Lineas y "n" vertices

3.1.1.1. La suma del grado de sus vertices es:

3.2. Número de vertices de grado impar en una gráfica sin bucles es par.

3.2.1. .

3.3. Algoritmo de Havel-Hakimi

3.4. Una gráfica simple con n vertices y k subconjuntos puede tener a lo más...

3.4.1. .

4. Recorridos

4.1. Paseos

4.1.1. Secuencia finita y alterna de nodos y arcos, comenzando y terminando en un nodo de cada linea tal que sea incidente con los vertices anteriores y posteriores.

4.1.1.1. Abierto

4.1.1.1.1. Aquel que termina en un nodo distinto al cual inició.

4.1.1.2. Cerrado

4.1.1.2.1. Aquel que termina en el mismo nodo donde inició

4.2. Trayectoria

4.2.1. Es un paseo abierto en donde no se repiten lineas, no se pueden incluir bucles.

4.3. Circuito

4.3.1. Un paseo cerrado donde el único nodo que se repite es con el primero y el final, también conocido como ciclo.

5. Incidencia-Adyacencia

5.1. Cuando un nodo es terminal de un arco se dice que son indicentes

5.1.1. El nodo incide en el arco

5.1.2. La linea indice en el nodo

5.2. Dos arcos no paralelos son incidentes de un nodo en común entonces se llaman arcos adyacentes.