Skip to content

Instantly share code, notes, and snippets.

@komod0

komod0/6107 Matemática Discreta - Ejercicios de Final.ipynb

Forked from FdelMazo/6107.ipynb
Created November 17, 2018 23:43
Show Gist options
  • Save komod0/a901f4baec297a77e684f735ce6b9335 to your computer and use it in GitHub Desktop.
Save komod0/a901f4baec297a77e684f735ce6b9335 to your computer and use it in GitHub Desktop.
Download ZIP
61.07 Matemática Discreta: or How I Learned to Stop Worrying and Love the Pensamiento Lógico
Display the source blob
Display the rendered blob
Raw
6107 Matemática Discreta - Ejercicios de Final.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 61.07 Matemática Discreta <br> Teoría de Grafos\n",
"\n",
"Intento de resumen de todos los ejercicios de grafos que rondan los finales de Matemática Discreta. La idea es que esten en lenguaje simple y natural para no perderse en demostraciones. \n",
"\n",
"Son meramente para complementar el estudio, no pretenden reemplazar nada. Muy recomendables los links de fuentes!! Son super interesantes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## El radio de un grafo es menor o igual que el diametro \n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar que el radio de un grafo $r(G)$ es menor o igual que el diametro $\\phi(G)$ que es menor o igual que 2 veces el radio.\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://www3.nd.edu/~dgalvin1/40210/40210_F12/CGT_early.pdf (Theorem 1.4)\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Excentricidad de un vértice $e(v)$**: distancia máxima de v a todos los otros vértices del grafo (siempre yendo por caminos minimos)\n",
"\n",
"* **Radio de G $r(G)$**: minimo número de excentricidad de todos los v en G\n",
"\n",
"* **Diametro de G $\\phi(G)$**: máximo número de excentricidad de todos los v en G\n",
"\n",
"* **Centro de G**: Conjunto de vértices de mínima excentricidad\n",
"\n",
"* **Periferia de G**: Conjunto de vértices de máxima excentricidad\n",
"\n",
"* **Desigualdad triangular entre tres vértices conectados**: $d(a,b) \\leq d(a,c) + d(c,b)$\n",
"\n",
"**Resolución**\n",
"\n",
"$$r(G) \\leq \\phi(G) \\leq 2*r(G)$$\n",
"\n",
"La primera desigualdad $r(G) \\leq \\phi(G)$ se cumple por la definición de radio y de diametro, ya que siempre $mínimo(x) <= máximo(x)$\n",
"\n",
"La segunda desigualdad $\\phi(G) \\leq 2*r(G)$:\n",
"\n",
"Sean x,y vértices de G separados por una distancia igual al diametro de G, y sea z un vértice central del grafo:\n",
"\n",
"\n",
"\n",
"$$\\phi(G) = d(x+y) \\leq d(x,z) + d(z,y) \\leq e(z) + e(z) \\leq r(G) + r(G) \\leq 2*r(G)$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## G y G' no pueden ser ambos conexos\n",
"\n",
"**Enunciado**\n",
"\n",
"> Tanto G como G' pueden ser conexos, pero imposible que ambos lo sean\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://math.stackexchange.com/q/122184\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Grafo conexo**: Para todo u,v en G existe un camino entre ellos\n",
"\n",
"* **Grafo complemento (G')**: Para todo u,v no conectado en G, existe la arista u,v en G'\n",
"\n",
"**Resolución**\n",
"\n",
"Tengo que probar que si G no conexo --> G' conexo y que si G' no conexo --> G' conexo.\n",
"\n",
"Como (G')' = G, con tan solo probar uno de los dos ya esta. (Si G no conexo implica G' conexo, entonces G' no conexo implica G'' conexo)\n",
"\n",
"Un G no conexo puede partirse en X componentes no conexas. Tengo que mostrar que entre todo u,v de G existe un camino en G'. \n",
"\n",
"Agarro dos vertices cualesquiera, tengo dos alternativas:\n",
"\n",
"* U,V estan en distintas componentes, por lo tanto en G no existe la arista u,v y por ende en G' si lo existe --> Existe camino entre u y v\n",
"\n",
"* U,V estan en la misma componente, por lo tanto existe un vertice x en otra componente tal que las aristas u,x y u,v no existen en G. Por ende, en G' existen esas aristas, haciendo el camino u,x - x,v --> Existe camino entre u y v\n",
"\n",
"Para cualquieras dos vertices en G no conexo existe un camino en G'. Como para todo vertice en G' hay un camino que los conecta, G' es conexo."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## La matriz de adyacencia elevada a q muestra los caminos de longitud q\n",
"\n",
"**Enunciado**\n",
"\n",
"> La posición (i,j) de la matriz $A^q$ indica el número de caminos de longitud q conectan Vi con Vj.\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://math.stackexchange.com/questions/2434064/proof-raising-adjacency-matrix-to-n-th-power-gives-n-length-walks-between\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Matriz de adyacencia A**: Matriz que tiene en la posición (i,j) un 1 si existe la arista Vi,Vj, de lo contrario tiene un 0\n",
"\n",
"* **Arista**: Recordar que las aristas son caminos de longitud 1\n",
"\n",
"**Resolución**\n",
"\n",
"Prueba por inducción\n",
"\n",
"* Hipótesis inductiva $P(q)$:\n",
" - $A^q (i,j)$ indica el número de caminos de longitud q que conectan Vi con Vj\n",
"\n",
"* Paso básico $P(1)$:\n",
" - $A^1 (i,j) = A(i,j) =$ Cantidad de aristas que conectan Vi con Vj. Una arista es un camino de longitud 1. El paso básico se cumple.\n",
"\n",
"* Paso inductivo $P(q) \\implies P(q+1)$: \n",
"\n",
" * $A^{q+1} = A^q * A \\implies A^{q+1} (i,j) = \\sum_{k=1}^{n} A^q (i,k) * A (k,j) \\quad \\forall k \\neq 0 $\n",
" * $A^q (i,k) =$ Caminos de long q entre Vi y Vk\n",
" * $A (k,j) =$ Caminos de long 1 entre Vk y Vj\n",
" * $\\implies$ Hay $A^q (i,k) * A (k,j)$ caminos de long q+1 entre Vi y Vj\n",
"\n",
"Corolario: Si el grafo es conexo, entonces ningun elemento de A^k, con K=n-1 es nulo."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Todo grafo completo es regular\n",
"\n",
"**Enunciado**\n",
"\n",
"> Todo grafo completo es regular\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://proofwiki.org/wiki/Complete_Graph_is_Regular\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Grafo completo $Kn$**: Todos los vértices inciden en todos\n",
"\n",
"* **Grafo regular**: Todos los vértices tienen el mismo grado\n",
"\n",
"* **Grado de vértice $d(v)$**: Número de aristas que inciden sobre el v\n",
"\n",
"**Resolución**\n",
"\n",
"Se cumple por definición. En todos los grafos los vértices inciden sobre todos, por ende d(v) es igual a n-1 para todos los vértices del grafo. Como todos los vértices tienen el mismo número, el grafo es regular.\n",
"\n",
"No vale la reciproca (todo grafo regular es completo). Como contraejemplo, un grafo de 6 vértices 4-regular."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Formula de Euler\n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar la formula de Euler\n",
"\n",
"**Fuentes**\n",
"\n",
"> http://www.math.caltech.edu/~2014-15/2term/ma006b/09%20Planar2.pdf\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Fórmula de Euler**: Sea un grafo planar y conexo, siendo $N$ su cantidad de vértices, $M$ su cantidad de aristas y $F$ su cantidad de caras se verifica que $N-M+F=2$\n",
"\n",
"* **Grafo planar**: El grafo puede ser dibujado en un plano sin que las aristas se crucen.\n",
"\n",
"* **Cara de un grafo**: Regiones delimitadas por aristas. Siempre tener en cuenta la cara externa (infinita) 'afuera' del grafo. Por ejemplo, un triangulo tiene 2 caras, la que esta delimitada dentro del triangulo y la que esta afuera de este.\n",
"\n",
"* **Árbol**: Grafo en el todos los vértices están conectados por exactamente un camino. Es conexo y sin ciclos, y si se le sacase una arista deja de serlo. Tiene n-1 aristas.\n",
"\n",
"* **Árbol generador/de expansión (spanning tree) de un grafo conexo**: Un arbol compuesto por todos los vértices y algunas aristas del grafo. Si le agrego aristas, eventualmente llegaré al grafo original. Todo grafo conexo tiene un árbol generador\n",
"\n",
"**Resolución**\n",
"\n",
"No necesariamente inducción, pero pensado analogamente.\n",
"\n",
"Para el paso básico, agarro el árbol generador del grafo conexo que tengo. Todo arbol cumple que tiene una cara (la externa) y n-1 aristas. Por ende, Euler se cumple:\n",
"\n",
"$$ N - M + F = N - (N-1) + 1 = 2 $$\n",
"\n",
"A medida que le agrego una arista al árbol generador, para eventualmente llegar al grafo original, aumenta en uno la arista. Pero ademas de esto, cerrare un ciclo en el arbol (perdiendo la propiedad de arbol), y por ende la cantidad de caras aumentará en uno.\n",
"\n",
"$$ N - (N-1 +1) + (1+1) = 2$$\n",
"\n",
"Es así que en todos los pasos se mantiene la invariante de la fórmula, hasta tener el grafo original, planar y conexo, donde se cumple la fórmula de Euler"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Formula de grafos planares\n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar que para un grafo planar con $N\\geq3$, $M\\leq3(N-2)$\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://courses.engr.illinois.edu/cs173/fa2009/Lectures/lect_40.pdf (Sección 4)\n",
"\n",
"> https://plus.maths.org/content/maths-minute-graphs-and-handshaking-lemma\n",
"\n",
"> https://math.stackexchange.com/questions/181833/proving-that-the-number-of-vertices-of-odd-degree-in-any-graph-g-is-even\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Degree Sum Formula**: La sumatoria de los grados de todos los vértices equivale a dos veces la cantidad de aristas en G. Proviene del simple hecho de que cada arista contribuye a dos vértices (el de partida y el de llegada). $\\forall V \\in G \\sum_{}d(V) = 2 M$.\n",
"\n",
"* **Handshaking Lemma**: Partiendo de la formula anterior, se deduce (ver fuentes) que todo grafo no dirigido tiene una cantidad par de vértices con grado impar.\n",
"\n",
"* **Grado de una cara**: Cantidad de aristas que delimitan la cara.\n",
"\n",
"* **Faceshaking Lemma**: Similar a degree sum; La sumatoria de los grados de todas las caras equivale a dos veces la cantidad de aristas en G, ya que cada arista contribuye a dos caras. $\\forall F \\in G \\sum_{}d(F) = 2 M$.\n",
"\n",
"**Resolución**\n",
"\n",
"Para un grafo no conexo, siendo x la cantidad de componentes conexas de G, se pueden agregar x-1 aristas al grafo sin perder su planaridad y haciendolo conexo.\n",
"\n",
"Para un grafo conexo, partimos de dos formulas, la de Euler y el Faceshaking Lemma.\n",
"\n",
"Lo que se nota es que ya que $N \\geq 3$, el grado de toda cara del grafo debe ser $\\geq 3$ para toda cara.\n",
"\n",
"Por ende, queda que la sumatoria de los grados es mayor o igual a 3F.\n",
"\n",
"$$ N - M + F = 2 \\implies F = 2 + M - N$$\n",
"$$\\forall F \\in G \\sum_{}d(F) = 2 M \\geq 3F$$\n",
"\n",
"\n",
"Juntando:\n",
"\n",
"$$2M \\geq 3F \\implies 2M \\geq 3(2+M-N) \\implies 2M\\geq 6+3M-3N \\implies M \\leq -6+3N \\implies M \\leq 3(N-2)$$\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Formula de grafo planar sin triangulos\n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar que para un grafo planar sin triangulos con N>=3, M<=2(n-2)\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://courses.engr.illinois.edu/cs173/fa2009/Lectures/lect_40.pdf (Sección 5)\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Triangulo**: Cara de grado 3\n",
"\n",
"**Resolución**\n",
"\n",
"Similar al problema anterior, solo que ahora toda cara del grafo debe ser mayor o igual a 4.\n",
"\n",
"\n",
"$$ N - M + F = 2 \\implies F = 2 + M - N$$\n",
"$$\\forall F \\in G \\sum_{}d(F) = 2 M \\geq 4F$$\n",
"\n",
"\n",
"Juntando:\n",
"\n",
"$$2M \\geq 4F \\implies 2M \\geq 4(2+M-N) \\implies 2M\\geq 8-2N+2M \\implies M \\leq 2(N-2)$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Teorema de Kuratowski (1)\n",
"\n",
"**Enunciado**\n",
"\n",
"> Encontrar el menor valor de N para que el grafo completo Kn no sea planar\n",
"\n",
"**Fuentes**\n",
"\n",
"> http://www.cs.xu.edu/~otero/math330/kuratowski.html \n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Aristas de un grafo completo**: Por el degree sum formula y sabiendo que el grado de todo vértice en un grafo Kn es n-1 (recordar que es regular), se puede ver que $M = \\frac{n(n-1)}{2}$\n",
"\n",
"**Resolución**\n",
"\n",
"Simplemente, $K5$ no cumplen la formula de los grafos planares $M \\leq 3(N-2)$, mientras que $K1, K2, K3, K4$ sí.\n",
"\n",
"K5 tiene $\\frac{5*(5-1)}{2} = 10$ aristas. 10 no cumple ser menor que $3*(5-2) = 9$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Teorema de Kuratowski (2)\n",
"\n",
"**Enunciado**\n",
"\n",
"> Encontrar el menor valor de N,M para que el grafo completo Kn,m no sea planar\n",
"\n",
"**Fuentes**\n",
"\n",
"> http://www.cs.xu.edu/~otero/math330/kuratowski.html \n",
"\n",
"> http://www.nomachetejuggling.com/2011/10/29/why-the-complete-bipartite-graph-k33-is-not-planar/\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Grafo bipartito**: Grafo que puede ser partido en dos conjuntos disjuntos (excluyentes) donde solo puede haber aristas de un conjunto a otro, es decir, los vértices dentro del mismo conjunto no estan conectados.\n",
"\n",
"* **Grafo bipartito completo (Kn,m):** Grafo bipartito donde un conjunto tiene n vértices, el otro tiene m vértices y todos los vértices en el primer conjunto estan conectados a los del segundo y viceversa. Notese que el grafo tiene N+M vértices en total.\n",
"\n",
"* **Aristas de un grafo completo**: Se puede ver que si todos los vértices del conjunto 1 están conectados con los del conjunto 2 y todos los vértices del conjunto 2 están conectados con los del conjunto 1, el grafo tiene $M*N$ aristas.\n",
"\n",
"**Resolución**\n",
"\n",
"Al igual que el problema anterior, la solución proviene de que $K3,3$ no cumple la fórmula de grafos planares sin triángulos $M \\leq 2(N-2)$.\n",
"\n",
"El grafo $K3,3$ tiene 9 aristas y 6 vértices, y 9 no es menor que $2*(6-2) = 8$.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sumatoria de autovalores de un grafo simple\n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar que la sumatoria de todos los autovalores de un grafo simple es 0\n",
"\n",
"**Fuentes**\n",
"\n",
"> http://mate.dm.uba.ar/~aldoc9/Publicaciones/Slides/edg.pdf\n",
"\n",
"> https://math.stackexchange.com/questions/241875/sum-of-the-eigenvalues-of-adjacency-matrix\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Autovalor:** Los autovalores de un grafo son los autovalores de su matriz de adyacencia. Estos pueden sacarse con el metodo de Algebra II de ver para que determinante de (A-λI) es igual a 0. En una matriz, la suma de su traza (diagonal) es igual a la suma de sus autovalores.\n",
"\n",
"* **Grafo simple:** Grafo sin lazos ni aristas dobles.\n",
"\n",
"* **Lazo o bucle:** Arista que conecta a un vertice consigo mismo.\n",
"\n",
"* **Aristas doble:** Par de aristas que conectan los mismos vertices.\n",
"\n",
"\n",
"**Resolución**\n",
"\n",
"Siendo la matriz de adyacencia la que representa como se conectan el vértice en la fila i con el vértice en la columna j, y viendo que el grafo es simple (sin lazos!), vemos que la diagonal principal de la matriz A va ser toda nula (porque el vértice i nunca se va a conectar consigo mismo, es decir A(1,1)=0, A(2,2)=0, A(3,3)=0...). \n",
"\n",
"Ya que la sumatoria de la traza de A es 0 y siendo la sumatoria de autovalores igual a la sumatoria de la traza, vemos que la sumatoria de autovalores es 0."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sumatoria de cuadrados de todos los autovalores\n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar que la sumatoria de los cuadrados todos los autovalores de un grafo es 2M\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://math.stackexchange.com/questions/1799744/sum-of-squares-of-eigen-values-of-adjacency-matrix-is-equal-to-twice-the-number\n",
"\n",
"**Resolución**\n",
"\n",
"Habiendo mostrado que $A^2 (i,j)$ representa los caminos de tamaño 2 de i a j, si yo evaluo $A^2$ sobre la traza (o sea, (1,1) (2,2) etc), esto va a representar a todos los caminos que me dejan mover desde i hasta un j adyacente, y luego volver a i, o sea que $A^2 (i,i)$ muestra la cantidad de adyacentes de i, que equivale a su grado.\n",
"\n",
"Se puede ver que la sumatoria de autovalores al cuadrado es la sumatoria de autovalores de $A^2$ que equivale a la sumatoria de su traza, que ya mostramos que seran todos los grados de los vertices.\n",
"\n",
"Por ende, sumar la traza de A equivale a sumar los grados de sus vértices y esto, por el degree sum formula equivale a 2M."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Si dos grafos son isomorfos comparten espectro\n",
"\n",
"**Enunciado**\n",
"\n",
"> Si dos grafos son isomorfos, tienen el mismo espectro. La reciproca es falsa.\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://math.stackexchange.com/questions/2636239/do-isomorphic-graphs-have-same-values-for-adjacency-matrices-and-spectrum\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Grafos isomorfos:** Dos grafos son isomorfos cuando existe una función biyectiva tal que se la pueda aplicar a todos los vértices y se mantenga la adyacencia de cada uno. Es decir, cuando uno puede ser redibujado como el otro y viceversa. Dos grafos son isomorfos si sus matrices de adyacencia son semejantes. Dos grafos son isomorfos si solo si sus complementos son isomorfos.\n",
"\n",
"* **Espectro:** El conjunto de autovalores del grafo.\n",
"\n",
"**Resolución**\n",
"\n",
"Dos grafos son isomorfos si sus matrices de adyacencias son semejantes. Y dos matrices son semejantes si pueden ser diagonalizables al mismo D. Ese D es la matriz que contiene en su diagonal principal a los autovalores del grafo.\n",
"\n",
"Por ende, si son isomorfos, sus matrices de adyacencias se pueden diagonalizar al mismo D, y ese D será el conjunto de autovalores, es decir, el espectro.\n",
"\n",
"La reciproca es falsa, y un contraejemplo es un grafo completo bipartito 1,4 (imaginarse una cruz) que comparte espectro con un grafo que puede ser imaginado como un cuadrado con un punto suelto en el medio.\n",
"\n",
"El espectro del grafo bipartito $Kr,s$ se calculó como $[ +\\sqrt{rs}, -\\sqrt{rs}, 0 (\\text{r+s-2} veces)]$, y en el caso de $K4,1$ es $[-2,2,0,0,0]$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Matriz laplaciana\n",
"\n",
"**Enunciado**\n",
"\n",
"> El significado de cada elemento (i,j) de la matriz $$L=M*M^t$$\n",
"\n",
"**Fuentes**\n",
"\n",
"> http://www.maths.nuigalway.ie/~rquinlan/linearalgebra/section3-1.pdf\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Matriz de incidencia de un Grafo (M):** Matriz donde el elemento (i,j) representa que el Vi incide en Vj.\n",
"\n",
"* **Matriz Laplaciana (L):** Una matriz de representación de grafos, que se define como $L = M * M^t$ donde:\n",
"\n",
"$$L(i,j) = \n",
"\\begin{cases}\n",
"\\kappa_i & \\text{si}\\ i = j \\\\\n",
"-1 & \\text{si}\\ i \\neq j\\ \\text{y}\\ n_i \\text{ es adyacente a } n_j \\\\\n",
"0 & \\text{otro caso}.\n",
"\\end{cases}\n",
"$$\n",
"\n",
"**Resolución**\n",
"\n",
"Los valores de cada elemento de la matriz laplaciana:\n",
"\n",
"* El grado de cada vértice porque es la sumatoria de la secuencia de grados del vértice\n",
"\n",
"* -1 porque es -1 de que la arista es saliente multiplicado por 1 de que la arista es entrante (de las matrices de incidencia e incidencia traspuesta respectivamente)\n",
"\n",
"* 0 porque no hay nada para multiplicar en las matrices de incidencia/incidencia traspuesta."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Teorema de Whitney\n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar que si un grafo es conexo, la vertice conectividad es menor o igual a la arista conectividad que es menor o igual al minimo grado del grafo. $$X(G) \\leq \\lambda(G) \\leq \\delta(G)$$\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://math.stackexchange.com/questions/1441288/inequality-relating-connectivity-edge-connectivity-and-minimum-degreewhitneys\n",
"\n",
"> https://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK4/NODE166.HTM\n",
"\n",
"> https://www.math.hmc.edu/~kindred/cuc-only/math104/lectures/lect09-slides-handout.pdf (Filmina 6 en adelante, tiene prueba por inducción!)\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Vertice conectividad (X(G)):** La mínima cantidad de vértices que le puedo sacar a un grafo (es decir, el corte de vértices) para desconectarlo.\n",
"\n",
"* **Arista conectividad ($\\lambda(G)$):** La mínima cantidad de aristas que le puedo sacar a un grafo (es decir, el corte de aristas) para desconectarlo.\n",
"\n",
"**Resolución**\n",
"\n",
"Una forma facil de ver la primera desigualdad es que si se encuentra un corte de aristas que desconecta el grafo, entonces sacar cualquiera de los dos vértices que la arista conectan van a sacar la arista. Es decir, sacar **un** vértice equivale a sacar la arista que dijimos ser un corte de aristas. Por ende, el corte de vértices mínimo sera menor o igual al corte de aristas.\n",
"\n",
"Si, se pueden encontrar cortes de vértices aun menores, es por eso que el corte de aristas funciona como una cota superior del corte de vértices.\n",
"\n",
"La forma de ver la segunda igualdad es que si V es el vértice con mínimo grado del grafo, entonces sus aristas son vitales para no desconectar el grafo. Desconectar todas las aristas que conectan al vértice de menor grado lo desconectarían del grafo, haciendo que el mínimo grado funcione como cota superior del corte de aristas."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Vértice y arista conectividad de grafos tal que su grafo-arista sea completo\n",
"\n",
"**Enunciado**\n",
"\n",
"> Determinar la vertice conectividad y arista conectividad para todos los grafos que su grafo arista es el completo Kn, con n>=3\n",
"\n",
"**Fuentes**\n",
"\n",
"> http://mathworld.wolfram.com/LineGraph.html (Ver tabla!!)\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Grafo arista (L):** El grafo arista de un grafo es un grafo que representa las adyacencias del grafo original. Para esto, se toman todas las aristas de G y se ponen como vértices de L(G), luego, las aristas de L(G) conectan a los vértices de L(G) cuando las aristas originales tenían un vértice en común. \n",
"\n",
"Por ejemplo, si en el grafo original se conectava V1 con V2 y V1 con V3, entonces ahora L(G) tendrá de vértices a A12 y A13 y una arista conectandolos, ya que en el grafo original tenían un vértice en comun (V1). \n",
"\n",
"Un **muy** buen ejemplo de como crear un line graph de un grafo esta en [Wikipedia](https://en.wikipedia.org/wiki/Line_graph#Example). Muy bueno para comprender el concepto!\n",
"\n",
"* **Grafo estrella (Sn):** Grafo donde un vértice esta conectado a todo el resto, y estos no están conectados entre si. Equivale al grafo completo bipartito K1,n-1.\n",
"\n",
"**Resolución**\n",
"\n",
"Se piden dos cosas entonces:\n",
"\n",
"* Encontrar el grafo G tal que L(G) sea completo\n",
"\n",
"* De ese grafo, notar su vértice conectividad y arista conectividad\n",
"\n",
"Lo primero a notar es que un L(G) es Kn completo cuando el G original era K1,n (es decir, el grafo completo bipartito con V1 conectado a N vértices), también conocido como grafo estrella (pero de n+1). Esto pasa porque si en el grafo original tenemos un vértice conectado a K vértices, entonces L(G) representará estas conexiones, resultando en el grafo completo.\n",
"\n",
"Pensar que K1,n tiene N+1 vértices y N aristas (una de V1 a cada V del otro componente). Y el L(G) de esté, Kn, tendrá n vértices y $\\frac{n(n-1)}{2}$ aristas\n",
"\n",
"Finalmente, se pide el vértice conectividad y arista conectividad de un grafo K1,n, AKA un grafo estrella. El grafo tiene mínimo grado 1 (el V1 suelto), y como vimos en el punto anterior, el mínimo grado de un G es cota superior de la arista conectividad y esta es una cota superior del vértice conectividad, resultando que los 3 valores sean 1."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## No existe grafo planar tal que su complemento sea planar\n",
"\n",
"**Enunciado**\n",
"\n",
"> No existe grafo planar tal que G' sea planar, con N>=10\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://math.stackexchange.com/questions/128657/how-to-prove-that-a-simple-graph-having-11-or-more-vertices-or-its-complement-is\n",
"\n",
"**Resolución**\n",
"\n",
"Ya vimos que si un grafo es planar se cumple que $m \\leq 3(n-2)$. (Sale de la formula de Euler).\n",
"\n",
"Por otro lado, sabemos que la cantidad de aristas del grafo complemento es básicamente las del grafo completo Kn menos las del grafo original. Y un grafo completo tiene $\\frac{n(n-1)}{2}$ Es decir $m' = \\frac{n(n-1}{2} - m$.\n",
"\n",
"Buscamos por el absurdo un grafo tal que el y su complemento sean planares. En otras palabras, estamos buscando el m y el m' tal que ambas cumplan la formula de grafos planares.\n",
"\n",
"$$ m' = \\frac{n (n-1)}{2} - m \\quad \\text{ y }\\quad m' \\leq 3(n-2) $$\n",
"\n",
"$$ \\frac{n (n-1)}{2} - m \\leq 3(n-2) $$\n",
"\n",
"$$ \\frac{n (n-1)}{2} \\leq 3(n-2) + m \\quad \\text{ con } \\quad m \\leq 3(n-2) $$\n",
"\n",
"$$ \\frac{n (n-1)}{2} \\leq 3(n-2) + 3(n-2) = 6(n-2) = 6n -12 $$\n",
"\n",
"$$ \\frac{n (n-1)}{2} \\leq = 6n -12 $$\n",
"\n",
"$$ n^2 - 13n + 24 \\leq 0 $$\n",
"\n",
"De la última formula cuadrática, vemos que no hay n>10 que cumpla. Por ende, demostrado por el absurdo, no hay grafo planar con n>10 tal que su complemento sea planar.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Todo grafo planar conexo tiene al menos un vértice con grado menor o igual a 5\n",
"\n",
"**Enunciado**\n",
"\n",
"> Todo grafo planar conexo con N>=3 tiene al menos un vertice de grado menor o igual a 5\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://math.stackexchange.com/questions/763598/every-planar-graph-has-a-vertex-of-degree-at-most-5\n",
"\n",
"**Resolución**\n",
"\n",
"Prueba por contradicción. Imaginamos un grafo planar con todos los vértices con grado mayor o igual a 6.\n",
"\n",
"Sabemos dos cosas entonces:\n",
"\n",
"$$ m \\leq 3(n-2) \\quad \\text{Formula de grafos planares. Sale de Euler}$$\n",
"\n",
"$$\\forall F \\in G \\sum_{}d(F) = 2 m \\quad \\text{Degree Sum Formula}$$\n",
"\n",
"Si todos los vértices tienen grado mayor o igual a 6, el degree sum formula queda:\n",
"\n",
"$$\\forall F \\in G \\sum_{}d(F) = 2 M \\geq 6n$$\n",
"\n",
"De aca sale:\n",
"\n",
"$$ m \\geq 3n$$\n",
"\n",
"Y finalmente:\n",
"\n",
"$$ 3n \\leq m \\leq 3n-6 \\quad \\text{Lo cual es absurdo}$$ \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Teorema de los 5 colores\n",
"\n",
"**Enunciado**\n",
"\n",
"> Todo grafo planar es 5-coloreable\n",
"\n",
"**Fuentes**\n",
"\n",
"> http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/MatthewWahab/5color.html\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **K-Coloracion de un grafo:** Pintar todos los vértices un grafo tal que todos los adyacentes tengan distintos colores.\n",
"\n",
"* **Numero cromático (K):** Mínimo número de una K-coloración del grafo.\n",
"\n",
"* **K'-Coloracion de un grafo:** Pintar todas las aristas tal que todas las aristas adyacentes (que compartan vértice) tengan distinto color.\n",
"\n",
"* **Indice cromático (K'):** Mínimo color de una K'-coloración.\n",
"\n",
"**Resolución**\n",
"\n",
"Caso trivial: si la cantidad de vértices es menor o igual a 5, puedo pintar todos los vértices de distintos colores.\n",
"\n",
"Para grafos con más de 5 vértices:\n",
"\n",
"* Sea V el vértice con menor grado del grafo\n",
"\n",
" * Si el grado es mayor o igual a 6 no es planar (como ya se vió) --> Contradicción\n",
"\n",
" * Si el grado es menor o igual a 4: Pinto el de un color, y los otros 4 de otro. --> Cumple\n",
"\n",
" * Si el grado es 5: Pinto uno de los adyacentes de un color, y el siguiente adyacente salteando a uno.\n",
" \n",
" <img style=\"width:300px;\" src=\"http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/MatthewWahab/5cpdeg5connecteddisconnected.bmp\">\n",
" \n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Todo grafo simple tiene dos vértices de igual grado\n",
"\n",
"**Enunciado**\n",
"\n",
"> Todo grafo simple de n mayor o igual a 2 tiene dos V de igual grado\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://math.stackexchange.com/questions/251310/if-n-is-a-natural-number-ge-2-how-do-i-prove-that-any-graph-with-n-vertic\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"* **Pidgeonhole principle:** Si tengo n palomas que pongo en m cajas, con n>m, al menos una caja tendrá más de una paloma.\n",
"\n",
"**Resolución**\n",
"\n",
"* Un grafo conexo simple tiene una secuencia de grados: d={1,2,...,n-1}. Por pidgeon hole principle, teniendo n vértices en esa secuencia, al menos un par van a tener el mismo grado.\n",
"\n",
"* Un grafo no conexo simple tiene (en el peor de los casos) una secuencia de grados: d={1,2,...,n-2}. Por pidgeon hole principle, teniendo n vértices en esa secuencia, al menos un par van a tener el mismo grado."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sumatoria de matriz de adyacencias de grafo conexo\n",
"\n",
"**Enunciado**\n",
"\n",
"> Sea G un grafo y A su matriz de adyacencia, G es conexo si solo si $\\sum_{k=1}^{n-1} A^k$ no contiene elementos nulos\n",
"\n",
"**Resolución**\n",
"\n",
"Un grafo es conexo si existe un camino entre todos sus vértices. Entonces, ya habiendo demostrado que $A^q (i,j)$ representa los caminos de longitud q desde Vi hasta Vj, la sumatoria de todos los $A^q$ dara distinto a 0, porque si un elemento fuese 0 esto significaría que no hay forma tal de conectar Vi con Vj"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Teorema de Dirac, teorema de Ore y grafos hamiltonianos\n",
"\n",
"**Enunciado**\n",
"\n",
"> Sean D los grafos que cumplen el teorema de Dirac, O los grafos que cumplen el teorema de Ore y H los grafos Hamiltonianos, demostrar que D esta contenido en O que esta contenido en H y que D!=O!=H\n",
"\n",
"**Fuentes**\n",
"\n",
"> http://mathonline.wikidot.com/dirac-s-and-ore-s-theorem\n",
"\n",
"> https://proofwiki.org/wiki/Dirac%27s_Theorem\n",
"\n",
"> https://proofwiki.org/wiki/Ore%27s_Theorem\n",
"\n",
"> http://www.ma.rhul.ac.uk/~uvah099/Maths/Combinatorics07/Old/Ore.pdf\n",
"\n",
"**Definiciones necesarias**\n",
"\n",
"\n",
"* **Camino:** Secuencia de aristas que conectan vértices distintos.\n",
"* **Ciclo:** Camino pero cerrado, es decir, el primer y último vértice son el mismo.\n",
"* **Ciclo Hamiltoniano:** Ciclo que pasa por todos los vértices exactamente una vez. Un grafo completo es hamiltoniano.* * **Grafo Hamiltoniano:** Grafo que contiene un ciclo hamiltoniano\n",
"* **Teorema de Dirac:** Si un grafo es simple y si el grado de todos los vértices es mayor o igual a $\\frac{n}{2}$, entonces el grafo contiene un camino hamiltoniano.\n",
"\n",
"$$ \\text{si} \\quad \\forall v \\in G \\quad d(v) \\geq \\frac{n}{2} \\implies \\text{Grafo es hamiltoniano} \\quad \\text{Teorema de Dirac}$$\n",
"\n",
"* **Teorema de Ore:** Si un grafo es conexo simple con n mayor o igual a 3, y si la suma de todos los grados de los vértices no adyacentes es mayor o igual a n, entonces el grafo contiene un camino hamiltoniano.\n",
"\n",
"$$ \\text{si} \\quad \\forall \\text{u,v no ady} \\quad d(u) + d(v) \\geq n \\implies \\text{Grafo es hamiltoniano} \\quad \\text{Teorema de Ore}$$\n",
"\n",
"**Resolución**\n",
"\n",
"Este ejercicio es inmenso. Hay que:\n",
"\n",
"* Demostrar Ore y Dirac, lo cual muestra que Ore y Dirac estan contenidos en los grafos hamiltonianos.\n",
"* Demostrar que Ore no comprende todos los grafos hamiltonianos.\n",
"* Demostrar que Dirac esta contenido en Ore, pero no son iguales.\n",
"\n",
"---\n",
"\n",
"* Ore esta contenido en Hamilton (Prueba del teorema de Ore):\n",
"\n",
"Prueba por contradicción: Un grafo que cumple Ore pero que no es hamiltoniano\n",
"\n",
"Si a G le agrego aristas se convierte en completo y por ende es hamiltoniano. Esto me muestra que existe un G¹ que es G más aristas tal que si le agrego una arista se convirte en hamiltoniano. \n",
"\n",
"Entonces, ese G¹ si o si tiene un camino (pero no un ciclo!) hamiltoniano. Este camino dice que tengo un i entre 2 y n-1 tal que conecto a V1 con Vi con Vn, pero recordando que es un camino y que las puntas no estan conectadas, no existe la arista V1 con Vn.\n",
"\n",
"Es decir, tengo el camino {V1, .... Vn} hamiltoniano y recuerdo que d(Vi)+d(Vn) es mayor o igual a n (ya que por hipotesis mi grafo cumple con Ore).\n",
"\n",
"Entonces, por Pigeonhole Principle, existe un i entre 2 y n-1 tal que Vi es adyacente a V1 y Vi-1 es adyacente a Vn.\n",
"\n",
"Pero eso armaría el ciclo {v1,v2,…,vi−1,vn,vn−1,…,vi,v1}, que es un ciclo hamiltoniano. Entonces, si G cumple Ore es hamiltoniano!!\n",
"\n",
"* Para mostrar que Ore es distinto que Hamilton, solo hay que mostrar un grafo en Hamilton pero no en Ore, como C5:\n",
"\n",
" <img style=\"width:200px;\" src=\"http://www4b.wolframalpha.com/Calculate/MSP/MSP96114db95eh8506eb820000534b8dc070979abb?MSPStoreType=image/gif&s=49\">\n",
"\n",
"---\n",
"\n",
"* Dirac esta contenido en Ore:\n",
"\n",
" * Solamente reemplazar Dirac en Ore:\n",
"\n",
"$$ d(u) + d(v) \\geq \\frac{n}{2} + \\frac{n}{2} \\geq n $$\n",
"\n",
"**Si G cumple Dirac, cumple Ore, y si G cumple Ore, es hamiltoniano**\n",
"\n",
"* Para mostrar que Dirac es distinto que Ore, mostrar un grafo en Ore pero no en Dirac\n",
"\n",
"Un ejemplo es el siguiente grafo **sin la arista BC**\n",
"\n",
" <img style=\"width:200px;\" src=\"http://cdn-ak.f.st-hatena.com/images/fotolife/f/faith_and_brave/20120628/20120628155826.png\">\n",
" \n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Teorema de amigos y extraños\n",
"\n",
"**Enunciado**\n",
"\n",
"> Demostrar que si G tiene 6 vértices, o bien G o bien G' contiene un triangulo.\n",
"\n",
"**Fuentes**\n",
"\n",
"> https://www.youtube.com/watch?v=xdiL-ADRTxQ\n",
"\n",
"**Resolución**\n",
"\n",
"Ver el video que es genial!\n",
"\n",
"Si n es 6, todo V tiene un grado entre 0 y 5. \n",
"\n",
"* Si tengo 3 adyacentes en G: tengo un triangulo en G.\n",
"\n",
"* Si tengo 3 no adyacentes en G, los tengo en G': tengo un triangulo en G'.\n",
"\n",
"* Si dos vértices son adyacentes: tengo un triangulo en G.\n",
"\n",
"* Si ninguno es adyacentente: tengo un triangulo en G'."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.6"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": false,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": true
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment