# TDA | Teoría: Resumen de Teoría de Grafos 1 ## Indice [TOC] ### Definiciones Básicas - Grafo: Un grafo es un par $(V, E)$, donde $V$ es un conjunto de vértices y $E \subseteq V \times V$ un conjunto de aristas. Por comodidad nombramos $n = |V|$ y $m = |E|$. - Grafo Conexo: Un grafo se dice conexo si existe un camino entre cada par de sus vértices. - Multigrafo: Un multigrafo es un grafo en el que puede haber varias aristas entre el mismo par de vértices distintos. - Pseudografo: Un pseudografo es un grafo en el que puede haber aristas múltiples entre cada par de vértices y también puede haber aristas (loops) que unan a un vértice consigo mismo. - Vecindario: Dado un vértice $v \in V$ de un grafo $G$, decimos que su vecindario $N(v)$ es el conjunto de vértices de $G$ que son adyacentes a $v$. - Grado de un Vértice: El grado de un vértice $v$ es el cardinal de su vecindario, denotado como $d(v) = |N(v)|$. En un digrafo, se tiene el grado de entrada ($d_{in}(v)$) y el grado de salida ($d_{out}(v)$). - Tipos de Grafos: Los grafos pueden ser no dirigidos o dirigidos (digrafos). ### Propiedades y Teoremas - Teorema del Grado: En cualquier grafo $G = (V,X)$, la suma de los grados de todos los vértices es igual al doble del número de aristas. - Corolario 1: Sea $G = (V, X)$ un grafo sin circuitos simples y $c$ componentes conexas. Entonces $m = n - c$. - Corolario 2: Sea $G = (V, X)$ un grafo con $c$ componentes conexas. Entonces $m \geq n - c$. - Corolario: En todo grafo, la cantidad de vértices con grado impar es par. - Grafo Completo: Un grafo se dice completo si todos sus vértices son adyacentes entre sí. Se denota como $K_n$ para un grafo completo de $n$ vértices. - Grafo Complemento: Dado un grafo $G = (V,X)$, su grafo complemento, $Ḡ = (V, \overline{X})$, tiene el mismo conjunto de vértices y un par de vértices son adyacentes en $Ḡ$ si y solo si no son adyacentes en $G$. - Teorema: Un grafo $G$ es un árbol si y solo si: 1. $G$ es un grafo sin circuitos simples y $m = n - 1$. 2. $G$ es conexo y $m = n - 1$. ### Caminos y Ciclos - Recorrido: Un recorrido en un grafo es una secuencia alternada de vértices y aristas tal que cada arista conecta un par de vértices consecutivos en la secuencia. - Camino: Un camino es un recorrido que no pasa dos veces por el mismo vértice. - Circuito: Es un recorrido $v_1, v_2, ..., v_k$ que cumple que $v_1 = v_k$. - Ciclo: es un camino en un grafo que comienza y termina en el mismo vértice, incluye al menos tres vértices y no pasa más de una vez por cada vértice, excepto por el vértice inicial que es también el final. ### Grafos Especiales - Grafo Bipartito: Un grafo $G = (V,X)$ se dice bipartito si sus vértices se pueden dividir en dos conjuntos disjuntos $V_1$ y $V_2$ tales que cada arista conecta un vértice de $V_1$ con uno de $V_2$. Un grafo es bipartito si y solo si no tiene ciclos de longitud impar. ### Isomorfismo de Grafos - Isomorfismo: Dos grafos $G$ y $G'$ son isomorfos si existe una correspondencia biyectiva entre sus vértices que preserve las adyacencias. ### Representación de Grafos - Matriz de Adyacencia: Una matriz $A \in \{0, 1\}^{n \times n}$ donde $A_{ij} = 1$ si hay una arista entre los vértices $v_i$ y $v_j$, y $A_{ij} = 0$ en caso contrario. Tiene complejidad espacial $\Theta(n^2)$ y es útil para grafos densos. Se puede guardar solo la mitad superior para ahorrar espacio. - Lista de Adyacencia: Una lista enlazada para cada vértice $v$ que contiene los vértices adyacentes a $v$. Tiene complejidad espacial $\Theta(n+m)$ y es útil para grafos dispersos. - Matriz de Incidencia: Una matriz $B \in \{0, 1\}^{n \times m}$ donde cada columna representa una arista y cada fila un vértice, con $B_{ij} = 1$ si el vértice $v_i$ es incidente a la arista $e_j$. - Elección de Representación: Depende del problema. Considerar ventajas/desventajas en complejidad espacial y temporal para operaciones como: determinar adyacencia, recorrer vecindario, remover vértice y aristas. ### Digrafos - Definición: Un digrafo $G = (V, X)$ es un conjunto de vértices $V$ y un conjunto de pares ordenados de $X$, los arcos, que indican una dirección de $u$ a $v$. - Grado de Entrada y Salida: Para cada vértice $v$, $d_{in}(v)$ es el número de arcos que entran a $v$ y $d_{out}(v)$ es el número de arcos que salen de $v$. - Matriz de Adyacencia para Digrafos: Una matriz $A \in \{0, 1\}^{n \times n}$ donde $A_{ij} = 1$ si hay un arco de $v_i$ a $v_j$, y $A_{ij} = 0$ en caso contrario. ### Herramientas para Demostrar Propiedades - Construcción: Construir explícitamente un objeto que cumpla ciertas propiedades para demostrar una afirmación. - Inducción: Demostrar una propiedad $P$ para todos los valores naturales $n$, probando el caso base ($P(0)$ o $P(1)$) y el paso inductivo ($P(n) \implies P(n+1)$). - Absurdo: Suponer que lo que queremos demostrar es falso y llegar a una contradicción. # Guía para Hacer una Demostración por el Absurdo Una demostración por el absurdo, también conocida como _reducción al absurdo_ o _argumento ad absurdum_, es una técnica de demostración matemática que prueba la validez de una proposición mostrando que la suposición de su falsedad lleva a una contradicción. ## Pasos para Realizar una Demostración por el Absurdo ### Paso 1: Entender y Formular la Proposición - **Definir claramente** la proposición que quieres demostrar. - Ejemplo: "Demostrar que $\sqrt2$ es un número irracional." ### Paso 2: Suponer lo Contrario - **Suponer que la proposición es falsa**. - Escribir claramente lo que implica esta suposición. - Ejemplo: "Supongamos que $\sqrt2$ es un número racional." ### Paso 3: Desarrollar las Implicaciones de la Suposición - **Desarrollar las consecuencias lógicas** de la suposición inicial. - Seguir razonando lógicamente para explorar las implicaciones de esta suposición. - Ejemplo: "Si √2 es racional, entonces puede ser expresado como una fracción irreducible a/b, donde a y b son enteros coprimos." ### Paso 4: Encontrar la Contradicción - **Buscar una contradicción** que surja de las implicaciones desarrolladas. - La contradicción puede ser interna (con la propia suposición) o externa (con algún principio o hecho ya establecido). - Ejemplo: "Al desarrollar a^2 = 2b^2, llegamos a que ambos a y b deben ser pares, lo cual contradice que a/b es una fracción irreducible." ### Paso 5: Concluir - **Concluir que la suposición inicial debe ser falsa** debido a la contradicción encontrada. - Afirmar la verdad de la proposición inicial. - Ejemplo: "Por lo tanto, nuestra suposición de que √2 es racional es falsa, lo que implica que √2 es irracional." ## Demostración por el Absurdo en Teoría de Grafos ### Proposición a Demostrar - En cualquier grafo bipartito, no existen ciclos de longitud impar. ### Paso 1: Suposición Contraria - Supongamos que existe un ciclo de longitud impar en un grafo bipartito. ### Paso 2: Implicaciones de la Suposición - Un grafo bipartito se define como: un grafo cuyos vértices se pueden dividir en dos conjuntos disjuntos $U$ y $V$, donde cada arista conecta un vértice en $U$ con uno en $V$. Por lo tanto, los vértices en un ciclo deben alternar entre pertenecer a $U$ y $V$. ### Paso 3: Análisis del Ciclo - Consideremos un ciclo de longitud impar, digamos de $2k+1$ vértices $k \in \mathbb{Z}$. - Si comenzamos en un vértice de $U$, el siguiente vértice debe ser de $V$, el próximo de $U$, y así sucesivamente. - Al llegar al vértice $2k+1$, deberíamos regresar al vértice inicial. ## Paso 4: Encontrar la Contradicción - Sin embargo, dado que la longitud del ciclo es impar, si comenzamos en $U$, el vértice final también debería ser de $U$ antes de regresar al inicio. - Esto es una contradicción porque en un grafo bipartito cada vértice en $U$ solo puede estar conectado con vértices en $V$ y viceversa. ## Paso 5: Conclusión - La existencia de un ciclo de longitud impar en un grafo bipartito lleva a una contradicción con la definición de grafo bipartito. - Por lo tanto, nuestra suposición de que tal ciclo existe es falsa, implicando que todos los ciclos en un grafo bipartito deben tener longitudes pares.