{"id":1095,"date":"2026-04-22T11:15:35","date_gmt":"2026-04-22T09:15:35","guid":{"rendered":"https:\/\/clases.jesussoto.es\/?p=1095"},"modified":"2026-04-23T18:08:57","modified_gmt":"2026-04-23T16:08:57","slug":"mad-laplaciana-de-un-grafo","status":"publish","type":"post","link":"https:\/\/clases.jesussoto.es\/?p=1095","title":{"rendered":"MAD: Laplaciana de un grafo"},"content":{"rendered":"<p>Sea \\(G(V,E)\\) un grafo simple y sin bucles con \\(|V|=n\\) y sea \\(A\\) la matriz \\(n\\times n\\) de adyacencia del grafo. Como la matriz es real y sim\u00e9trica, se puede diagonalizar mediante una matriz ortogonal \\[A=P\\ D\\ P^t,\\] siendo \\(D=diag(\\lambda_1,\\lambda_2,\\ldots,\\lambda_n)\\), donde \\(\\lambda_i\\) son los autovalores de \\(A\\). Recordemos que los autovalores se puede repetir.<\/p>\n<blockquote>\n<p><strong>Definici\u00f3n<\/strong>: Denominamos espectro de una grafo al conjunto de autovalores de su matriz de adyacencia.<\/p>\n<\/blockquote>\n<p>Como sabemos de nuestros estudios de \u00c1lgebra lineal, podemos considerar \\[\\lambda_1\\geq \\lambda_2 \\geq \\ldots \\geq\\lambda_n,\\] ordenados de mayor a menor. Como la traza de \\(A\\) es cero, entonces las suma de los autovalores ser\u00e1 cero, por tanto habr\u00e1 positivos y negativos. En concreto, \\(\\lambda_1>0\\) y \\(\\lambda_n<0\\).\n\n\n\n\n\n<blockquote>\n<p><strong>Lema<\/strong>: Un grafo es bipartito si y s\u00f3lo si los autovalores son sim\u00e9tricos respecto al cero; es decir, si \u03bb es autovalor, entonces \u2212\u03bb tambi\u00e9n lo es.<\/p>\n<\/blockquote>\n<p>Otra matriz interesante es la matriz laplaciana de un grafo simple no dirigido. <\/p>\n<blockquote>\n<p><strong>Definici\u00f3n<\/strong>: Denominamos matriz laplaciana de un grafo simple no dirigido \\(G(V,E), \\ V=\\{v_1, v_2, \\ldots, v_n\\}\\), a la matriz \\(\\mathcal{L}=[l_{ij}]\\) donde \\[l_{ij}=\\left\\{\\begin{array}{c,l}grado(v_i) &amp; \\mbox{si } i=j\\\\ -1 &amp; \\mbox{si } i\\neq j \\mbox{ y }\\{v_i,v_j\\}\\in E\\\\ 0 &amp; \\mbox{en otro caso }\\end{array}\\right.\\]<\/p>\n<\/blockquote>\n<p>Veamos algunas propiedades  interesantes :<\/p>\n<blockquote>\n<p><strong>Propiedades<\/strong>: Sea un grafo \\(G(V,E), \\ V=\\{v_1, v_2, \\ldots, v_n\\}\\), y \\(\\mathcal{L}\\) su matriz laplaciana, entonces<\/p>\n<ol>\n<li>\\(\\mathcal{L}\\) es una matriz real, sim\u00e9trica y semi-definida positiva(todos los valores propios no son inferiores a cero).<\/li>\n<li>El rango de \\(\\mathcal{L}\\)  es \\(n-k\\) donde \\(k\\)  es el n\u00famero de componentes conexas de \\(G\\) .<\/li>\n<li>Las sumas de las filas y columnas de \\(\\mathcal{L}\\) son zero.<\/li>\n<\/ol>\n<\/blockquote>\n<p>Podemos relacionar la matriz laplaciana de un grafo con su matriz de adyacencia:<\/p>\n<blockquote>\n<p><strong>Proposici\u00f3n<\/strong>: Sea \\(\\mathcal{L}\\) la matriz laplaciana de un grafo, y \\(\\mathcal{A}\\) su matriz de adyacencia. Sea \\(\\mathcal{D}\\) la matriz diagonal donde \\(d_{ii}=\\mathbf{gr}(v_i)\\), entonces \\[\\mathcal{L}=\\mathcal{D}-\\mathcal{A}\\]<\/p>\n<\/blockquote>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea G=(V,E), donde V={1,2,3,4,5}, y E={{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {4,5}}. Construir su matriz laplaciana y verificar el resultado anterior.<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1e() {\n  var htmlShow1e = document.getElementById(\"html-show1e\");\n  if (htmlShow1e.style.display === \"none\") {\n    htmlShow1e.style.display = \"block\";\n  } else {\n    htmlShow1e.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1e()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1e\" style=\"display: none;\">\n<!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i1)<\/span><\/td>\n<td><span class=\"input\"><span class=\"code_function\">load<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">graphs<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i5)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">v<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">3<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">4<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">5<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">a<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">[<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">2<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">3<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">4<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">5<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">3<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">4<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">5<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">3<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">4<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">4<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">5<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">g<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">create_graph<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">v<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">a<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">adjacency_matrix<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">g<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><!-- Text cell --><\/p>\n<div class=\"comment\">Para saber los grados aplicamos:<\/div>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i6)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">d<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">m<\/span><span class=\"code_endofline\">.<\/span><span class=\"code_function\">makelist<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">v<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\\begin{pmatrix}4\\\\4\\\\3\\\\4\\\\3\\end{pmatrix}\\]<\/p>\n<p><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i9)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">L<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_variable\">m<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_function\">makelist<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">L<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">d<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">v<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">L<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\\begin{bmatrix}4 &amp; -1 &amp; -1 &amp; -1 &amp; -1\\\\-1 &amp; 4 &amp; -1 &amp; -1 &amp; -1\\\\-1 &amp; -1 &amp; 3 &amp; -1 &amp; 0\\\\-1 &amp; -1 &amp; -1 &amp; 4 &amp; -1\\\\-1 &amp; -1 &amp; 0 &amp; -1 &amp; 3\\end{bmatrix}\\]<\/p>\n<\/div>\n<hr \/>\n<h3>Matriz Laplaciana en Digrafos<\/h3>\n<p>La forma m\u00e1s com\u00fan de definirla utiliza la matriz de grados de salida ($D_{out}$). Si tenemos un digrafo $G = (V, E)$, la matriz laplaciana $\\mathcal{L}$ se define como:$$\\mathcal{L} = D_{out} &#8211; A$$<br \/>\nDonde:<\/p>\n<ul>\n<li>$D_{out}$: Es una matriz diagonal donde cada elemento de la diagonal $d_{ii}$ es el n\u00famero de aristas que salen del nodo $i$.<\/li>\n<li>$A$: Es la matriz de adyacencia del digrafo, donde $A_{ij} = 1$ si existe un arco del nodo $i$ al nodo $j$, y $0$ en caso contrario.<\/li>\n<\/ul>\n<h3>Propiedades<\/h3>\n<blockquote><p><strong>Proposici\u00f3n<\/strong>: El n\u00famero de componentes conexas de un grafo G coincide con la multiplicidad del autovalor \\(\\mu_1= 0\\) de su matriz laplaciana\n<\/p><\/blockquote>\n<blockquote><p><strong>Corolario<\/strong>: Si G es un grafo conexo, la multiplicidad del autovalor \\(\\mu_1= 0\\) de la matriz laplaciana de G es 1.<\/p><\/blockquote>\n<blockquote><p><strong>Propiedad<\/strong>: Sea y \\(\\mathbf {B}\\) las matrices de incidencia (orientada) de un grafo o digrafo \\(G(V,E)\\), entonces \\[\\mathcal{L}=BB^t.\\]\n<\/p><\/blockquote>\n<table id=\"yzpi\" border=\"0\" width=\"100%\" cellspacing=\"0\" cellpadding=\"3\" bgcolor=\"#999999\">\n<tbody>\n<tr>\n<td width=\"100%\"><strong>Ejercicio:<\/strong> Dado el digrafo adjunto, \u00bfcu\u00e1ntos caminos de longitud 3 tiene?<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/uploads.jesussoto.es\/2022\/03\/grafo_comp_conexas2-300x141.png\" alt=\"\" width=\"300\" height=\"141\" class=\"aligncenter size-medium wp-image-1235\"\/><\/td>\n<\/tr>\n<tr>\n<td width=\"100%\" >\n<div id=\"menu-a\" >\n<ul>\n<li>23<\/li>\n<li>27<\/li>\n<li>32<\/li>\n<\/ul>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><script>\nfunction showHtmlDiv() {\n  var htmlShow = document.getElementById(\"html-show\");\n  if (htmlShow.style.display === \"none\") {\n    htmlShow.style.display = \"block\";\n  } else {\n    htmlShow.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show\" style=\"display: none;\">\n<p id=\"htmlContent\" class=\"text-html\"><strong>A.)<\/strong><\/p>\n<p>Sea \\(M\\) la matriz de adyacencia del grafo y \\(M^3=[m_{ij}]\\) su tercera potencia, entonces el n\u00famero de caminos de longitud tres ser\u00e1 \\[\\sum_{i=1}^8\\sum_{j=1}^8 m_{ij}=23\\]<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Sea \\(G(V,E)\\) un grafo simple y sin bucles con \\(|V|=n\\) y sea \\(A\\) la matriz \\(n\\times n\\) de adyacencia del grafo. Como la matriz es real y sim\u00e9trica, se puede diagonalizar mediante&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[9],"class_list":["post-1095","post","type-post","status-publish","format-standard","hentry","category-matematica-discreta","tag-practicas-mad"],"_links":{"self":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1095","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1095"}],"version-history":[{"count":7,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1095\/revisions"}],"predecessor-version":[{"id":1100,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1095\/revisions\/1100"}],"wp:attachment":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1095"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1095"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1095"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}