Skip to content

Instantly share code, notes, and snippets.

@milemarchese

milemarchese/6107_Matemática_Discreta-Ejercicios_de_Final.ipynb

Forked from FdelMazo/6107.ipynb
Created February 13, 2019 00:13
Show Gist options
  • Save milemarchese/3443345e9f895018dca2dacc78a9cc77 to your computer and use it in GitHub Desktop.
Save milemarchese/3443345e9f895018dca2dacc78a9cc77 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 Teoría de Grafos
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 estén 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 diámetro \n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar que el radio de un grafo $r(G)$ es menor o igual que el diámetro $\\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 mínimos).\n",
"\n",
"* **Radio de G $r(G)$**: mínimo número de excentricidad de todos los v en G.\n",
"\n",
"* **Diámetro 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 diámetro, 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 diámetro 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 es 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 está. (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 dos vertices cualesquiera 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 recíproca (todo grafo regular es completo). Como contraejemplo, un grafo de 6 vértices 4-regular."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Fórmula de Euler\n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar la fórmula 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 triángulo tiene 2 caras, la que está delimitada dentro del triángulo y la que está afuera de este.\n",
"\n",
"* **Árbol**: Grafo en el que 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 árbol 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 árbol 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 además de esto, cerraré un ciclo en el árbol (perdiendo la propiedad de árbol), luego 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": [
"## Fórmula 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 fórmula 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 fórmulas, 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": [
"## Fórmula de grafo planar sin triángulos\n",
"\n",
"**Enunciado**\n",
"\n",
"> Probar que para un grafo planar sin triángulos 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 K<sub>n</sub> 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 K<sub>n</sub> es n-1 (recordar que es regular), se puede ver que $M = \\frac{n(n-1)}{2}$.\n",
"\n",
"**Resolución**\n",
"\n",
"Simplemente, $K<sub>5</sub>$ no cumplen la fórmula de los grafos planares $M \\leq 3(N-2)$, mientras que $K1, K2, K3, K4$ sí.\n",
"\n",
"K<sub>5</sub> 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 K<sub>n,m</sub> 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 (K<sub>n,m</sub>):** Grafo bipartito donde un conjunto tiene n vértices, el otro tiene m vértices y todos los vértices en el primer conjunto están conectados a los del segundo y viceversa. Nótese 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 $K<sub>3.3</sub>$ 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 vértice consigo mismo.\n",
"\n",
"* **Aristas doble:** Par de aristas que conectan los mismos vértices.\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 vértices.\n",
"\n",
"Luego, 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 recíproca 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 $K<sub>4,1</sub>$ 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 V<sub>i</sub> incide en V<sub>j</sub>.\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 vértice conectividad es menor o igual a la arista conectividad que es menor o igual al mínimo 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 fácil 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 conecta la arista va 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$\\geq$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 común (V1). \n",
"\n",
"Un **muy** buen ejemplo de como crear un line graph de un grafo está 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 sí. Equivale al grafo completo bipartito K<sub>1,n-1</sub>.\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 K<sub>n</sub> completo cuando el G original era K<sub>1,n</sub> (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 K<sub>1,n</sub> tiene N+1 vértices y N aristas (una de V1 a cada V del otro componente). Y el L(G) de este, K<sub>n</sub>, 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 K<sub>1,n</sub>, 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$\\geq$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{Fórmula 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 fórmula queda:\n",
"\n",
"$$\\forall F \\in G \\sum_{}d(F) = 2 M \\geq 6n$$\n",
"\n",
"De acá 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-Coloración 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 y 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 V<sub>i</sub> hasta V<sub>j</sub>, 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 V<sub>i</sub> con V<sub>j</sub>."
]
},
{
"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 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",
" "
]
}
],
"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.7.1"
},
"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