Fundamentos de Combinatoria, Grafos y Árboles: Conceptos Clave

Cálculo Combinatorio

Fórmulas para la selección de elementos:

• X = t + k - 1
• Y = k o Y = t - 1

Donde:

• t: tipos de elementos.
• k: cantidad a escoger (selección).

Ejemplo práctico: 27 libros, 16 de tipo A, 15 de tipo B, 10 son A y B.

Cálculo: 16 + 15 - 10 = 21. Entonces, 27 - 21 = 6.

Teoría de Grafos

Definiciones fundamentales

• Grafos isomorfos: Dos grafos G y G' son isomorfos si existe una correspondencia uno a uno entre sus vértices, tal que el número de aristas que unen cualquier par de vértices en G es igual al número de aristas que unen el par correspondiente en G'.
• Grafo conexo: Es aquel en el que existe un paseo entre cualquier par de vértices.
• Grafo ponderado: Grafo que tiene valores asignados a sus aristas.
• Grafo simple: Grafo que no contiene lazos.
• Grafo completo (Kn): Grafo simple donde todos los vértices están conectados entre sí.
• Subgrafo: Contiene algunos vértices del grafo original sin añadir aristas adicionales.
• Subgrafo generador: Contiene todos los vértices del grafo original, aunque no necesariamente todas las aristas.

Paseos y Circuitos

• Paseo simple: No repite aristas (rayas).
• Paseo elemental: No repite vértices.
• Paseo euleriano: Paseo en el que se recorren todas las aristas exactamente una vez.
• Circuito simple: No repite aristas.
• Circuito elemental: No repite vértices (el vértice terminal no cuenta).
• Circuito euleriano: Circuito en el que se recorren todas las aristas exactamente una vez y se regresa al inicio.

Árboles y Estructuras Jerárquicas

Ejemplos de clasificación

• Árbol ternario no regular: Nodo rama (d, f), nodo hoja (b, c, e, g), altura 3.
• Árbol binario regular: Raíz (a), nodo rama (b, c), nodo hoja (g, f, e, d), altura 2.

Codificación

• Código de prefijos: 1 para izquierda, 0 para derecha.
• Construcción de código de Huffman:

  Ejemplo: 5, 7, 10, 13, 18

  1. 5 + 7 = 12 → 10, 12, 13, 18
  2. 10 + 12 = 22 → 13, 18, 22
  3. 13 + 18 = 31 → 22, 31