{"id":1107,"date":"2026-04-27T10:18:57","date_gmt":"2026-04-27T08:18:57","guid":{"rendered":"https:\/\/clases.jesussoto.es\/?p=1107"},"modified":"2026-04-27T17:35:33","modified_gmt":"2026-04-27T15:35:33","slug":"mad-grafos-eulerianos-hamiltonianos-planos-mapas-regiones-y-coloracion-de-grafos","status":"publish","type":"post","link":"https:\/\/clases.jesussoto.es\/?p=1107","title":{"rendered":"MAD: Grafos Eulerianos, Hamiltonianos, planos, mapas, regiones y coloraci\u00f3n de grafos"},"content":{"rendered":"<h2>Grafos Eulerianos<\/h2>\n<p>Un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. Un grafo se denomina grafo euleriano si tiene un circuito euleriano.<\/p>\n<p><iframe loading=\"lazy\" title=\"Matem\u00e1tica Discreta - Grafos Eulerianos - Jes\u00fas Soto\" width=\"640\" height=\"360\" src=\"https:\/\/www.youtube.com\/embed\/zbOUAsoUoPg?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<blockquote><p><strong>Ejercicio:<\/strong> Determinar si el grafo siguiente tiene un camino euleriano.<br \/>\n<svg width=\"420\" height=\"520\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\">\n  <!-- edges -->\n  <line x1=\"100\" y1=\"80\" x2=\"300\" y2=\"80\" stroke=\"#333\" stroke-width=\"3\"\/>\n  <line x1=\"100\" y1=\"80\" x2=\"200\" y2=\"180\" stroke=\"#333\" stroke-width=\"3\"\/>\n  <line x1=\"300\" y1=\"80\" x2=\"200\" y2=\"180\" stroke=\"#333\" stroke-width=\"3\"\/>\n  <line x1=\"300\" y1=\"80\" x2=\"200\" y2=\"280\" stroke=\"#333\" stroke-width=\"3\"\/>\n  <line x1=\"200\" y1=\"180\" x2=\"200\" y2=\"280\" stroke=\"#333\" stroke-width=\"3\"\/>\n  <line x1=\"200\" y1=\"280\" x2=\"120\" y2=\"420\" stroke=\"#333\" stroke-width=\"3\"\/>\n  <line x1=\"120\" y1=\"420\" x2=\"280\" y2=\"420\" stroke=\"#333\" stroke-width=\"3\"\/>\n  <line x1=\"280\" y1=\"420\" x2=\"200\" y2=\"280\" stroke=\"#333\" stroke-width=\"3\"\/>\n  <!-- vertices -->\n  <g font-family=\"Arial\" font-size=\"14\" text-anchor=\"middle\" fill=\"#000\">\n    <circle cx=\"100\" cy=\"80\" r=\"18\" fill=\"#ffd\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"100\" y=\"86\">v1<\/text>\n    <circle cx=\"300\" cy=\"80\" r=\"18\" fill=\"#ffd\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"300\" y=\"86\">v2<\/text>\n    <circle cx=\"200\" cy=\"180\" r=\"18\" fill=\"#ffd\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"200\" y=\"186\">v3<\/text>\n    <circle cx=\"200\" cy=\"280\" r=\"18\" fill=\"#ffd\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"200\" y=\"286\">v4<\/text>\n    <circle cx=\"120\" cy=\"420\" r=\"18\" fill=\"#ffd\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"120\" y=\"426\">v5<\/text>\n    <circle cx=\"280\" cy=\"420\" r=\"18\" fill=\"#ffd\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"280\" y=\"426\">v6<\/text>\n  <\/g>\n<\/svg>\n<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv1aw5() {\n  var htmlShow1aw5 = document.getElementById(\"html-show1aw5\");\n  if (htmlShow1aw5.style.display === \"none\") {\n    htmlShow1aw5.style.display = \"block\";\n  } else {\n    htmlShow1aw5.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1aw55()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1aw5\" style=\"display: none;\">\n<svg width=\"420\" height=\"520\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\">\n  <!-- fondo blanco -->\n  <rect width=\"100%\" height=\"100%\" fill=\"#ffffff\"\/>\n  <!-- aristas (fondo, gris claro) -->\n  <g stroke=\"#cccccc\" stroke-width=\"3\" stroke-linecap=\"round\">\n    <line x1=\"100\" y1=\"80\"  x2=\"300\" y2=\"80\"\/>\n    <line x1=\"100\" y1=\"80\"  x2=\"200\" y2=\"180\"\/>\n    <line x1=\"300\" y1=\"80\"  x2=\"200\" y2=\"180\"\/>\n    <line x1=\"300\" y1=\"80\"  x2=\"200\" y2=\"280\"\/>\n    <line x1=\"200\" y1=\"180\" x2=\"200\" y2=\"280\"\/>\n    <line x1=\"200\" y1=\"280\" x2=\"120\" y2=\"420\"\/>\n    <line x1=\"120\" y1=\"420\" x2=\"280\" y2=\"420\"\/>\n    <line x1=\"280\" y1=\"420\" x2=\"200\" y2=\"280\"\/>\n  <\/g>\n  <!-- aristas del camino (superpuestas, color destacado) -->\n  <g stroke=\"#d32f2f\" stroke-width=\"6\" stroke-linecap=\"round\">\n    <!-- 1: v2 - v4 -->\n    <line x1=\"300\" y1=\"80\"  x2=\"200\" y2=\"280\"\/>\n    <!-- 2: v4 - v5 -->\n    <line x1=\"200\" y1=\"280\" x2=\"120\" y2=\"420\"\/>\n    <!-- 3: v5 - v6 -->\n    <line x1=\"120\" y1=\"420\" x2=\"280\" y2=\"420\"\/>\n    <!-- 4: v6 - v4 -->\n    <line x1=\"280\" y1=\"420\" x2=\"200\" y2=\"280\"\/>\n    <!-- 5: v4 - v3 -->\n    <line x1=\"200\" y1=\"280\" x2=\"200\" y2=\"180\"\/>\n    <!-- 6: v3 - v1 -->\n    <line x1=\"200\" y1=\"180\" x2=\"100\" y2=\"80\"\/>\n    <!-- 7: v1 - v2 -->\n    <line x1=\"100\" y1=\"80\"  x2=\"300\" y2=\"80\"\/>\n    <!-- 8: v2 - v3 -->\n    <line x1=\"300\" y1=\"80\"  x2=\"200\" y2=\"180\"\/>\n  <\/g>\n  <!-- numeraci\u00f3n de pasos sobre las aristas -->\n  <g font-family=\"Arial\" font-size=\"12\" fill=\"#000\" text-anchor=\"middle\">\n    <text x=\"250\" y=\"180\">1<\/text> <!-- v2-v4 -->\n    <text x=\"160\" y=\"350\">2<\/text> <!-- v4-v5 -->\n    <text x=\"200\" y=\"420\">3<\/text> <!-- v5-v6 -->\n    <text x=\"240\" y=\"350\">4<\/text> <!-- v6-v4 -->\n    <text x=\"200\" y=\"230\">5<\/text> <!-- v4-v3 -->\n    <text x=\"150\" y=\"130\">6<\/text> <!-- v3-v1 -->\n    <text x=\"200\" y=\"80\">7<\/text>  <!-- v1-v2 -->\n    <text x=\"250\" y=\"130\">8<\/text> <!-- v2-v3 -->\n  <\/g>\n  <!-- v\u00e9rtices (c\u00edrculos) -->\n  <g font-family=\"Arial\" font-size=\"14\" text-anchor=\"middle\" fill=\"#000\">\n    <!-- v1 -->\n    <circle cx=\"100\" cy=\"80\" r=\"18\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"100\" y=\"86\">v1<\/text>\n    <!-- v2 (inicio: verde) -->\n    <circle cx=\"300\" cy=\"80\" r=\"18\" fill=\"#c8e6c9\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"300\" y=\"86\">v2<\/text>\n    <!-- v3 (final: naranja) -->\n    <circle cx=\"200\" cy=\"180\" r=\"18\" fill=\"#ffcc80\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"200\" y=\"186\">v3<\/text>\n    <!-- v4 -->\n    <circle cx=\"200\" cy=\"280\" r=\"18\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"200\" y=\"286\">v4<\/text>\n    <!-- v5 -->\n    <circle cx=\"120\" cy=\"420\" r=\"18\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"120\" y=\"426\">v5<\/text>\n    <!-- v6 -->\n    <circle cx=\"280\" cy=\"420\" r=\"18\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"280\" y=\"426\">v6<\/text>\n  <\/g>\n  <!-- leyenda -->\n  <g font-family=\"Arial\" font-size=\"12\" fill=\"#000\" text-anchor=\"start\">\n    <rect x=\"18\" y=\"450\" width=\"16\" height=\"10\" fill=\"#d32f2f\" stroke=\"#000\" stroke-width=\"0.5\"\/>\n    <text x=\"40\" y=\"459\">Camino euleriano (orden numerado)<\/text>\n    <rect x=\"18\" y=\"472\" width=\"16\" height=\"10\" fill=\"#c8e6c9\" stroke=\"#000\" stroke-width=\"0.5\"\/>\n    <text x=\"40\" y=\"481\">V\u00e9rtice inicio \\(v_2\\)<\/text>\n    <rect x=\"18\" y=\"494\" width=\"16\" height=\"10\" fill=\"#ffcc80\" stroke=\"#000\" stroke-width=\"0.5\"\/>\n    <text x=\"40\" y=\"503\">V\u00e9rtice final \\(v_3\\)<\/text>\n  <\/g>\n<\/svg>\n<\/div>\n<hr \/>\n<h3>Propiedades de los grafo eulerianos:<\/h3>\n<ul>\n<li>Un grafo conexo y no dirigido se dice que es euleriano si cada v\u00e9rtice tiene un grado par.<\/li>\n<li>Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los v\u00e9rtices disjuntos.<\/li>\n<li>Si un grafo no dirigido G es euleriano entonces su grafo-l\u00ednea L(G) se dice que es tambi\u00e9n euleriano.<\/li>\n<li>Un grafo dirigido es euleriano si es conexo y cada v\u00e9rtice tiene grados internos iguales a los externos.<\/li>\n<li>Un grafo no dirigido se dice que es susceptible de ser recorrido si es conexo y dos v\u00e9rtices en el grafo tienen grado impar.<\/li>\n<\/ul>\n<p>El siguiente resultado nos sirve para determinar si un grafo contiene un camino euleriano o un ciclo:<\/p>\n<blockquote>\n<p><strong>Teorema<\/strong>: Dado un grafo conexo (no existen nodos aislados) y no dirigido G, si G tiene exactamente dos v\u00e9rtices de grado impar, entonces G tiene un camino euleriano no cerrado. En caso de que todos los v\u00e9rtices tengan grado par, G tiene un ciclo euleriano.<\/p>\n<\/blockquote>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea \\(G=(V,E)\\), donde \\(V\\)={1,2,3,4,5,6}, \\(E\\)={{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,6}, {4,5}, {5,6}}, a) tiene un camino euleriano, \u00bfcu\u00e1l es?; b) tiene un ciclo euleriano, \u00bfcu\u00e1l es?.<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1aw() {\n  var htmlShow1aw = document.getElementById(\"html-show1aw\");\n  if (htmlShow1aw.style.display === \"none\") {\n    htmlShow1aw.style.display = \"block\";\n  } else {\n    htmlShow1aw.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1aw()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1aw\" 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)\t<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">load<\/span><span class=\"code_operator\">(<\/span><span class=\"code_string\">&quot;graphs&quot;<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{\t}\u00bb..\/maxima\/5.45.1\/share\/graphs\/graphs.mac\u00bb\\]<\/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)\t<\/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_function\">makelist<\/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_endofline\">,<\/span><span class=\"code_number\">1<\/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_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\">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\">3<\/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\">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_operator\">[<\/span><span class=\"code_number\">5<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">6<\/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\">E<\/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\">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 class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">A2<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">A<\/span><span class=\"code_operator\">^<\/span><span class=\"code_operator\">^<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{\t}\\begin{bmatrix}4 &amp; 3 &amp; 2 &amp; 3 &amp; 2 &amp; 2\\\\3 &amp; 4 &amp; 2 &amp; 3 &amp; 2 &amp; 2\\\\2 &amp; 2 &amp; 4 &amp; 2 &amp; 4 &amp; 0\\\\3 &amp; 3 &amp; 2 &amp; 4 &amp; 2 &amp; 2\\\\2 &amp; 2 &amp; 4 &amp; 2 &amp; 4 &amp; 0\\\\2 &amp; 2 &amp; 0 &amp; 2 &amp; 0 &amp; 2\\end{bmatrix}\\]<\/p>\n<p>Como el grafo es simple, el cuadrado de la matriz de adyacencia nos proporciona los grados de los v\u00e9rtices. Vemos que todos los grados de los v\u00e9rtices son de orden par; por tanto, el grafo tiene un ciclo euleriano.\n<\/p><\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea \\(G=(V,E)\\), donde \\(V\\)={1,2,3,4,5}, \\(E\\)={{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{4,5}}, a) tiene un camino euleriano, \u00bfcu\u00e1l es?; b) tiene un ciclo euleriano, \u00bfcu\u00e1l es?.<\/p>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1aw2() {\n  var htmlShow1aw2 = document.getElementById(\"html-show1aw2\");\n  if (htmlShow1aw2.style.display === \"none\") {\n    htmlShow1aw2.style.display = \"block\";\n  } else {\n    htmlShow1aw2.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1aw2()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1aw2\" 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\">load<\/span><span class=\"code_operator\">(<\/span><span class=\"code_string\">&quot;graphs&quot;<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\u00bb..\/maxima\/5.45.1\/share\/graphs\/graphs.mac\u00bb\\]<\/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_variable\">V<\/span><span class=\"code_operator\">:<\/span><span class=\"code_function\">makelist<\/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_endofline\">,<\/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_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\">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\">E<\/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\">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 class=\"code_endofline\"><br \/><\/span><span class=\"code_variable\">A2<\/span><span class=\"code_operator\">:<\/span><span class=\"code_variable\">A<\/span><span class=\"code_operator\">^<\/span><span class=\"code_operator\">^<\/span><span class=\"code_number\">2<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\\operatorname{ }\\begin{bmatrix}4 &amp; 3 &amp; 2 &amp; 3 &amp; 2\\\\3 &amp; 4 &amp; 2 &amp; 3 &amp; 2\\\\2 &amp; 2 &amp; 3 &amp; 2 &amp; 3\\\\3 &amp; 3 &amp; 2 &amp; 4 &amp; 2\\\\2 &amp; 2 &amp; 3 &amp; 2 &amp; 3\\end{bmatrix}\\]<\/p>\n<p>De nuevo, tenemos un grafo simple. Como todos los grados de los v\u00e9rtices no son de orden par, el grafo no tiene un ciclo euleriano. Sin embargo, los v\u00e9rtices 3 y 5 tiene grado impar, luego hay un camino euleriano entre ambos.\n<\/p><\/div>\n<hr \/>\n<h2>Grafos Hamiltonianos<\/h2>\n<p>Un camino hamiltoniano es un camino de un grafo que visita todos los v\u00e9rtices del grafo una sola vez. Si adem\u00e1s el \u00faltimo v\u00e9rtice visitado es adyacente al primero, el camino es un ciclo hamiltoniano. Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.<\/p>\n<p>Ejempos de grafos Hamiltonianos:<\/p>\n<ul>\n<li>Todos los grafos ciclos son hamiltonianos.<\/li>\n<li>Todos los s\u00f3lidos plat\u00f3nicos, (tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.) considerados como grafos, son hamiltonianos<\/li>\n<li>Un \u00e1rbol tiene un camino hamiltoniano si y s\u00f3lo si tiene a lo sumo dos hojas.<\/li>\n<\/ul>\n<blockquote><p><strong>Ejercicio:<\/strong> \u00bfTiene un camino hamiltoniano?<br \/>\n<svg width=\"420\" height=\"320\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\">\n  <!-- aristas -->\n  <g stroke=\"#333\" stroke-width=\"4\" stroke-linecap=\"round\">\n    <!-- c - l1 (arriba) -->\n    <line x1=\"210\" y1=\"160\" x2=\"210\" y2=\"70\"\/>\n    <!-- c - l2 (izquierda) -->\n    <line x1=\"210\" y1=\"160\" x2=\"110\" y2=\"230\"\/>\n    <!-- c - l3 (derecha) -->\n    <line x1=\"210\" y1=\"160\" x2=\"310\" y2=\"230\"\/>\n  <\/g>\n  <!-- v\u00e9rtices (c\u00edrculos) -->\n  <g font-family=\"Arial\" font-size=\"14\" text-anchor=\"middle\" fill=\"#000\">\n    <!-- c (central) -->\n    <circle cx=\"210\" cy=\"160\" r=\"24\" fill=\"#ffe082\" stroke=\"#333\" stroke-width=\"3\"\/>\n    <text x=\"210\" y=\"166\" font-weight=\"bold\">c<\/text>\n    <!-- l1 (arriba) -->\n    <circle cx=\"210\" cy=\"70\" r=\"18\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"210\" y=\"76\">1<\/text>\n    <!-- l2 (izquierda) -->\n    <circle cx=\"110\" cy=\"230\" r=\"18\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"110\" y=\"236\">2<\/text>\n    <!-- l3 (derecha) -->\n    <circle cx=\"310\" cy=\"230\" r=\"18\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"310\" y=\"236\">3$<\/text>\n  <\/g>\n<\/svg>\n<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv1aw24() {\n  var htmlShow1aw24 = document.getElementById(\"html-show1aw24\");\n  if (htmlShow1aw24.style.display === \"none\") {\n    htmlShow1aw24.style.display = \"block\";\n  } else {\n    htmlShow1aw24.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1aw24()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1aw24\" style=\"display: none;\">\nUna consecuencia del resultado anterior es que \\(K_{1,3}\\) no tiene un camino hamiltoniano.\n<\/div>\n<hr \/>\n<p>Hay que tener en cuenta que cualquier ciclo hamiltoniano puede ser convertido en un camino hamiltoniano si se elimina cualquiera de sus aristas, pero un camino hamiltoniano puede ser extendido en ciclo s\u00f3lo si los v\u00e9rtices de los extremos son adyacentes.<\/p>\n<blockquote><p><strong>Ejercicio:<\/strong> Determinar si el siguiente grafo es hamiltoniano<br \/>\n<svg width=\"600\" height=\"420\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\">\n  <!-- aristas -->\n  <g stroke=\"#333\" stroke-width=\"3\" stroke-linecap=\"round\">\n    <!-- v conectado a a, b, c, d -->\n    <line x1=\"300\" y1=\"120\" x2=\"300\" y2=\"220\"\/> <!-- v-a -->\n    <line x1=\"300\" y1=\"120\" x2=\"180\" y2=\"120\"\/> <!-- v-b -->\n    <line x1=\"300\" y1=\"120\" x2=\"420\" y2=\"120\"\/> <!-- v-c -->\n    <line x1=\"300\" y1=\"120\" x2=\"300\" y2=\"40\"\/>  <!-- v-d -->\n    <!-- tri\u00e1ngulo a-x-y -->\n    <line x1=\"300\" y1=\"220\" x2=\"240\" y2=\"300\"\/> <!-- a-x -->\n    <line x1=\"240\" y1=\"300\" x2=\"360\" y2=\"300\"\/> <!-- x-y -->\n    <line x1=\"360\" y1=\"300\" x2=\"300\" y2=\"220\"\/> <!-- y-a -->\n  <\/g>\n  <!-- v\u00e9rtices (c\u00edrculos y etiquetas) -->\n  <g font-family=\"Arial\" font-size=\"14\" text-anchor=\"middle\" fill=\"#000\">\n    <!-- v -->\n    <circle cx=\"300\" cy=\"120\" r=\"20\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"300\" y=\"126\">v<\/text>\n    <!-- a -->\n    <circle cx=\"300\" cy=\"220\" r=\"18\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"300\" y=\"226\">a<\/text>\n    <!-- x -->\n    <circle cx=\"240\" cy=\"300\" r=\"16\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"240\" y=\"306\">x<\/text>\n    <!-- y -->\n    <circle cx=\"360\" cy=\"300\" r=\"16\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"360\" y=\"306\">y<\/text>\n    <!-- b -->\n    <circle cx=\"180\" cy=\"120\" r=\"16\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"180\" y=\"126\">b<\/text>\n    <!-- c -->\n    <circle cx=\"420\" cy=\"120\" r=\"16\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"420\" y=\"126\">c<\/text>\n    <!-- d -->\n    <circle cx=\"300\" cy=\"40\" r=\"16\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"2\"\/>\n    <text x=\"300\" y=\"46\">d<\/text>\n  <\/g>\n<\/svg>\n<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv1aw246() {\n  var htmlShow1aw246 = document.getElementById(\"html-show1aw246\");\n  if (htmlShow1aw246.style.display === \"none\") {\n    htmlShow1aw246.style.display = \"block\";\n  } else {\n    htmlShow1aw246.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1aw246()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1aw246\" style=\"display: none;\">\nSi quitas el v\u00e9rtice v, el grafo G\u2212{v} tiene cuatro componentes ({a,x,y} y los v\u00e9rtices aislados {b},{c},{d}); por eso no existe un camino hamiltoniano en G (un camino que recorre todos los v\u00e9rtices no puede conectar v\u00e9rtices situados en m\u00e1s de dos componentes de G\u2212{v} sin pasar por v repetidas veces).\n<\/div>\n<hr \/>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea \\(G=(V,E)\\), donde \\(V\\)={1,2,3,4,5,6}, \\(E\\)={{1,2}, {1,3}, {1,5}, {2,3}, {2,4}, {3,4}, {3,6}, {4,5}, {5,6}}, a) tiene un camino hamiltoniano, \u00bfcu\u00e1l es?; b) tiene un ciclo hamiltoniano, \u00bfcu\u00e1l es?.<\/p>\n<\/blockquote>\n<p>Un resultado que puede ayudarnos a distinguirlos es el siguiente:<\/p>\n<blockquote>\n<p><strong>Propiedad<\/strong>: Un grafo con \\(n\\) v\u00e9rtices \\((n &gt; 3)\\) es hamiltoniano si cada v\u00e9rtice tiene grado mayor o igual a \\(n\/2\\).<\/p>\n<\/blockquote>\n<h2>Grafos planos<\/h2>\n<p>Decimos que un grafo es plano (o planar seg\u00fan referencias) si es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce. <\/p>\n<p>Los grafos \\(K_5\\) y el \\(K_{3,3}\\) son los grafos no planos minimales, lo cual nos permitir\u00e1n caracterizar el resto de los grafos no planos.<\/p>\n<blockquote>\n<p><strong>Teorema de Kuratowski<\/strong>: Un grafo es plano si y solo si no contiene un subgrafo isomorfo a una subdivisi\u00f3n elemental de \\(K_5\\) (el grafo completo de 5 v\u00e9rtices) o \\(K_{3,3}\\) (el grafo bipartito completo de 6 v\u00e9rtices).<\/p>\n<\/blockquote>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea \\(G=(V,E)\\), donde \\(V\\)={1,2,3,4,5,6}, \\(E\\)={{1,2}, {1,3}, {1,5}, {2,3}, {2,4}, {3,4}, {3,6}, {4,5}, {5,6}}, \u00bfes plano?.<\/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\">(%i1)\t<\/span><\/td>\n<td style=\"vertical-align: top;padding: 1mm;\"><span class=\"input\"><span class=\"code_function\">load<\/span><span class=\"code_operator\">(<\/span><span class=\"code_string\">&quot;graphs&quot;<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">;<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p>\\[\u00ab..\/maxima\/5.45.1\/share\/graphs\/graphs.mac\u00bb\\]<\/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)\t<\/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_function\">makelist<\/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_endofline\">,<\/span><span class=\"code_number\">1<\/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_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\">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\">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\">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\">6<\/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_endofline\">,<\/span><span class=\"code_operator\">[<\/span><span class=\"code_number\">5<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_number\">6<\/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\">E<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><span class=\"code_endofline\"><br \/><\/span><span class=\"code_function\">draw_graph<\/span><span class=\"code_operator\">(<\/span><span class=\"code_variable\">g<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0 <span class=\"code_variable\">show_id<\/span><span class=\"code_operator\">=<\/span><span class=\"code_function\">true<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0 <span class=\"code_variable\">show_vertices<\/span><span class=\"code_operator\">=<\/span><span class=\"code_variable\">V<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0 <span class=\"code_variable\">show_vertex_size<\/span><span class=\"code_operator\">=<\/span><span class=\"code_number\">5<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0 <span class=\"code_variable\">edge_color<\/span><span class=\"code_operator\">=<\/span><span class=\"code_variable\">blue<\/span><span class=\"code_endofline\">,<\/span><span class=\"code_endofline\"><br \/><\/span> \u00a0 <span class=\"code_variable\">edge_width<\/span><span class=\"code_operator\">=<\/span><span class=\"code_number\">1<\/span><span class=\"code_endofline\">,<\/span> \u00a0\u00a0 <span class=\"code_endofline\"><br \/><\/span> \u00a0 <span class=\"code_variable\">text_color<\/span><span class=\"code_operator\">=<\/span><span class=\"code_variable\">black<\/span><span class=\"code_operator\">)<\/span><span class=\"code_endofline\">$<\/span><\/span><\/td>\n<\/tr>\n<\/table>\n<p> <img decoding=\"async\" src=\"https:\/\/uploads.jesussoto.es\/grafos\/grafo_2311_6.png\" width=\"398\" style=\"max-width:90%;\" loading=\"lazy\" alt=\" (Graphics) \"\/><br \/>\nAparentemente el grafo no es plano, pero vemos que podemos hacer uno isomorfo que s\u00ed lo es:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/uploads.jesussoto.es\/grafos\/grafo_2310_01.png\" alt=\"\" height=\"362\" class=\"aligncenter size-medium wp-image-1235\"\/><\/p>\n<\/div>\n<hr \/>\n<blockquote><p><strong>Ejercicio:<\/strong> Determinar si es plano el grafo <br \/><img decoding=\"async\" src=\"https:\/\/uploads.jesussoto.es\/grafos\/Bidiakis_cube_hamiltonian.svg.png\" alt=\"\" style=\"width: 75%; height: auto;\" class=\"aligncenter size-medium\"\/><\/p><\/blockquote>\n<p>En la pr\u00e1ctica, es dif\u00edcil usar el teorema de Kuratowski para decidir r\u00e1pidamente si un grafo es plano. Sin embargo, existe un algoritmo r\u00e1pido para este problema: dado un grafo de n v\u00e9rtices y a el n\u00famero de aristas, es posible determinar en tiempo O(n) (lineal) si el grafo es plano o no, utilizando los dos teoremas siguientes:<\/p>\n<blockquote><p><strong>Teorema:<\/strong> Si G es un grafo plano con n \u2265 3 v\u00e9rtices, entonces a \u2264 3n &#8211; 6<\/p><\/blockquote>\n<blockquote><p><strong>Teorema:<\/strong> Si n > 3 y no existen ciclos de longitud 3, entonces a \u2264 2n &#8211; 4<\/p><\/blockquote>\n<blockquote><p><strong>Ejercicio:<\/strong> Determinar el m\u00ednimo n\u00famero de aristas que hay que eliminar a $K_6$ para que sea plano<\/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;\">\nPara un grafo plano simple con v\u22653, se cumple: $e\\leq 3v\u22126$<\/p>\n<p>En $K_6$, tenemos $v=6$,$e=\\binom{6}{2}=15$<\/p>\n<p>Si queremos que sea plano, como m\u00e1ximo puede tener:<\/p>\n<p>$$e_{max}=3(6)\u22126=12$$<\/p>\n<p>Por tanto, hay que quitar al menos:<\/p>\n<p>\\[15\u221212=3\\]<\/p>\n<p>aristas.<\/p>\n<p>Veamos c\u00f3mo ser\u00eda el grafo:<br \/>\n<svg width=\"520\" height=\"420\" viewBox=\"0 0 520 420\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\">\n  <!-- K6 planarizado: aristas negras (se quedan), rojas (eliminadas) -->\n  <!-- aristas que SE QUEDAN -->\n  <g stroke=\"#333\" stroke-width=\"4\" stroke-linecap=\"round\">\n    <!-- tri\u00e1ngulo exterior -->\n    <line x1=\"260\" y1=\"40\" x2=\"70\" y2=\"360\"\/>\n    <line x1=\"70\" y1=\"360\" x2=\"450\" y2=\"360\"\/>\n    <line x1=\"450\" y1=\"360\" x2=\"260\" y2=\"40\"\/>\n    <!-- tri\u00e1ngulo interior -->\n    <line x1=\"260\" y1=\"160\" x2=\"170\" y2=\"300\"\/>\n    <line x1=\"170\" y1=\"300\" x2=\"350\" y2=\"300\"\/>\n    <line x1=\"350\" y1=\"300\" x2=\"260\" y2=\"160\"\/>\n    <!-- conexiones -->\n    <line x1=\"260\" y1=\"40\" x2=\"260\" y2=\"160\"\/>\n    <line x1=\"260\" y1=\"40\" x2=\"170\" y2=\"300\"\/>\n    <line x1=\"70\" y1=\"360\" x2=\"170\" y2=\"300\"\/>\n    <line x1=\"70\" y1=\"360\" x2=\"350\" y2=\"300\"\/>\n    <line x1=\"450\" y1=\"360\" x2=\"350\" y2=\"300\"\/>\n    <line x1=\"450\" y1=\"360\" x2=\"260\" y2=\"160\"\/>\n  <\/g>\n  <!-- aristas ELIMINADAS -->\n  <g stroke=\"#d32f2f\" stroke-width=\"4\" stroke-dasharray=\"8,6\" stroke-linecap=\"round\">\n    <!-- quitamos conexiones \"verticales\" interiores -->\n    <line x1=\"260\" y1=\"40\" x2=\"350\" y2=\"300\"\/>\n    <line x1=\"70\" y1=\"360\" x2=\"260\" y2=\"160\"\/>\n    <line x1=\"450\" y1=\"360\" x2=\"170\" y2=\"300\"\/>\n  <\/g>\n  <!-- v\u00e9rtices -->\n  <g font-family=\"Arial\" font-size=\"16\" text-anchor=\"middle\" fill=\"#000\">\n    <circle cx=\"260\" cy=\"40\" r=\"22\" fill=\"#ffe082\" stroke=\"#333\" stroke-width=\"3\"\/>\n    <text x=\"260\" y=\"46\" font-weight=\"bold\">1<\/text>\n    <circle cx=\"70\" cy=\"360\" r=\"22\" fill=\"#ffe082\" stroke=\"#333\" stroke-width=\"3\"\/>\n    <text x=\"70\" y=\"366\" font-weight=\"bold\">2<\/text>\n    <circle cx=\"450\" cy=\"360\" r=\"22\" fill=\"#ffe082\" stroke=\"#333\" stroke-width=\"3\"\/>\n    <text x=\"450\" y=\"366\" font-weight=\"bold\">3<\/text>\n    <circle cx=\"260\" cy=\"160\" r=\"22\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"3\"\/>\n    <text x=\"260\" y=\"166\" font-weight=\"bold\">4<\/text>\n    <circle cx=\"170\" cy=\"300\" r=\"22\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"3\"\/>\n    <text x=\"170\" y=\"306\" font-weight=\"bold\">5<\/text>\n    <circle cx=\"350\" cy=\"300\" r=\"22\" fill=\"#fff9c4\" stroke=\"#333\" stroke-width=\"3\"\/>\n    <text x=\"350\" y=\"306\" font-weight=\"bold\">6<\/text>\n  <\/g>\n<\/svg><\/p>\n<p>\ud83d\udd34 Las aristas rojas discontinuas son las **3 que eliminamos**.<\/p>\n<\/div>\n<hr \/>\n<h3>Regiones de un grafo plano<\/h3>\n<p>Un grafo plano, apropiadamente representado divide al plano en distintas regiones (llamadas caras). <\/p>\n<p>Un mapa es un grafo plano en el que nos interesan las caras entre las aristas.<\/p>\n<p>Un de los resultado m\u00e1s interesante de los grafos planos es la f\u00f3rmula de Euler:<\/p>\n<blockquote>\n<p><strong>F\u00f3rmula de Euler<\/strong>: Si un grafo plano y conexo tiene \\(v\\) v\u00e9rtices, \\(a\\) aristas y \\(c\\) caras, entonces \\[v \u2212 a + c = 2\\]<\/p>\n<\/blockquote>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> Sea \\(K_5\\) y eliminemos las aristas m\u00ednimas necesarias para conseguir que sea plano, \u00bfcu\u00e1ntas regiones tiene?<\/p>\n<\/blockquote>\n<h2>Coloraci\u00f3n de grafos<\/h2>\n<p>La coloraci\u00f3n de grafos es una forma de asignar etiquetas, llamadas colores, a elementos del grafo. En una coloraci\u00f3n, los v\u00e9rtices de un grafo cumplen que ning\u00fan v\u00e9rtice adyacente comparte el mismo color.<\/p>\n<p>La <strong>v\u00e9rtice coloraci\u00f3n<\/strong> (o simplemente coloraci\u00f3n) es la asignaci\u00f3n de los v\u00e9rtices de un grafo con colores tal que dos v\u00e9rtices que comparten la misma arista tengan colores diferentes. Un grafo con bucles no puede ser coloreado; solo se consideran grafos simples.<\/p>\n<p>El <strong>n\u00famero crom\u00e1tico<\/strong> de un grafo es la menor cantidad de colores necesarios para colorear sus v\u00e9rtices sin que dos v\u00e9rtices adyacentes tengan el mismo color. O m\u00e1s formalmente, es el menor entero m tal que G es m-coloreable (o bien, tiene una coloraci\u00f3n propia con m colores). A este n\u00famero se le denota como \\(\\chi(G)\\).<\/p>\n<p>El \u00fanico grafo que es 1-coloreable es el grafo sin aristas, y el grafo completo \\({\\displaystyle K_{n}\\,}\\) de \\(n\\) v\u00e9rtices requiere \\({\\displaystyle \\chi (K_{n})=n\\,}\\) colores.<\/p>\n<p>Los grafos 2-coloreables son exactamente grafos bipartitos, incluidos \u00e1rboles y bosques. Por el teorema de los cuatro colores, todo grafo plano es 4-coloreable.<\/p>\n<p>Una de las principales aplicaciones de la coloraci\u00f3n de grafos es la asignaci\u00f3n de registros en compiladores, introducida en 1981.<\/p>\n<blockquote>\n<p><strong>Ejercicio:<\/strong> \u00bfCu\u00e1l es \\(\\chi(G)\\) donde \\(G\\) es el grafo de Petersen(*)?<\/p>\n<p><a href=\"https:\/\/commons.wikimedia.org\/wiki\/File:Petersen1_tiny.svg#\/media\/Archivo:Petersen1_tiny.svg\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/9\/91\/Petersen1_tiny.svg\" alt=\"Petersen1 tiny.svg\" height=\"220\" width=\"220\"  class=\"aligncenter size-medium wp-image-1235\"><\/a><\/p>\n<\/blockquote>\n<p style=\"font-size: 8px;\">(*)De &lt;a href=\u00bb\/\/commons.wikimedia.org\/w\/index.php?title=User:Leshabirukov&amp;amp;action=edit&amp;amp;redlink=1&#8243; class=\u00bbnew\u00bb title=\u00bbUser:Leshabirukov (page does not exist)\u00bb&gt;Leshabirukov&lt;\/a&gt; &#8211; Own work by uploader based on &lt;a class=\u00bbexternal free\u00bb href=\u00bbhttps:\/\/en.wikipedia.org\/wiki\/File:Heawood_Graph.svg\u00bb&gt;http:\/\/en.wikipedia.org\/wiki\/File:Heawood_Graph.svg&lt;\/a&gt;, <a href=\"https:\/\/creativecommons.org\/licenses\/by-sa\/3.0\" title=\"Creative Commons Attribution-Share Alike 3.0\">CC BY-SA 3.0<\/a>, <a href=\"https:\/\/commons.wikimedia.org\/w\/index.php?curid=5788203\">Enlace<\/a><\/p>\n<p>Un caso particular es la coloraci\u00f3n de las aristas: asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color. El proceso lo podemos repetir con las caras de un grafo plano, asignando un color a cada cara o regi\u00f3n tal que caras que compartan una frontera com\u00fan tengan colores diferentes. En este caso se trata de un grafo plano.<\/p>\n<p>Para terminar os dejo unos enlaces de inter\u00e9s<\/p>\n<ul>\n<li><a href=\"https:\/\/www.gaussianos.com\/la-conjetura-de-steinberg-es-falsa\/\" target=\"_blank\">La conjetura de Steinberg es falsa<\/a>.<\/li>\n<li><a href=\"https:\/\/blogs.20minutos.es\/mati-una-profesora-muy-particular\/2013\/03\/14\/de-rama-en-rama-pero-por-el-camino-mas-corto\/\" target=\"_blank\">De rama en rama, pero por el camino m\u00e1s corto<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<hr \/>\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> Sea (58, 20, 34, 86, 66, 24, 55, 36, 15) la secuencia de n\u00fameros que se van insertando en un ABB inicialmente vac\u00edo y \\(H\\) el n\u00famero de hojas que tiene el \u00e1rbol binario de b\u00fasqueda resultante tras insertar todos los elementos en el orden dado. \u00bfCu\u00e1l es el valor de \\(\\mathbf{mod}(H*21, 23)\\)\n<\/td>\n<\/tr>\n<tr>\n<td width=\"100%\">\n<div id=\"menu-a\">\n<ul>\n<li>9<\/li>\n<li>15<\/li>\n<li>21<\/li>\n<\/ul>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<style>\n#solucion{display:none;}\n#cy2{width:700px;height:420px;max-width:100%;margin:20px auto;border:1px solid #ccc;background:#fff;}\n<\/style>\n<p><button type=\"button\" onclick=\"mostrarSolucion()\">Soluci\u00f3n<\/button><\/p>\n<div id=\"solucion\">\n<p><strong>B.)<\/strong><\/p>\n<p>Primero dibujamos el grafo ABB.<\/p>\n<div id=\"cy2\"><\/div>\n<p>Observamos que tiene 4 hojas. Por tanto, \\(\\mathbf{mod}(4*21, 23)=15\\)\n<\/p><\/div>\n<p><script>\nvar cy2=null;\nfunction crearArbol(){\nif(cy2!==null){return;}\ncy2=cytoscape({\ncontainer:document.getElementById('cy2'),\nelements:[\n{data:{id:'58',level:0}},\n{data:{id:'20',level:1}},\n{data:{id:'86',level:1}},\n{data:{id:'15',level:2}},\n{data:{id:'34',level:2}},\n{data:{id:'66',level:2}},\n{data:{id:'24',level:3}},\n{data:{id:'36',level:3}},\n{data:{id:'55',level:3}},\n{data:{id:'e1',source:'58',target:'20'}},\n{data:{id:'e2',source:'58',target:'86'}},\n{data:{id:'e3',source:'20',target:'15'}},\n{data:{id:'e4',source:'20',target:'34'}},\n{data:{id:'e5',source:'86',target:'66'}},\n{data:{id:'e6',source:'34',target:'24'}},\n{data:{id:'e7',source:'34',target:'36'}},\n{data:{id:'e8',source:'66',target:'55'}}\n],\nstyle:[\n{selector:'node',style:{'background-color':'#2ecc71','label':'data(id)','color':'#2c3e50','text-valign':'center','text-halign':'center','width':40,'height':40,'font-size':16,'font-weight':'bold'}},\n{selector:'node[level = 0]',style:{'background-color':'#e74c3c'}},\n{selector:'edge',style:{'width':3,'line-color':'#34495e','target-arrow-color':'#34495e','target-arrow-shape':'triangle','curve-style':'bezier'}}\n],\nlayout:{name:'breadthfirst',directed:true,roots:'#58',padding:30,spacingFactor:1.3,animate:false},\nuserZoomingEnabled:false,\nuserPanningEnabled:false,\nboxSelectionEnabled:false\n});\nsetTimeout(function(){\ncy2.resize();\ncy2.fit(undefined,20);\ncy2.center();\n},100);\n}\nfunction mostrarSolucion(){\nvar s=document.getElementById('solucion');\nif(s.style.display==='none'||s.style.display===''){\ns.style.display='block';\nsetTimeout(function(){crearArbol();},50);\n}else{\ns.style.display='none';\n}\n}\n<\/script><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Grafos Eulerianos Un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente&#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":[],"class_list":["post-1107","post","type-post","status-publish","format-standard","hentry","category-matematica-discreta"],"_links":{"self":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1107","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=1107"}],"version-history":[{"count":46,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1107\/revisions"}],"predecessor-version":[{"id":1180,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1107\/revisions\/1180"}],"wp:attachment":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1107"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1107"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1107"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}