{"id":1038,"date":"2026-04-15T11:15:31","date_gmt":"2026-04-15T09:15:31","guid":{"rendered":"https:\/\/clases.jesussoto.es\/?p=1038"},"modified":"2026-04-01T13:10:45","modified_gmt":"2026-04-01T11:10:45","slug":"mad-isomorfismo-de-grafos-y-representacion-matricial-de-un-grafo","status":"publish","type":"post","link":"https:\/\/clases.jesussoto.es\/?p=1038","title":{"rendered":"MAD: Representaci\u00f3n matricial de un grafo"},"content":{"rendered":"<h2><strong>Matriz de adyacencia<\/strong><\/h2>\n<p>Si tenemos un grafo \\(G=(V,E)\\) donde \\(V=\\{v_1,\u2026,v_n\\}\\), llamamos matriz de adyacencia del grafo a la matriz cuadrada nxn, \\(A=[a_{ij}]\\), donde<br \/>\n\\[a_{ij}=\\left\\{\\begin{matrix}1 &amp; \\mbox{si } \\{v_i,v_j\\}\\in E\\\\ 0 &amp; \\mbox{si } \\{v_i,v_j\\}\\not\\in E\\end{matrix}\\right.\\]<\/p>\n<p>Si tenemos un digrafo \\(G=(V,E)\\) donde \\(V=\\{v_1,\u2026,v_n\\}\\), llamamos matriz de adyacencia del digrafo a la matriz cuadrada nxn, \\(A=[a_{ij}]\\), donde \\[a_{ij}=\\left\\{\\begin{matrix}1 &amp; \\mbox{si } (v_i,v_j)\\in E\\\\ 0 &amp; \\mbox{si } (v_i,v_j)\\not\\in E\\end{matrix}\\right.\\]\n<\/p>\n<p>Para ambos casos, si hubiera un bucle en \\(v_i\\) \\(a_{ii}\\) es 1 (dependiendo de la convenci\u00f3n usada, tambi\u00e9n puede aparecer 2). <\/p>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Determinar la matriz de adyacencia del grafo <br \/> <img decoding=\"async\" src=\"https:\/\/uploads.jesussoto.es\/grafos\/grafo_v5.png\" alt=\"\" height=\"150\" class=\"aligncenter size-medium wp-image-1235\"\/>\n<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1a() {\n  var htmlShow1a = document.getElementById(\"html-show1a\");\n  if (htmlShow1a.style.display === \"none\") {\n    htmlShow1a.style.display = \"block\";\n  } else {\n    htmlShow1a.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1a()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1a\" 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\">(%i4)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">load<\/span>(<span class=\"code_string\">\u00abgraphs\u00bb<\/span>)<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_variable\">v<\/span><span class=\"code_operator\">:<\/span>[<span class=\"code_number\">1<\/span>,<span class=\"code_number\">2<\/span>,<span class=\"code_number\">3<\/span>,<span class=\"code_number\">4<\/span>,<span class=\"code_number\">5<\/span>]<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_variable\">g<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">create_graph<\/span>(<span class=\"code_variable\">v<\/span>,<br \/> \u00a0 [[<span class=\"code_number\">1<\/span>,<span class=\"code_number\">2<\/span>],[<span class=\"code_number\">1<\/span>,<span class=\"code_number\">5<\/span>],<br \/> \u00a0\u00a0\u00a0\u00a0\u00a0 [<span class=\"code_number\">1<\/span>,<span class=\"code_number\">4<\/span>],[<span class=\"code_number\">2<\/span>,<span class=\"code_number\">3<\/span>],<br \/> \u00a0\u00a0\u00a0\u00a0\u00a0 [<span class=\"code_number\">3<\/span>,<span class=\"code_number\">5<\/span>],[<span class=\"code_number\">3<\/span>,<span class=\"code_number\">4<\/span>],<br \/> \u00a0\u00a0\u00a0\u00a0\u00a0 [<span class=\"code_number\">4<\/span>,<span class=\"code_number\">5<\/span>]])<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_function\">adjacency_matrix<\/span>( <span class=\"code_variable\">g<\/span>)<span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"center\"><mtd><mtext\/><\/mtd><mtd><mo>0 errores, 0 advertencias<\/mo><\/mtd><\/mlabeledtr><mlabeledtr columnalign=\"center\"><mtd><mtext\/><\/mtd><mtd><mo>0 errores, 0 advertencias<\/mo><\/mtd><\/mlabeledtr><\/mtable><\/math><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"center\"><mtd><mtext>(%o4) <\/mtext><\/mtd><mtd><mrow><mo>(<\/mo><mrow><mtable><mtr><mtd><mn>0<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><mtd><mn>0<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><\/mtr><mtr><mtd><mn>1<\/mn><\/mtd><mtd><mn>0<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><mtd><mn>0<\/mn><\/mtd><mtd><mn>0<\/mn><\/mtd><\/mtr><mtr><mtd><mn>0<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><mtd><mn>0<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><\/mtr><mtr><mtd><mn>1<\/mn><\/mtd><mtd><mn>0<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><mtd><mn>0<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><\/mtr><mtr><mtd><mn>1<\/mn><\/mtd><mtd><mn>0<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><mtd><mn>1<\/mn><\/mtd><mtd><mn>0<\/mn><\/mtd><\/mtr><\/mtable><\/mrow><mo>)<\/mo><\/mrow><\/mtd><\/mlabeledtr><\/mtable><\/math>\n<\/div>\n<hr \/>\n<blockquote><p><strong>Ejercicio:<\/strong> Crear una funci\u00f3n en maxima que, dada una lista de aristas, nos devuelva su matriz de adyacencia.<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv1a9() {\n  var htmlShow1a9 = document.getElementById(\"html-show1a9\");\n  if (htmlShow1a9.style.display === \"none\") {\n    htmlShow1a9.style.display = \"block\";\n  } else {\n    htmlShow1a9.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1a9()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1a9\" 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 style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_comment\">\/* Definici\u00f3n de la funci\u00f3n *\/<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_function\">matriz_adyacencia<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">aristas<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">dirigido<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">block<\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_operator\">[<\/span><span class=\"code_variable\">M<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">j<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_comment\">\/* 1. Creamos una matriz de ceros de tama\u00f1o n x n *\/<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">M<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">zeromatrix<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_comment\">\/* 2. Recorremos la lista de aristas para marcar las conexiones *\/<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">for <\/span><span class=\"code_variable\">k<\/span><span class=\"code_function\"> in <\/span><span class=\"code_variable\">aristas<\/span><span class=\"code_function\"> do <\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">i<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">k<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">j<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">k<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">2<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">M<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">j<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">M<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">j<\/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_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_function\">if <\/span><span class=\"code_function\">not <\/span><span class=\"code_variable\">dirigido <\/span><span class=\"code_function\">then <\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_function\">if <\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">#<\/span><span class=\"code_variable\">j<\/span><span class=\"code_function\"> then <\/span><span class=\"code_variable\">M<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">j<\/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\">M<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">j<\/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_number\">1<\/span><span class=\"code_function\"> else <\/span><span class=\"code_variable\">M<\/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\">M<\/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_number\">1<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">return<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">M<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<hr \/>\n<p>Veamos algunas propiedades interesantes<\/p>\n<blockquote>\n<p><strong>Propiedades<\/strong>: La matriz de adyacencia, \\(A\\), verifica:<\/p>\n<ul>\n<li>es sim\u00e9trica para un grafo no dirigido; <\/li>\n<li>Depende del etiquetado del grafo. Existe una correspondencia biyectiva entre los grafos simples etiquetados con \\(n\\) v\u00e9rtices y las matrices \\(n\\times n\\) sim\u00e9tricas binarias con ceros en la diagonal.<\/li>\n<li>no es binaria para un multigrafo.<\/li>\n<li>para un pseudografo, la diagonal principal no est\u00e1 formada \u00fanicamente por ceros.<\/li>\n<li>si un grafo tiene un v\u00e9rtice \\(v_i\\) aislado, tanto la columna \\(i-\u00e9sima\\) de \\(A\\) como la fila \\(i-\u00e9sima\\) estar\u00e1n formadas por ceros.<\/li>\n<li>si \\(G\\) es un grafo no dirigido, la suma de los elementos de la fila (o columna) \\(i-\u00e9sima\\) de \\(A\\) coincide con el grado del v\u00e9rtice \\(v_i\\). <\/li>\n<li>en un grafo no dirigido sin lazos, la suma de todos los elementos es el doble del tama\u00f1o del grafo, es decir, el doble del n\u00famero de aristas del grafo. En grafos dirigidos, la suma de todos los elementos de \\(A\\) da exactamente el tama\u00f1o del grafo<\/li>\n<\/ul>\n<\/blockquote>\n<p>Observar que una de las propiedades nos dec\u00eda que, en un grafo no dirigido, la suma de los elementos de la fila (o columna) \\(i-\u00e9sima\\) de \\(A\\) coincide con el grado del v\u00e9rtice \\(v_i\\). En general, podr\u00edamos decir que si \\(A\\) es la matriz de adyacencia de un grafo y \\(\\mathbf{1}\\) es la matriz columna de tantas filas como orden tiene \\(A\\), el producto \\[\\mathbf{d}=A.\\mathbf{1}\\] nos proporciona los grados de cada uno de los v\u00e9rtices del grafo.<\/p>\n<p>Si tenemos un digrafo \\[\\mathbf{d}_{out}=A.\\mathbf{1}\\] el vector de grados de salida.<\/p>\n<h3>Caminos y distancia<\/h3>\n<p>Otra propiedad interesante es la posibilidad de conocer los caminos de un v\u00e9rtice a otro. Si llamamos \\(C_{ij}(k)\\) el n\u00famero de caminos de longitud \\(k\\) entre los v\u00e9rtices \\(v_i\\) y \\(v_j\\), este se puede determinar mediante la potencia \\(k\\)-\u00e9sima de la matriz de adyacencia. Es decir, si \\(\\mathbf {A}=[a_{ij}]\\) es la matriz de adyacencia, \\[C_{i,j}(k)=[\\mathbf{A}^{k}]_{ij}.\\]<\/p>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Cu\u00e1ntos caminos de longitud 4 parten del v\u00e9rtice 1 del grafo anterior<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1b() {\n  var htmlShow1b = document.getElementById(\"html-show1b\");\n  if (htmlShow1b.style.display === \"none\") {\n    htmlShow1b.style.display = \"block\";\n  } else {\n    htmlShow1b.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1b()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1b\" 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\">(%i6)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">c4<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">^<\/span><span class=\"code_operator\">^<\/span><span class=\"code_number\">4<\/span><span class=\"code_endofline\">$<\/span><br \/><span class=\"code_function\">sum<\/span>(<span class=\"code_function\">row<\/span>(<span class=\"code_variable\">c4<\/span>,<span class=\"code_number\">1<\/span>)[<span class=\"code_number\">1<\/span>][<span class=\"code_variable\">i<\/span>],<span class=\"code_variable\">i<\/span>,<span class=\"code_number\">1<\/span>,<span class=\"code_number\">5<\/span>)<span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"left\"><mtd><mtext>(%o6) <\/mtext><\/mtd><mtd><mn>66<\/mn><\/mtd><\/mlabeledtr><\/mtable><\/math>\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea \\(G(V,E)\\), siendo \\(E:\\{\\{1,4\\},\\{1,2\\},\\{2,2\\},\\{1,3\\},\\{2,3\\}\\}\\) \u00bfQu\u00e9 dos v\u00e9rtices no est\u00e1n conectados por una camino de longitud 2?<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1cw2() {\n  var htmlShow1cw2 = document.getElementById(\"html-show1cw2\");\n  if (htmlShow1cw2.style.display === \"none\") {\n    htmlShow1cw2.style.display = \"block\";\n  } else {\n    htmlShow1cw2.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1cw2()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1cw2\" style=\"display: none;\">\nEs suficiente con ver que, si \\(A\\) es la matriz de adyacencia, solo necesitamos ver \\(A^2\\).\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea \\(G(V,E)\\), siendo \\(E:\\{\\{1,4\\},\\{1,2\\},\\{2,2\\},\\{1,3\\},\\{2,3\\}\\}\\) \u00bfCu\u00e1ntos caminos de longitud 3 hay?<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1cw() {\n  var htmlShow1cw = document.getElementById(\"html-show1cw\");\n  if (htmlShow1cw.style.display === \"none\") {\n    htmlShow1cw.style.display = \"block\";\n  } else {\n    htmlShow1cw.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1cw()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1cw\" style=\"display: none;\">\nEs suficiente con ver que si \\(A\\) es la matriz de adyacencia, entonces \\[A^3=\\begin{bmatrix}3 &#038; 6 &#038; 5 &#038; 3\\\\<br \/>\n6 &#038; 7 &#038; 5 &#038; 2\\\\<br \/>\n5 &#038; 5 &#038; 3 &#038; 1\\\\<br \/>\n3 &#038; 2 &#038; 1 &#038; 0\\end{bmatrix}\\] Ahora solo nos resta sumar todas las componentes.\n<\/div>\n<hr \/>\n<p>Cuando <strong>el grafo es simple<\/strong>, esta potencia nos sirve para ver el grado de cada v\u00e9rtice:<br \/>\n\\[grado(v_i)=[\\mathbf{A}^{2}]_{ii}.\\]<\/p>\n<p>Y como sabemos que \\(\\sum_{v\\in V} grado(v)=2|E|\\), tendremos \\[|E|=\\frac{1}{2}traza(\\mathbf{A}^{2}).\\]<\/p>\n<p>La tercera potencia tambi\u00e9n nos proporciona datos curiosos.<\/p>\n<blockquote>\n<p><strong>Propiedad<\/strong>: Si \\(\\mathbf {A}=[a_{ij}]\\) es la matriz de adyacencia de un grafo \\(G\\), el n\u00famero de tri\u00e1ngulos (circuitos de longitud 3)<\/p>\n<ul>\n<li>del grafo es \\[\\frac{1}{6}traza(\\mathbf{A}^{3})\\]<\/li>\n<li>que tienen a \\(v_i\\) como v\u00e9rtice es \\[\\frac{1}{2}\\left[\\mathbf{A}^{3}\\right]_{ii}\\]<\/li>\n<\/ul>\n<\/blockquote>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Cu\u00e1ntos tri\u00e1ngulos tiene el grafo completo \\(K_5\\)<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1c() {\n  var htmlShow1c = document.getElementById(\"html-show1c\");\n  if (htmlShow1c.style.display === \"none\") {\n    htmlShow1c.style.display = \"block\";\n  } else {\n    htmlShow1c.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1c()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1c\" 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\">(%i5)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">load<\/span>(<span class=\"code_string\">\u00abgraphs\u00bb<\/span>)<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_variable\">v<\/span><span class=\"code_operator\">:<\/span>[<span class=\"code_number\">1<\/span>,<span class=\"code_number\">2<\/span>,<span class=\"code_number\">3<\/span>,<span class=\"code_number\">4<\/span>,<span class=\"code_number\">5<\/span>]<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_variable\">a<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">create_list<\/span>([<span class=\"code_variable\">v<\/span>[<span class=\"code_variable\">i<\/span>],<span class=\"code_variable\">v<\/span>[<span class=\"code_variable\">j<\/span>]],<span class=\"code_variable\">i<\/span>,<span class=\"code_number\">1<\/span>,<span class=\"code_number\">4<\/span>,<span class=\"code_variable\">j<\/span>,<span class=\"code_variable\">i<\/span><span class=\"code_operator\">+<\/span><span class=\"code_number\">1<\/span>,<span class=\"code_number\">5<\/span>)<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_variable\">g<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">create_graph<\/span>(<span class=\"code_variable\">v<\/span>,<span class=\"code_variable\">a<\/span>)<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_function\">draw_graph<\/span>(<span class=\"code_variable\">g<\/span>,<br \/> \u00a0 <span class=\"code_variable\">show_id<\/span><span class=\"code_operator\">=<\/span>true,<br \/> \u00a0 <span class=\"code_variable\">show_vertices<\/span><span class=\"code_operator\">=<\/span><span class=\"code_variable\">v<\/span>,<br \/> \u00a0 <span class=\"code_variable\">show_vertex_size<\/span><span class=\"code_operator\">=<\/span><span class=\"code_number\">3<\/span>, \u00a0\u00a0\u00a0<br \/> \u00a0 <span class=\"code_variable\">edge_width<\/span><span class=\"code_operator\">=<\/span><span class=\"code_number\">1<\/span>)<span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"left\"><mtd><mtext\/><\/mtd><mtd><mo>0 errores, 0 advertencias<\/mo><\/mtd><\/mlabeledtr><mlabeledtr columnalign=\"left\"><mtd><mtext\/><\/mtd><mtd><mo>0 errores, 0 advertencias<\/mo><\/mtd><\/mlabeledtr><\/mtable><\/math><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"left\"><mtd><mtext>(%t5) <\/mtext><\/mtd><mtd\/><\/mlabeledtr><\/mtable><\/math><img decoding=\"async\" src=\"https:\/\/uploads.jesussoto.es\/grafos\/grafo_k5.png\" width=\"398\" style=\"max-width:90%;\" loading=\"lazy\" alt=\" (Gr\u00e1ficos) \" class=\"aligncenter size-medium wp-image-1235\"\/><br \/><!-- Code cell --><\/p>\n<table>\n<tr style=\"border: 0px;\">\n<td style=\"width: 70px;vertical-align: top;padding: 1mm;\"><span class=\"prompt\">(%i7)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">m<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">adjacency_matrix<\/span>(<span class=\"code_variable\">g<\/span>)<span class=\"code_endofline\">$<\/span><br \/><span class=\"code_function\">mat_trace<\/span>(<span class=\"code_variable\">m<\/span><span class=\"code_operator\">^<\/span><span class=\"code_operator\">^<\/span><span class=\"code_number\">3<\/span>)<span class=\"code_operator\">\/<\/span><span class=\"code_number\">6<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"left\"><mtd><mtext\/><\/mtd><mtd><mo>0 errores, 0 advertencias<\/mo><\/mtd><\/mlabeledtr><\/mtable><\/math><math xmlns=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"block\"><mtable><mlabeledtr columnalign=\"left\"><mtd><mtext>(%o7) <\/mtext><\/mtd><mtd><mn>10<\/mn><\/mtd><\/mlabeledtr><\/mtable><\/math>\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> \u00bfCu\u00e1ntos caminos de longitud 5 tiene el digrafo?<\/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\"\/><\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv1() {\n  var htmlShow1 = document.getElementById(\"html-show1\");\n  if (htmlShow1.style.display === \"none\") {\n    htmlShow1.style.display = \"block\";\n  } else {\n    htmlShow1.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1\" style=\"display: none;\">\nObservemos que la matriz de adyacencia es \\[A=\\begin{bmatrix}0 &#038; 1 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 1 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 0 &#038; 1 &#038; 0 &#038; 0 &#038; 1 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 1 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 1\\\\<br \/>\n1 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 1 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 1 &#038; 0 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 0 &#038; 1 &#038; 0 &#038; 0 &#038; 0 &#038; 0\\end{bmatrix}\\]<br \/>\nSi hacemos la quinta potencia tendremos:<br \/>\n\\[A^5=[\\alpha_{ij}]=\\begin{bmatrix}0 &#038; 0 &#038; 0 &#038; 2 &#038; 0 &#038; 0 &#038; 2 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 2 &#038; 0 &#038; 0 &#038; 2 &#038; 0 &#038; 2\\\\<br \/>\n0 &#038; 0 &#038; 0 &#038; 4 &#038; 0 &#038; 0 &#038; 4 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 4 &#038; 0 &#038; 0 &#038; 3 &#038; 0 &#038; 4\\\\<br \/>\n0 &#038; 0 &#038; 1 &#038; 0 &#038; 0 &#038; 1 &#038; 0 &#038; 1\\\\<br \/>\n0 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 1 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 0 &#038; 0 &#038; 0 &#038; 1 &#038; 0 &#038; 0\\\\<br \/>\n0 &#038; 0 &#038; 0 &#038; 4 &#038; 0 &#038; 0 &#038; 3 &#038; 0\\end{bmatrix}\\]<br \/>\nAhora solo necesitamos sumar todos los valores de la matriz \\[\\sum_{i=1}^8\\sum_{j=1}^8\\alpha_{ij}\\]\n<\/div>\n<hr \/>\n<blockquote><p>\n<strong>Proposici\u00f3n:<\/strong> El di\u00e1metro de un grafo es el valor $k$ m\u00e1s peque\u00f1o necesario para que la matriz sumatoria de potencias, de su matriz de adyacencia, no tenga ceros.\n<\/p><\/blockquote>\n<h3>Isomorfismos y adyacencia<\/h3>\n<blockquote>\n<p><strong>Propiedad<\/strong>: Sean \\(\\mathbf {A}\\) y \\(\\mathbf {A^\\prime}\\) las matrices de adyacencia de los grafos \\(G\\) y \\(G^\\prime\\), entonces las siguientes condiciones son equivalentes:<\/p>\n<ul>\n<li>\\(G\\equiv G^\\prime\\) (isomorfos)<\/li>\n<li>Existe una matriz \\(P\\), matriz de permutaciones, tal que \\(A^\\prime=PAP^{t}\\) <\/li>\n<\/ul>\n<\/blockquote>\n<blockquote>\n<p><strong>Propiedad<\/strong>: Sea \\(\\mathbf {A}\\) la matriz de adyacencia de un grafo \\(G(V,E)\\), con \\(|V|=n\\), entonces las siguientes condiciones son equivalentes:<\/p>\n<ul>\n<li>\\(G\\) es conexo<\/li>\n<li>son mayores que cero las entradas de la matriz \\[I_{n}+A+A^{2}+A^{3}+\\ldots+A^{n-1}\\]<\/li>\n<\/ul>\n<\/blockquote>\n<blockquote>\n<p><strong>Propiedad<\/strong>: Sea \\(\\mathbf {A}\\) la matriz de adyacencia de un grafo \\(G\\), y \\(P\\), una matriz de permutaciones, tal que \\(PAP^{t}\\) es una matriz diagonal por bloques; entonces:<\/p>\n<ol>\n<li>El n\u00famero de componentes conexas del grafo es igual n\u00famero de bloques.<\/li>\n<li>\\(G\\) es conexo si, y solo si, el n\u00famero de bloques es 1.<\/li>\n<\/ol>\n<\/blockquote>\n<h2><strong>Matriz de incidencia<\/strong><\/h2>\n<p>Del mismo modo podemos construir la <strong>matriz de incidencia<\/strong>, donde las columnas de la matriz representan las aristas del grafo y las filas representan a los distintos nodos. <\/p>\n<h3><strong>Grafo no dirigido<\/strong><\/h3>\n<p> Utilizando la terminolog\u00eda anterior, llamamos <strong>matriz de incidencia<\/strong> del grafo no dirigido a la matriz \\(|V|\\times |E|\\), \\(M=[m_{ij}]\\), donde<br \/>\n\\[m_{ij}=\\left\\{\\begin{array}{ll}0 &amp; \\mbox{si } \\not\\exists v\\in V|\\ e_j=\\{v_i,v\\}\\in E\\\\ 1 &amp; \\mbox{si } \\exists v\\in V|\\ e_j=\\{v_i,v\\}\\in E\\\\ 2 &amp; \\mbox{si } \\ e_j=\\{v_i,v_i\\}\\in E\\end{array}\\right.\\]<\/p>\n<h3><strong>Grafo dirigido<\/strong><\/h3>\n<p>\\[m_{ij}=\\left\\{\\begin{array}{ll}0 &amp; \\mbox{si } \\not\\exists v\\in V|\\ e_j=(v_i,v)\\in E\\\\ 1 &amp; \\mbox{si } \\exists v\\in V|\\ e_j=(v_i,v)\\in E\\\\ -1 &amp; \\mbox{si } \\exists v\\in V|\\ e_j=(v,v_i)\\in E\\end{array}\\right.\\]<br \/>\nObservar que un bucle entra y sale del mismo v\u00e9rtice, luego contribuye +1 y \u22121, por tanto es cero.<\/p>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> \u00bfCu\u00e1l es la norma de la matriz de incidencia del digrafo?<\/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\"\/><\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv1rt() {\n  var htmlShow1rt = document.getElementById(\"html-show1rt\");\n  if (htmlShow1rt.style.display === \"none\") {\n    htmlShow1rt.style.display = \"block\";\n  } else {\n    htmlShow1rt.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1rt()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1rt\" 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\">(%i5)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">n<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">8<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">E<\/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\">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\">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\">3<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">7<\/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\">3<\/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\">8<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">5<\/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_operator\">[<\/span><span class=\"code_number\">6<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">7<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">7<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">6<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">8<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">4<\/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\">m<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">zeromatrix<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">E<\/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_function\">for<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">1<\/span><span class=\"code_function\">thru<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">)<\/span><span class=\"code_function\">do<\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">m<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/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_operator\">]<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">m<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">2<\/span><span class=\"code_operator\">]<\/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_number\">1<\/span><span class=\"code_endofline\"><br \/><\/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_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\begin{pmatrix}-1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0\\\\1 &amp; -1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\\\0 &amp; 1 &amp; -1 &amp; -1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\\\0 &amp; 0 &amp; 1 &amp; 0 &amp; -1 &amp; -1 &amp; 0 &amp; 0 &amp; 0 &amp; 1\\\\0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1 &amp; 0 &amp; 0 &amp; 0\\\\0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1 &amp; 1 &amp; 0\\\\0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; -1 &amp; 0\\\\0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; -1\\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\">(%i6)<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">sqrt<\/span><span class=\"code_operator\">(<\/span><span class=\"code_function\">mat_trace<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">m<\/span><span class=\"code_endofline\">.<\/span><span class=\"code_function\">transpose<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">numer<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[4.47213595499958\\]<\/p>\n<p>Recordad que la norma de una matriz es independiente del orden en el que coloquemos las columnas.\n<\/p><\/div>\n<hr \/>\n<blockquote><p><strong>Ejercicio:<\/strong> Crear una funci\u00f3n en maxima que, dada una lista de aristas, nos devuelva su matriz de incidencia.<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv1a6() {\n  var htmlShow1a6 = document.getElementById(\"html-show1a6\");\n  if (htmlShow1a6.style.display === \"none\") {\n    htmlShow1a6.style.display = \"block\";\n  } else {\n    htmlShow1a6.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1a6()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1a6\" 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 style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">m_inc<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">block<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">n<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">0<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">for <\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">1<\/span><span class=\"code_function\"> thru <\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">)<\/span><span class=\"code_function\"> do <\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">n<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">max<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">max<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">2<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">m<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">zeromatrix<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">for <\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">1<\/span><span class=\"code_function\"> thru <\/span><span class=\"code_function\">length<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">)<\/span><span class=\"code_function\"> do <\/span><span class=\"code_operator\">(<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">m<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/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_operator\">]<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_variable\">m<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">2<\/span><span class=\"code_operator\">]<\/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_number\">1<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <span class=\"code_function\"> if <\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">=<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">2<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">)<\/span><span class=\"code_function\"> then <\/span><span class=\"code_variable\">m<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/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_operator\">]<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">m<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>Si el grafo fuese dirigido, entonces el bucle contar\u00eda como cero y tendr\u00edamos una columna de ceros en la arista correspondiente.\n<\/p><\/div>\n<hr \/>\n<h3><strong>Matriz de incidencia y conexi\u00f3n<\/strong><\/h3>\n<p>La matriz de incidencia nos permite conocer las componentes conexas de un grafo.<\/p>\n<blockquote>\n<p><strong>Propiedad: <\/strong>Sea \\(\\mathbf{M}\\) la matriz de incidencia de un digrafo \\(G(V,E)\\), con \\(|V|=n\\), entonces \\[\\mathbf{rang}(M)=n-c\\] siendo \\(c\\) el n\u00famero de componentes conexas del digrafo.<\/p>\n<\/blockquote>\n<p>Observar que hemos dado esta propiedad para un digrafo. Del mismo modo podemos establecerla para un grafo no dirigido, pero en este caso es m\u00e1s sencillo si orientamos artificialmente el grafo.<\/p>\n<blockquote>\n<p><strong>Definici\u00f3n: <\/strong>\\(G(V,E)\\) un grafo no dirigido; llamaremos matriz de incidencia orientada <strong>B<\/strong> del grafo \\(G(V,E)\\) a la matriz de incidencia resultante de darle una orientaci\u00f3n a las aristas del grafo. Es decir, lo transformamos en un digrafo.<\/p>\n<\/blockquote>\n<p>Esta orientaci\u00f3n es arbitraria, no modifica las propiedades algebraicas que nos interesan del grafo y nos permite interpretarlas de una forma m\u00e1s sencilla. Por ejemplo, ahora podemos repetir la propiedad anterior:<\/p>\n<blockquote>\n<p><strong>Propiedad: <\/strong>Sea \\(\\mathbf{B}\\) la matriz de incidencia orientada de un grafo \\(G(V,E)\\), con \\(|V|=n\\), entonces \\[\\mathbf{rang}(B)=n-c\\] siendo \\(c\\) el n\u00famero de componentes conexas del grafo.<\/p>\n<\/blockquote>\n<p>Si tenemos un digrafo, la matriz \\(\\mathbf{B}\\) (matriz de incidencia orientada) es la misma, ya que el digrafo est\u00e1 orientado.<\/p>\n<h3><strong>Matriz de incidencia y adyacencia<\/strong><\/h3>\n<blockquote>\n<p><strong>Propiedad<\/strong>: Sean \\(\\mathbf {A}\\) y \\(\\mathbf {B}\\) las matrices de adyacencia e incidencia (orientada) de un grafo o digrafo \\(G(V,E)\\), entonces \\[D-A=BB^t,\\] siendo \\(D\\) una matriz diagonal cuyos elementos de la diagonal son los grados de los v\u00e9rtices correspondientes.<\/p>\n<\/blockquote>\n<p>Para obtener la matriz de grados ($D$) a partir de la matriz de adyacencia ($A$), la forma m\u00e1s eficiente y universal, v\u00e1lida tanto para grafos dirigidos como no dirigidos, es multiplicar la matriz $A$ por un vector columna de unos ($\\mathbf{1}$), el resultado es un vector donde cada componente es la suma de la fila correspondiente.<\/p>\n<p>Para un grafo de $n$ nodos, sea $\\mathbf{1} = [1, 1, \\dots, 1]^T$:$$\\mathbf{d} = A\\mathbf{1}$$ donde $\\mathbf{d}$ es el vector de grados. Para convertir este vector en la matriz diagonal $D$, usamos el operador $\\text{diag}$: $$D = \\text{diag}(A\\mathbf{1})$$<\/p>\n<div style=\"overflow-x:auto;\">\n<table style=\"width:100%; border-collapse: collapse; margin: 20px 0; font-family: sans-serif; min-width: 400px; border: 1px solid #ddd;\">\n<thead>\n<tr style=\"background-color: #f2f2f2; text-align: left;\">\n<th style=\"padding: 12px 15px; border-bottom: 2px solid #4CAF50;\">Tipo de Grafo<\/th>\n<th style=\"padding: 12px 15px; border-bottom: 2px solid #4CAF50;\">Definici\u00f3n de \\( D \\)<\/th>\n<th style=\"padding: 12px 15px; border-bottom: 2px solid #4CAF50;\">Requisito \/ Nota<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr style=\"border-bottom: 1px solid #eee;\">\n<td style=\"padding: 12px 15px;\"><strong>Cualquiera<\/strong><\/td>\n<td style=\"padding: 12px 15px;\">\\( D = \\text{diag}(A\\mathbf{1}) \\)<\/td>\n<td style=\"padding: 12px 15px;\">M\u00e9todo universal (el m\u00e1s robusto).<\/td>\n<\/tr>\n<tr style=\"border-bottom: 1px solid #eee; background-color: #f9f9f9;\">\n<td style=\"padding: 12px 15px;\"><strong>No dirigido<\/strong><\/td>\n<td style=\"padding: 12px 15px;\">\\( D = \\text{diag}(\\text{diag}(A^2)) \\)<\/td>\n<td style=\"padding: 12px 15px;\">Debe ser un grafo <strong>simple<\/strong> (sin bucles).<\/td>\n<\/tr>\n<tr style=\"border-bottom: 1px solid #eee;\">\n<td style=\"padding: 12px 15px;\"><strong>Dirigido (Out-degree)<\/strong><\/td>\n<td style=\"padding: 12px 15px;\">\\( D_{out} = \\text{diag}(A\\mathbf{1}) \\)<\/td>\n<td style=\"padding: 12px 15px;\">Suma por filas (aristas que salen).<\/td>\n<\/tr>\n<tr style=\"border-bottom: 1px solid #eee; background-color: #f9f9f9;\">\n<td style=\"padding: 12px 15px;\"><strong>Dirigido (In-degree)<\/strong><\/td>\n<td style=\"padding: 12px 15px;\">\\( D_{in} = \\text{diag}(\\mathbf{1}^T A) \\)<\/td>\n<td style=\"padding: 12px 15px;\">Suma por columnas (aristas que entran).<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<blockquote><p>\n<strong>Ejercicio:<\/strong> Dado el grafo adjunto, verificar la relaci\u00f3n anterior. <\/p>\n<div id=\"miGrafo21Cytoscape\" style=\"width: 500px; height: 300px;\"><\/div>\n<p><!-- [grafo_cytoscape] esto es necesario para que se vean los grafos--><br \/>\n<script>\ndocument.addEventListener('DOMContentLoaded', function() {\n  const container = document.getElementById('miGrafo21Cytoscape');\n  if (container) {\n    const cy = cytoscape({\n      container: container,\n      elements: [\n          { data: { id: 'n1', label: '1' } },\n          { data: { id: 'n2', label: '2' } },\n          { data: { id: 'n3', label: '3' } },\n          { data: { id: 'n4', label: '4' } },\n          { data: { source: 'n1', target: 'n2', label: '' } },\n          { data: { source: 'n2', target: 'n3', label: '' } },\n          { data: { source: 'n2', target: 'n4', label: '' } },\n          { data: { source: 'n2', target: 'n4', label: '' } },\n          { data: { source: 'n4', target: 'n4', label: '' } },\n          { data: { source: 'n1', target: 'n3', label: '' } }  ],\n      style: [\n          {\n            selector: 'node',\n            style: {\n              'background-color': '#000',\n              'label': 'data(label)',\n              'width': 15,  \/\/ Establece el ancho del nodo a 30 p\u00edxeles\n              'height': 15 \/\/ Establece la altura del nodo a 30 p\u00edxeles\n            }\n          },\n          {\n            selector: 'edge',\n            style: {\n              'width': 2,\n              'line-color': 'blue',\n              'label': 'data(label)',\n              'curve-style': 'bezier',\n              'target-arrow-shape': 'none' \/\/ triangle si es un grafo dirigido\n            }\n          }\n        ],\n        layout: {\n        name: 'grid'\n      },\n      zoomingEnabled: false \/\/ Deshabilita el zoom con la rueda del rat\u00f3n \n    });\n  } else {\n    console.error(\"No se encontr\u00f3 el contenedor con el ID 'miGrafo1Cytoscape'\");\n  }\n});\n<\/script><\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1rt5() {\n  var htmlShow1rt5 = document.getElementById(\"html-show1rt5\");\n  if (htmlShow1rt5.style.display === \"none\") {\n    htmlShow1rt5.style.display = \"block\";\n  } else {\n    htmlShow1rt5.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1rt5()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1rt5\" style=\"display: none;\">\n<!-- Text cell --><\/p>\n<div class=\"comment\">Utilizaremos la funciones para determinar las matrices de adyacencia e incidencia anteriores. <br \/> Demos una orientaci\u00f3n arbitraria y calculamos la matriz de incidencia orientada:<\/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\">(%i4) <\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">E<\/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\">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\">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\">4<\/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\">B<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">m_inc<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\\begin{bmatrix}-1 &amp; -1 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\\\1 &amp; 0 &amp; -1 &amp; -1 &amp; -1 &amp; 0\\\\0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0\\\\0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0\\end{bmatrix}\\]<\/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\">(%i5) <\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_variable\">B<\/span><span class=\"code_endofline\">.<\/span><span class=\"code_function\">transpose<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">B<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\\begin{bmatrix}2 &amp; -1 &amp; -1 &amp; 0\\\\-1 &amp; 4 &amp; -1 &amp; -2\\\\-1 &amp; -1 &amp; 2 &amp; 0\\\\0 &amp; -2 &amp; 0 &amp; 2\\end{bmatrix}\\]<\/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\">(%i8) <\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">m_grados<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">)<\/span><span class=\"code_operator\">:<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">block<\/span><span class=\"code_operator\">(<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">D<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">I1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">D<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">zeromatrix<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_variable\">I1<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">matriz_adyacencia<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">n<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">E<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">false<\/span><span class=\"code_operator\">)<\/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_variable\">n<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">,<\/span> \u00a0 <span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">for <\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">:<\/span><span class=\"code_number\">1<\/span><span class=\"code_function\"> thru <\/span><span class=\"code_variable\">n<\/span><span class=\"code_function\"> do <\/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_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">I1<\/span><span class=\"code_operator\">[<\/span><span class=\"code_variable\">i<\/span><span class=\"code_operator\">]<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">1<\/span><span class=\"code_operator\">]<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0\u00a0 <span class=\"code_function\">return<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">D<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\"><br \/><\/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_function\">matriz_adyacencia<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">4<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">E<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_function\">false<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">D<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">m_grados<\/span><span class=\"code_operator\">(<\/span><span class=\"code_number\">4<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_variable\">E<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\\begin{bmatrix}0 &amp; 1 &amp; 1 &amp; 0\\\\1 &amp; 0 &amp; 1 &amp; 2\\\\1 &amp; 1 &amp; 0 &amp; 0\\\\0 &amp; 2 &amp; 0 &amp; 2\\end{bmatrix}\\]<\/p>\n<p>\\[\\operatorname{ }\\begin{bmatrix}2 &amp; 0 &amp; 0 &amp; 0\\\\0 &amp; 4 &amp; 0 &amp; 0\\\\0 &amp; 0 &amp; 2 &amp; 0\\\\0 &amp; 0 &amp; 0 &amp; 4\\end{bmatrix}\\]<\/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\">D<\/span><span class=\"code_operator\">\u2212<\/span><span class=\"code_variable\">A<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\\begin{bmatrix}2 &amp; -1 &amp; -1 &amp; 0\\\\-1 &amp; 4 &amp; -1 &amp; -2\\\\-1 &amp; -1 &amp; 2 &amp; 0\\\\0 &amp; -2 &amp; 0 &amp; 2\\end{bmatrix}\\]<\/p>\n<\/div>\n<hr \/>\n<p>Si el grafo es simple, tendr\u00edamos:<\/p>\n<blockquote>\n<p><strong>Propiedad<\/strong>: Sean \\(\\mathbf {A}\\) y \\(\\mathbf {M}\\) las matrices de adyacencia e incidencia (no orientada) de un grafo simple \\(G(V,E)\\), entonces \\[A+D=MM^t,\\] siendo \\(D\\) una matriz diagonal cuyos elementos de la diagonal son los grados de los v\u00e9rtices correspondientes.<\/p>\n<\/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> Valore la afirmaci\u00f3n: <\/p>\n<p style=\"font-family: Arial, sans-serif;text-align: center;font-size: 16px; margin: 10px 10px;\"><strong><em>Todo grafo bipartido es conexo<\/em><\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td width=\"100%\" >\n<div id=\"menu-a\" >\n<ul>\n<li>Verdadero<\/li>\n<li>Falso<\/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\">Hay que trabajarla un poco m\u00e1s antes de que veas la respuesta.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Matriz de adyacencia Si tenemos un grafo \\(G=(V,E)\\) donde \\(V=\\{v_1,\u2026,v_n\\}\\), llamamos matriz de adyacencia del grafo a la matriz cuadrada nxn, \\(A=[a_{ij}]\\), donde \\[a_{ij}=\\left\\{\\begin{matrix}1 &amp; \\mbox{si } \\{v_i,v_j\\}\\in E\\\\ 0 &amp; \\mbox{si&#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-1038","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\/1038","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=1038"}],"version-history":[{"count":23,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1038\/revisions"}],"predecessor-version":[{"id":1091,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1038\/revisions\/1091"}],"wp:attachment":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1038"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1038"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1038"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}