# 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. ### Grafo completo vs Grafo conexo - Grafo completo: En un grafo completo de $n$ vértices, cada par de vértices está conectado por una arista, en $\frac{n(n-1)}{2}$ aristas en total - Grafo conexo: Un grafo conexo si hay al menos un camino entre cualquier par de vértices. No necesita que todos los pares de vértices estén directamente conectados por una arista, lo que lo diferencia de un grafo completo - Ejemplo: -  ### 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.