Teoría de Grafos y Optimización: Conceptos Fundamentales y Algoritmos

Teoría de Grafos y Optimización

Programación Lineal

La programación lineal sirve para resolver problemas de funciones lineales mediante el uso de algoritmos. Estos algoritmos resuelven problemas del tipo Maximizar (f: R^m -> R) o minimizar (x1-xn) -- f(x1-xn) = a1 * x1 + ... + an * xn. Existen algoritmos como: gráficos, simplex y transporte de redes.

Conjuntos Convexos

Definición de Segmento

Dados dos puntos cualesquiera, el segmento que los une está en el conjunto. El segmento que une dos puntos P, Q pertenecientes a R^m es el conjunto de puntos definido por [P, Q] = t * P + (1 - t) * Q, 0 <= t <= 1.

Conjunto Convexo

Un conjunto de puntos C perteneciente a R^n es convexo si para cualquier par de puntos P, Q pertenecientes a C, el segmento [P, Q] pertenece a C.

Grafos

Definición de Grafo

Un grafo es un conjunto cuyos elementos denominaremos puntos o vértices y un conjunto de parejas de dos elementos que denominaremos aristas. Una relación en un conjunto es un subconjunto del producto directo. La teoría de grafos comienza por el estudio de las relaciones en un conjunto.

Ejemplo de Relación

Conjunto V (habitantes de la Tierra) y relación (parejas de personas del mismo país).

Propiedades de una Relación

• Reflexiva: (Persona1, Persona1), es decir, cada vértice se relaciona consigo mismo.
• Simétrica: Si (P1, P2) pertenece a A, entonces (P2, P1) también.
• Transitiva: Si (P1, P2) y (P2, P3) pertenecen a A, también (P1, P3).

Representaciones de una Relación

• En el plano cartesiano (propiedad de simetría y reflexiva).
• En una matriz (las 3 propiedades).
• Grafo.

Tipos de Relación

• De equivalencia: (Las 3 propiedades).
• De orden: (Según cuáles de las 3 propiedades se cumplen).

Caminos Hamiltonianos

Hay varios teoremas para saber si existe un camino hamiltoniano:

Teoremas sobre Caminos Hamiltonianos

• Teorema 1: Si hay un vértice con grado 1, entonces no existe circuito.
• Teorema 2: Si hay un vértice de grado 2, entonces forma parte de cualquier circuito.
• Teoremas particulares: Si el grado de los vértices y el número de vértices es suficientemente grande, entonces existe circuito.
• Teorema de Dirac: Grafo con m vértices (m >= 3) y grado de los vértices >= m/2, entonces hay circuito.
• Teorema de Ore: Grafo con m vértices (m >= 3) y para cada par de vértices v y v' no adyacentes, la suma de sus grados >= m.

Álgebra de Boole

Definición de Álgebra de Boole

Un álgebra de Boole es un conjunto C con dos operaciones (suma y producto con a y b pertenecientes a C) que cumple las siguientes propiedades:

• Asociativa.
• Conmutativa.
• Existe elemento neutro.
• No hay opuesto ni inverso, pero en su lugar hay complementario. Sea A un subconjunto, el complementario B de A es el subconjunto que contiene todos los elementos del total que no están en A.
• Distributiva.

Según la definición de Boole, se deducen otras 8 propiedades:

1. Los neutros son únicos.
2. Involución.
3. Idempotencia.
4. Identidad de los neutros.
5. Absorción o simplificación.
6. Neutros recíprocamente complementarios.
7. 7.
8. Leyes de Morgan.

Isomorfismo y Matrices de Adyacencia

Isomorfismo

Mismos vértices y mismas aristas y ciclos de mayor orden para establecer la correspondencia.

Matriz de Adyacencia

Al lado, orígenes y arriba, destinos, y con un 1 se representa la unión. Si la matriz es simétrica, el grafo es no dirigido.

Cadenas, Ciclos y Circuitos

Cadenas y Ciclos

Una cadena cerrada es si va de un punto b al mismo punto b. Un ciclo es si un punto c va a c otra vez sin repetir aristas.

Circuito Euleriano

Si hay vértices con grados impares, no hay circuito euleriano, pero si solo hay dos grados impares, entonces sí.

Circuitos y Recorridos

Un circuito es cíclico y un recorrido solo va de un punto a otro.

Ejercicio de Transporte

Pasos para Resolver un Problema de Transporte

• Paso 1: Orígenes de donde salen flechas, transbordos entran y salen, y destinos solo salen flechas.
• Paso 2: En la tabla, a la izquierda se colocan primero los orígenes y luego los transbordos, y arriba primero los transbordos y luego los destinos.
• Paso 3: Se le suma la suma de los transbordos.
• Paso 4: Método del Rincón Noroeste.