{"id":1040,"date":"2026-04-20T10:15:59","date_gmt":"2026-04-20T08:15:59","guid":{"rendered":"https:\/\/clases.jesussoto.es\/?p=1040"},"modified":"2026-04-04T19:24:12","modified_gmt":"2026-04-04T17:24:12","slug":"mad-arboles","status":"publish","type":"post","link":"https:\/\/clases.jesussoto.es\/?p=1040","title":{"rendered":"MAD: \u00c1rboles"},"content":{"rendered":"<h2>1. Definici\u00f3n y Caracterizaci\u00f3n<\/h2>\n<p>Un <strong>\u00e1rbol<\/strong> es un grafo simple <em>G = (V, E)<\/em> que cumple cualquiera de las siguientes condiciones equivalentes:<\/p>\n<ul>\n<li><strong>Conectividad y Ciclos:<\/strong> Es un grafo conexo y no contiene ciclos.<\/li>\n<li><strong>Caminos \u00danicos:<\/strong> Existe un \u00fanico camino simple entre cualquier par de v\u00e9rtices <em>u, v<\/em>.<\/li>\n<li><strong>Relaci\u00f3n V\u00e9rtices-Aristas:<\/strong> Para un grafo de <em>n<\/em> v\u00e9rtices, es un \u00e1rbol si es conexo y tiene <em>n-1<\/em> aristas, o si no tiene ciclos y tiene <em>n-1<\/em> aristas.<\/li>\n<li><strong>Propiedades Cr\u00edticas:<\/strong>\n<ul>\n<li>Es conexo, pero deja de serlo si se prescinde de cualquier arista.<\/li>\n<li>No contiene ciclos, pero se forma uno si se a\u00f1ade cualquier arista nueva.<\/li>\n<li>Todo \u00e1rbol es un <strong>grafo bipartito<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<blockquote><p><strong>Ejercicio:<\/strong> Considera un grafo simple conexo G con 15 v\u00e9rtices. <strong>a)<\/strong> Si G es un \u00e1rbol, \u00bfcu\u00e1ntas aristas debe tener? Justifica tu respuesta. <strong>b)<\/strong> Si G tiene 18 aristas, \u00bfpuede ser un \u00e1rbol? \u00bfPor qu\u00e9? <strong>c)<\/strong> Si eliminamos 4 aristas de G y obtenemos un bosque con 3 componentes conexas (todas ellas \u00e1rboles), \u00bfcu\u00e1ntas aristas ten\u00eda G originalmente?\n<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv1b3a() {\n  var htmlShow1b3a = document.getElementById(\"html-show1b3a\");\n  if (htmlShow1b3a.style.display === \"none\") {\n    htmlShow1b3a.style.display = \"block\";\n  } else {\n    htmlShow1b3a.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1b3a()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1b3a\" style=\"display: none;\">\n<h4>Apartado a) Si G es un \u00e1rbol con 15 v\u00e9rtices, \u00bfcu\u00e1ntas aristas debe tener?<\/h4>\n<p>Una de las propiedades fundamentales de los \u00e1rboles establece que un \u00e1rbol con \\( n \\) v\u00e9rtices tiene exactamente \\( n-1 \\) aristas.<\/p>\n<p>En nuestro caso:<\/p>\n<ul>\n<li>N\u00famero de v\u00e9rtices: \\( n = 15 \\)<\/li>\n<li>N\u00famero de aristas: \\( n &#8211; 1 = 15 &#8211; 1 = 14 \\)<\/li>\n<\/ul>\n<p>Por tanto, el grafo G debe tener exactamente <strong>14 aristas<\/strong>.<\/p>\n<p>Esta propiedad se cumple porque un \u00e1rbol es un grafo conexo (necesitamos al menos 14 aristas para conectar 15 v\u00e9rtices) y sin ciclos (no podemos tener m\u00e1s de 14 aristas porque se formar\u00eda un ciclo). La \u00fanica cantidad posible es exactamente \\( n-1 \\) aristas.<\/p>\n<h4>Apartado b) Si G tiene 18 aristas, \u00bfpuede ser un \u00e1rbol?<\/h4>\n<p>Como hemos visto en el apartado anterior, un \u00e1rbol con 15 v\u00e9rtices debe tener exactamente 14 aristas.<\/p>\n<p>Si G tiene 18 aristas, tenemos:<\/p>\n<ul>\n<li>Aristas de G: 18<\/li>\n<li>Aristas necesarias para ser \u00e1rbol: 14<\/li>\n<li>Aristas en exceso: \\( 18 &#8211; 14 = 4 \\)<\/li>\n<\/ul>\n<p>Consecuentemente, G no puede ser un \u00e1rbol.<\/p>\n<p>Un grafo con 15 v\u00e9rtices y 18 aristas tiene 4 aristas m\u00e1s de las necesarias. Estas aristas adicionales necesariamente forman ciclos. Por tanto, G no cumple la definici\u00f3n de \u00e1rbol (que debe ser conexo y sin ciclos).<\/p>\n<h4>Apartado c) Bosque con 3 componentes conexas<\/h4>\n<p>Partimos de un grafo G con 15 v\u00e9rtices. Al eliminar 4 aristas, obtenemos un bosque con 3 componentes conexas (tres \u00e1rboles separados).<\/p>\n<p><strong>Paso 1:<\/strong> Calcular cu\u00e1ntas aristas tiene el bosque resultante.<\/p>\n<p>Sea \\( n_1, n_2, n_3 \\) el n\u00famero de v\u00e9rtices en cada componente. Sabemos que:<\/p>\n<ul>\n<li>\\( n_1 + n_2 + n_3 = 15 \\) (los v\u00e9rtices se reparten entre las 3 componentes)<\/li>\n<\/ul>\n<p>Cada componente es un \u00e1rbol, por tanto:<\/p>\n<ul>\n<li>Componente 1 tiene \\( n_1 &#8211; 1 \\) aristas<\/li>\n<li>Componente 2 tiene \\( n_2 &#8211; 1 \\) aristas<\/li>\n<li>Componente 3 tiene \\( n_3 &#8211; 1 \\) aristas<\/li>\n<\/ul>\n<p>Total de aristas en el bosque:<\/p>\n<p>\\[ (n_1 &#8211; 1) + (n_2 &#8211; 1) + (n_3 &#8211; 1) = n_1 + n_2 + n_3 &#8211; 3 = 15 &#8211; 3 = 12 \\text{ aristas} \\]<\/p>\n<p><strong>Paso 2:<\/strong> Calcular cu\u00e1ntas aristas ten\u00eda G originalmente.<\/p>\n<p>Si al eliminar 4 aristas quedaron 12 aristas, entonces G ten\u00eda:<\/p>\n<p>\\[ 12 + 4 = 16 \\text{ aristas} \\]<\/p>\n<p>Por tanto, G ten\u00eda originalmente <strong>16 aristas<\/strong>.<\/p>\n<p><strong>Nota:<\/strong> Observa que G no era un \u00e1rbol (tendr\u00eda 14 aristas), sino un grafo con 2 aristas extra que formaban ciclos.<\/p>\n<\/div>\n<hr \/>\n<h2>2. Tipos y Conceptos Relacionados<\/h2>\n<ul>\n<li><strong>Bosque:<\/strong> Grafo simple sin ciclos donde sus componentes conexas son \u00e1rboles.<\/li>\n<li><strong>\u00c1rbol Generador (o Recubridor):<\/strong> Subgrafo de un grafo <em>G<\/em> que es un \u00e1rbol y contiene a todos los v\u00e9rtices de <em>G<\/em>. Un grafo tiene \u00e1rbol generador si y solo si es conexo.<\/li>\n<li><strong>\u00c1rbol Generador M\u00ednimo:<\/strong> En grafos ponderados, es el \u00e1rbol generador cuyo peso total (suma de los pesos de sus aristas) es el m\u00ednimo posible.    <\/li>\n<li><strong>Algoritmo de Prim:<\/strong> Procedimiento paso a paso para hallar este \u00e1rbol partiendo de un v\u00e9rtice inicial y a\u00f1adiendo la arista de menor peso que conecte con un v\u00e9rtice nuevo.<\/li>\n<\/ul>\n<blockquote><p><strong>Ejercicio:<\/strong> Dado el siguiente grafo ponderado que representa conexiones entre servidores (los pesos indican el coste de cada enlace):<\/p>\n<div id=\"cy1\" class=\"cy-graph\" style=\"width:400px;height:400px;max-width:100%;margin:20px auto;border:1px solid #ccc;\"><\/div>\n<dl>\n<dd><strong>a)<\/strong> Dibuja al menos dos \u00e1rboles generadores diferentes de este grafo.<\/dd>\n<dd><strong>b)<\/strong> Utilizando el <strong>algoritmo de Prim<\/strong> comenzando desde el v\u00e9rtice A, construye paso a paso el \u00e1rbol generador m\u00ednimo. Indica en cada paso qu\u00e9 arista a\u00f1ades y por qu\u00e9.<\/dd>\n<dd><strong>c)<\/strong> \u00bfCu\u00e1l es el coste total del \u00e1rbol generador m\u00ednimo?<\/dd>\n<\/dl>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1b3b() {\n  var htmlShow1b3b = document.getElementById(\"html-show1b3b\");\n  if (htmlShow1b3b.style.display === \"none\") {\n    htmlShow1b3b.style.display = \"block\";\n  } else {\n    htmlShow1b3b.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1b3b()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1b3b\" style=\"display: none;\">\n<h3><strong>Apartado <strong>a)<\/strong><\/strong> Dos \u00e1rboles generadores diferentes.<\/h3>\n<p>Un \u00e1rbol generador debe incluir todos los v\u00e9rtices (A, B, C, D, E, F) y exactamente \\( 6 &#8211; 1 = 5 \\) aristas, sin formar ciclos.<\/p>\n<p><strong>\u00c1rbol Generador 1:<\/strong><\/p>\n<ul>\n<li>Aristas: A-C (peso 3), C-D (peso 2), A-B (peso 5), B-E (peso 4), D-F (peso 8)<\/li>\n<li>Peso total: \\( 3 + 2 + 5 + 4 + 8 = 22 \\)<\/li>\n<\/ul>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    A ---5--- B\r\n    |         |\r\n    3         4\r\n    |         |\r\n    C--2--D   E\r\n          |\r\n          8\r\n          |\r\n          F\r\n<\/pre>\n<p><strong>\u00c1rbol Generador 2:<\/strong><\/p>\n<ul>\n<li>Aristas: A-D (peso 6), C-D (peso 2), B-E (peso 4), D-E (peso 7), D-F (peso 8)<\/li>\n<li>Peso total: \\( 6 + 2 + 4 + 7 + 8 = 27 \\)<\/li>\n<\/ul>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    A         B\r\n     \\        |\r\n      \\       4\r\n       6      |\r\n        \\     E\r\n         \\   \/\r\n          \\ \/7\r\n           D\r\n          \/|\r\n         \/ |\r\n        2  8\r\n       \/   |\r\n      C    F\r\n<\/pre>\n<h3><strong>Apartado b)<\/strong> Algoritmo de Prim desde A<\/h3>\n<p><strong>Soluci\u00f3n paso a paso:<\/strong><\/p>\n<p>El algoritmo de Prim construye el \u00e1rbol generador m\u00ednimo comenzando desde un v\u00e9rtice inicial y a\u00f1adiendo en cada paso la arista de menor peso que conecte un v\u00e9rtice ya incluido con uno nuevo.<\/p>\n<p><strong>Inicio:<\/strong><\/p>\n<ul>\n<li>V\u00e9rtices en el \u00e1rbol: {A}<\/li>\n<li>V\u00e9rtices pendientes: {B, C, D, E, F}<\/li>\n<\/ul>\n<p><strong>Paso 1:<\/strong><\/p>\n<ul>\n<li>Aristas candidatas desde A: A-B (peso 5), A-C (peso 3), A-D (peso 6)<\/li>\n<li>Elegimos la de menor peso: <strong>A-C (peso 3)<\/strong><\/li>\n<li>V\u00e9rtices en el \u00e1rbol: {A, C}<\/li>\n<li>Peso acumulado: 3<\/li>\n<\/ul>\n<p><strong>Paso 2:<\/strong><\/p>\n<ul>\n<li>Aristas candidatas: A-B (5), A-D (6), C-D (2)<\/li>\n<li>Elegimos: <strong>C-D (peso 2)<\/strong><\/li>\n<li>V\u00e9rtices en el \u00e1rbol: {A, C, D}<\/li>\n<li>Peso acumulado: \\( 3 + 2 = 5 \\)<\/li>\n<\/ul>\n<p><strong>Paso 3:<\/strong><\/p>\n<ul>\n<li>Aristas candidatas: A-B (5), D-E (7), D-F (8)<\/li>\n<li>Elegimos: <strong>A-B (peso 5)<\/strong><\/li>\n<li>V\u00e9rtices en el \u00e1rbol: {A, B, C, D}<\/li>\n<li>Peso acumulado: \\( 5 + 5 = 10 \\)<\/li>\n<\/ul>\n<p><strong>Paso 4:<\/strong><\/p>\n<ul>\n<li>Aristas candidatas: B-E (4), D-E (7), D-F (8)<\/li>\n<li>Elegimos: <strong>B-E (peso 4)<\/strong><\/li>\n<li>V\u00e9rtices en el \u00e1rbol: {A, B, C, D, E}<\/li>\n<li>Peso acumulado: \\( 10 + 4 = 14 \\)<\/li>\n<\/ul>\n<p><strong>Paso 5:<\/strong><\/p>\n<ul>\n<li>Aristas candidatas: D-F (8)<\/li>\n<li>Elegimos: <strong>D-F (peso 8)<\/strong><\/li>\n<li>V\u00e9rtices en el \u00e1rbol: {A, B, C, D, E, F}<\/li>\n<li>Peso acumulado: \\( 14 + 8 = 22 \\)<\/li>\n<\/ul>\n<p><strong>\u00c1rbol Generador M\u00ednimo resultante:<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    A ---5--- B\r\n    |         |\r\n    3         4\r\n    |         |\r\n    C--2--D   E\r\n          |\r\n          8\r\n          |\r\n          F\r\n<\/pre>\n<p>Aristas seleccionadas: A-C, C-D, A-B, B-E, D-F<\/p>\n<h3><strong>Apartado c)<\/strong> Coste total del \u00e1rbol generador m\u00ednimo<\/h3>\n<p>Sumando los pesos de todas las aristas seleccionadas:<\/p>\n<p>\\[ 3 + 2 + 5 + 4 + 8 = 22 \\]<\/p>\n<p>El coste total del \u00e1rbol generador m\u00ednimo es <strong>22<\/strong>.<\/p>\n<\/div>\n<hr \/>\n<h2>3. \u00c1rboles con Ra\u00edz<\/h2>\n<p>Estructura donde se destaca un v\u00e9rtice especial llamado <strong>ra\u00edz<\/strong>.<\/p>\n<ul>\n<li><strong>Jerarqu\u00eda:<\/strong>\n<ul>\n<li><strong>Niveles:<\/strong> La ra\u00edz est\u00e1 en el nivel 0; sus adyacentes en el nivel 1, y as\u00ed sucesivamente.<\/li>\n<li><strong>Altura:<\/strong> Valor m\u00e1ximo del nivel de sus v\u00e9rtices, $h(G)$.<\/li>\n<li><strong>Relaciones:<\/strong> Se definen conceptos de <strong>padre<\/strong> (v\u00e9rtice anterior en el camino desde la ra\u00edz), <strong>hijo<\/strong> (v\u00e9rtice siguiente), <strong>ancestro<\/strong> y <strong>descendiente<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tipos de V\u00e9rtices:<\/strong>\n<ul>\n<li><strong>Hoja:<\/strong> V\u00e9rtice que no tiene hijos.<\/li>\n<li><strong>V\u00e9rtice Interno:<\/strong> V\u00e9rtice que no es una hoja.<\/li>\n<\/ul>\n<\/li>\n<li><strong>Clasificaci\u00f3n por Grado:<\/strong>\n<ul>\n<li><strong>\u00c1rbol m-ario:<\/strong> Cada v\u00e9rtice interno tiene a lo sumo <em>m<\/em> hijos. Es \u00abcompleto\u00bb si todos tienen exactamente <em>m<\/em> hijos.<\/li>\n<li><strong>\u00c1rbol Binario:<\/strong> \u00c1rbol 2-ario donde se distingue entre hijo derecho e hijo izquierdo.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<blockquote><p><strong>Ejercicio:<\/strong> Considera el siguiente \u00e1rbol con ra\u00edz en A:<\/p>\n<div class=\"grafo-container\">\n<div id=\"cy2\" class=\"cy-graph\"><\/div>\n<\/div>\n<dl>\n<dd><strong>a)<\/strong> Indica la altura del \u00e1rbol.<\/dd>\n<dd><strong>b)<\/strong> Enumera todos los v\u00e9rtices hoja.<\/dd>\n<dd><strong>c)<\/strong> Para el v\u00e9rtice E, indica: su padre, sus hijos, sus ancestros y sus descendientes.<\/dd>\n<dd><strong>d)<\/strong> Determina el nivel de cada v\u00e9rtice.<\/dd>\n<dd><strong>e)<\/strong> \u00bfEs este \u00e1rbol m-ario? En caso afirmativo, \u00bfqu\u00e9 valor tiene m? \u00bfEs completo?<\/dd>\n<\/dl>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1b3c() {\n  var htmlShow1b3c = document.getElementById(\"html-show1b3c\");\n  if (htmlShow1b3c.style.display === \"none\") {\n    htmlShow1b3c.style.display = \"block\";\n  } else {\n    htmlShow1b3c.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1b3c()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1b3c\" style=\"display: none;\">\n<h3><strong>Apartado a)<\/strong> Altura del \u00e1rbol<\/h3>\n<p>La altura de un \u00e1rbol es el nivel m\u00e1ximo de sus v\u00e9rtices (el nivel m\u00e1s alejado de la ra\u00edz).<\/p>\n<p>Niveles en el \u00e1rbol:<\/p>\n<ul>\n<li>Nivel 0: A<\/li>\n<li>Nivel 1: B, C, D<\/li>\n<li>Nivel 2: E, F, G, H<\/li>\n<li>Nivel 3: I<\/li>\n<\/ul>\n<p>Luego, la altura del \u00e1rbol es <strong>3<\/strong>.<\/p>\n<h3><strong>Apartado b)<\/strong> V\u00e9rtices hoja<\/h3>\n<p>Un v\u00e9rtice hoja es aquel que no tiene hijos (es decir, no tiene descendientes).<\/p>\n<p>Analizando cada v\u00e9rtice:<\/p>\n<ul>\n<li>A tiene hijos (B, C, D) \u2192 NO es hoja<\/li>\n<li>B tiene hijos (E, F) \u2192 NO es hoja<\/li>\n<li>C no tiene hijos \u2192 <strong>S\u00cd es hoja<\/strong><\/li>\n<li>D tiene hijos (G, H) \u2192 NO es hoja<\/li>\n<li>E tiene hijo (I) \u2192 NO es hoja<\/li>\n<li>F no tiene hijos \u2192 <strong>S\u00cd es hoja<\/strong><\/li>\n<li>G no tiene hijos \u2192 <strong>S\u00cd es hoja<\/strong><\/li>\n<li>H no tiene hijos \u2192 <strong>S\u00cd es hoja<\/strong><\/li>\n<li>I no tiene hijos \u2192 <strong>S\u00cd es hoja<\/strong><\/li>\n<\/ul>\n<p>Los v\u00e9rtices hoja son: <strong>C, F, G, H, I<\/strong> (5 hojas en total).<\/p>\n<h3><strong>Apartado c)<\/strong> Informaci\u00f3n sobre el v\u00e9rtice E<\/h3>\n<p><strong>Padre de E:<\/strong> El v\u00e9rtice inmediatamente anterior en el camino desde la ra\u00edz hasta E.<\/p>\n<ul>\n<li>Camino desde la ra\u00edz: A \u2192 B \u2192 E<\/li>\n<li>Padre de E: <strong>B<\/strong><\/li>\n<\/ul>\n<p><strong>Hijos de E:<\/strong> Los v\u00e9rtices directamente conectados a E y que est\u00e1n en el nivel siguiente.<\/p>\n<ul>\n<li>Hijos de E: <strong>I<\/strong><\/li>\n<\/ul>\n<p><strong>Ancestros de E:<\/strong> Todos los v\u00e9rtices en el camino desde la ra\u00edz hasta E (sin incluir a E).<\/p>\n<ul>\n<li>Camino: A \u2192 B \u2192 E<\/li>\n<li>Ancestros de E: <strong>A, B<\/strong><\/li>\n<\/ul>\n<p><strong>Descendientes de E:<\/strong> Todos los v\u00e9rtices en los sub\u00e1rboles que cuelgan de E.<\/p>\n<ul>\n<li>Descendientes de E: <strong>I<\/strong><\/li>\n<\/ul>\n<h3><strong>Apartado d)<\/strong> Nivel de cada v\u00e9rtice<\/h3>\n<p>El nivel de un v\u00e9rtice es la distancia (n\u00famero de aristas) desde la ra\u00edz hasta ese v\u00e9rtice.<\/p>\n<table border=\"1\" cellpadding=\"8\" cellspacing=\"0\">\n<thead>\n<tr>\n<th>V\u00e9rtice<\/th>\n<th>Nivel<\/th>\n<th>Camino desde la ra\u00edz<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>A<\/td>\n<td>0<\/td>\n<td>A<\/td>\n<\/tr>\n<tr>\n<td>B<\/td>\n<td>1<\/td>\n<td>A \u2192 B<\/td>\n<\/tr>\n<tr>\n<td>C<\/td>\n<td>1<\/td>\n<td>A \u2192 C<\/td>\n<\/tr>\n<tr>\n<td>D<\/td>\n<td>1<\/td>\n<td>A \u2192 D<\/td>\n<\/tr>\n<tr>\n<td>E<\/td>\n<td>2<\/td>\n<td>A \u2192 B \u2192 E<\/td>\n<\/tr>\n<tr>\n<td>F<\/td>\n<td>2<\/td>\n<td>A \u2192 B \u2192 F<\/td>\n<\/tr>\n<tr>\n<td>G<\/td>\n<td>2<\/td>\n<td>A \u2192 D \u2192 G<\/td>\n<\/tr>\n<tr>\n<td>H<\/td>\n<td>2<\/td>\n<td>A \u2192 D \u2192 H<\/td>\n<\/tr>\n<tr>\n<td>I<\/td>\n<td>3<\/td>\n<td>A \u2192 B \u2192 E \u2192 I<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h3><strong>Apartado e)<\/strong> \u00bfEs m-ario? \u00bfEs completo?<\/h3>\n<p>Un \u00e1rbol es <strong>m-ario<\/strong> si cada v\u00e9rtice interno tiene <strong>a lo sumo<\/strong> m hijos.<\/p>\n<p>Analizando los v\u00e9rtices internos (no hojas):<\/p>\n<ul>\n<li>A tiene 3 hijos (B, C, D)<\/li>\n<li>B tiene 2 hijos (E, F)<\/li>\n<li>D tiene 2 hijos (G, H)<\/li>\n<li>E tiene 1 hijo (I)<\/li>\n<\/ul>\n<p>El m\u00e1ximo n\u00famero de hijos que tiene un v\u00e9rtice interno es 3 (el v\u00e9rtice A).<\/p>\n<p>Vemos que s\u00ed, es un \u00e1rbol <strong>3-ario<\/strong> (ternario), porque ning\u00fan v\u00e9rtice interno tiene m\u00e1s de 3 hijos.<\/p>\n<p>Un \u00e1rbol m-ario es <strong>completo<\/strong> si <strong>todos<\/strong> los v\u00e9rtices internos tienen <strong>exactamente<\/strong> m hijos.<\/p>\n<p>Verificando:<\/p>\n<ul>\n<li>A tiene 3 hijos \u2713<\/li>\n<li>B tiene 2 hijos \u2717 (deber\u00eda tener 3)<\/li>\n<li>D tiene 2 hijos \u2717 (deber\u00eda tener 3)<\/li>\n<li>E tiene 1 hijo \u2717 (deber\u00eda tener 3)<\/li>\n<\/ul>\n<p>Por tanto, <strong>no<\/strong>, no es un \u00e1rbol 3-ario completo, porque no todos los v\u00e9rtices internos tienen exactamente 3 hijos.<\/p>\n<\/div>\n<hr \/>\n<h2>4. \u00c1rboles Binarios de B\u00fasqueda (ABB)<\/h2>\n<p>Es un tipo de \u00e1rbol binario donde los v\u00e9rtices est\u00e1n ordenados.<\/p>\n<ul>\n<li><strong>Propiedad de Orden:<\/strong> Para cada v\u00e9rtice <em>v<\/em>, los elementos del sub\u00e1rbol izquierdo son menores (anteriores) a <em>v<\/em>, y los del sub\u00e1rbol derecho son mayores (posteriores).<\/li>\n<li><strong>Operaciones Principales:<\/strong>\n<ul>\n<li><strong>B\u00fasqueda:<\/strong> Localizaci\u00f3n de un elemento compar\u00e1ndolo con la ra\u00edz y descendiendo por la rama correspondiente.<\/li>\n<li><strong>Inserci\u00f3n:<\/strong> A\u00f1adir un nuevo v\u00e9rtice manteniendo la propiedad de orden.<\/li>\n<li><strong>Eliminaci\u00f3n:<\/strong> Procedimiento para prescindir de un v\u00e9rtice considerando si es una hoja, si tiene un solo hijo o si tiene dos hijos.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<blockquote><p>\n<strong>Ejercicio:<\/strong> Dibuja un \u00e1rbol binario que satisfaga las siguientes condiciones:<\/p>\n<dl>\n<dd><strong>a)<\/strong> Tiene exactamente 7 v\u00e9rtices.<\/dd>\n<dd><strong>b)<\/strong> Tiene altura 3.<\/dd>\n<dd><strong>c)<\/strong> Tiene exactamente 3 hojas.<\/dd>\n<dd><strong>d)<\/strong> El v\u00e9rtice ra\u00edz tiene dos hijos, y al menos un v\u00e9rtice interno (no hoja, no ra\u00edz) tiene un solo hijo.<\/dd>\n<\/dl>\n<p><strong>Pregunta adicional:<\/strong> \u00bfCu\u00e1ntos \u00e1rboles binarios distintos podemos construir con estas condiciones? (No es necesario dibujarlos todos, pero razona si hay m\u00e1s de uno posible)\n<\/p><\/blockquote>\n<p><script>\nfunction showHtmlDiv1b3d() {\n  var htmlShow1b3d = document.getElementById(\"html-show1b3d\");\n  if (htmlShow1b3d.style.display === \"none\") {\n    htmlShow1b3d.style.display = \"block\";\n  } else {\n    htmlShow1b3d.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1b3d()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1b3d\" style=\"display: none;\">\n<h3>Construcci\u00f3n del \u00e1rbol con las condiciones dadas<\/h3>\n<p><strong>Condiciones:<\/strong><\/p>\n<ul>\n<li>Exactamente 7 v\u00e9rtices<\/li>\n<li>Altura 3<\/li>\n<li>Exactamente 3 hojas<\/li>\n<li>La ra\u00edz tiene dos hijos<\/li>\n<li>Al menos un v\u00e9rtice interno (no hoja, no ra\u00edz) tiene un solo hijo<\/li>\n<\/ul>\n<p>Vamos a construir el \u00e1rbol paso a paso razonando las restricciones.<\/p>\n<p><strong>Paso 1:<\/strong> Identificar la estructura b\u00e1sica.<\/p>\n<ul>\n<li>Total: 7 v\u00e9rtices<\/li>\n<li>Hojas: 4 v\u00e9rtices<\/li>\n<li>V\u00e9rtices internos: \\( 7 &#8211; 4 = 3 \\) v\u00e9rtices (incluida la ra\u00edz)<\/li>\n<\/ul>\n<p><strong>Paso 2:<\/strong> Distribuci\u00f3n por niveles.<\/p>\n<ul>\n<li>Nivel 0 (ra\u00edz): 1 v\u00e9rtice<\/li>\n<li>Nivel 1: 2 v\u00e9rtices (los dos hijos de la ra\u00edz)<\/li>\n<li>Niveles 2 y 3: \\( 7 &#8211; 1 &#8211; 2 = 4 \\) v\u00e9rtices restantes<\/li>\n<\/ul>\n<p><strong>Paso 3:<\/strong> Cumplir la condici\u00f3n de \u00abal menos un v\u00e9rtice interno con un solo hijo\u00bb.<\/p>\n<p>Si ambos v\u00e9rtices del nivel 1 tuvieran dos hijos, tendr\u00edamos 4 v\u00e9rtices en el nivel 2, y no podr\u00edamos alcanzar el nivel 3. Por tanto, <strong>uno de los v\u00e9rtices del nivel 1 debe tener un solo hijo<\/strong> (para que ese hijo est\u00e9 en nivel 2 y pueda tener su propio hijo en nivel 3).<\/p>\n<p><strong>Una soluci\u00f3n posible:<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n         1 (nivel 0) - ra\u00edz\r\n        \/ \\\r\n       \/   \\\r\n      2     3 (nivel 1)\r\n     \/ \\    |\r\n    4   5   6 (nivel 2)\r\n            |\r\n            7 (nivel 3)\r\n<\/pre>\n<p><strong>Verificaci\u00f3n:<\/strong><\/p>\n<ul>\n<li>V\u00e9rtices totales: 7 \u2713<\/li>\n<li>Altura: 3 (el v\u00e9rtice 7 est\u00e1 en nivel 3) \u2713<\/li>\n<li>Hojas: 4, 5 (nivel 2) y 7 (nivel 3) = 3.<\/li>\n<\/ul>\n<p><strong>Pregunta adicional: \u00bfCu\u00e1ntos \u00e1rboles distintos?<\/strong><\/p>\n<p>Hay <strong>m\u00faltiples<\/strong> \u00e1rboles binarios distintos que cumplen estas condiciones (al menos en configuraciones similares), ya que podemos reorganizar los sub\u00e1rboles izquierdo y derecho en diferentes niveles. El n\u00famero exacto requerir\u00eda enumeraci\u00f3n exhaustiva.<\/p>\n<\/div>\n<hr \/>\n<blockquote><p><strong>Ejercicio:<\/strong> Considera la siguiente secuencia de n\u00fameros que se van insertando en un ABB inicialmente vac\u00edo:<br \/>\n\\[(50,\\, 30,\\, 70,\\, 20,\\, 40,\\, 60,\\, 80,\\, 10,\\, 25)\\]<\/p>\n<dl>\n<dd><strong>a)<\/strong> Dibuja el \u00e1rbol binario de b\u00fasqueda resultante tras insertar todos los elementos en el orden dado.<\/dd>\n<dd><strong>b)<\/strong> Describe el proceso paso a paso de <strong>b\u00fasqueda<\/strong> del elemento 25 en el \u00e1rbol construido. Indica qu\u00e9 v\u00e9rtices se visitan.<\/dd>\n<dd><strong>c)<\/strong> Describe el proceso de <strong>eliminaci\u00f3n<\/strong> del v\u00e9rtice 30 del \u00e1rbol. Dibuja el \u00e1rbol resultante.<\/dd>\n<dd><strong>d)<\/strong> Si hubi\u00e9ramos insertado los mismos n\u00fameros pero en orden ascendente (10, 20, 25, 30, &#8230;), \u00bfqu\u00e9 forma tendr\u00eda el \u00e1rbol? \u00bfQu\u00e9 problema observas?<\/dd>\n<\/dl>\n<\/blockquote>\n<p><script>\nfunction showHtmlDiv1b3e() {\n  var htmlShow1b3e = document.getElementById(\"html-show1b3e\");\n  if (htmlShow1b3e.style.display === \"none\") {\n    htmlShow1b3e.style.display = \"block\";\n  } else {\n    htmlShow1b3e.style.display = \"none\";\n  }\n}\n<\/script><\/p>\n<p><button onclick=\"showHtmlDiv1b3e()\">Soluci\u00f3n:<\/button><\/p>\n<div id=\"html-show1b3e\" style=\"display: none;\">\n<h3><strong>Apartado a)<\/strong> Construcci\u00f3n del ABB<\/h3>\n<p><strong>Veamos el proceso paso a paso:<\/strong><\/p>\n<p><strong>Paso 1: Insertar 50<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    50\r\n<\/pre>\n<p>50 se convierte en la ra\u00edz (el \u00e1rbol estaba vac\u00edo).<\/p>\n<p><strong>Paso 2: Insertar 30<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    50\r\n   \/\r\n  30\r\n<\/pre>\n<p>30 < 50, por tanto, va a la izquierda de 50.<\/p>\n<p><strong>Paso 3: Insertar 70<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    50\r\n   \/  \\\r\n  30   70\r\n<\/pre>\n<p>70 > 50, por tanto, va a la derecha de 50.<\/p>\n<p><strong>Paso 4: Insertar 20<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    50\r\n   \/  \\\r\n  30   70\r\n \/\r\n20\r\n<\/pre>\n<p>20 < 50 \u2192 izquierda. 20 < 30 \u2192 izquierda de 30.<\/p>\n<p><strong>Paso 5: Insertar 40<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    50\r\n   \/  \\\r\n  30   70\r\n \/  \\\r\n20  40\r\n<\/pre>\n<p>40 < 50 \u2192 izquierda. 40 > 30 \u2192 derecha de 30.<\/p>\n<p><strong>Paso 6: Insertar 60<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    50\r\n   \/  \\\r\n  30   70\r\n \/  \\  \/\r\n20  40 60\r\n<\/pre>\n<p>60 > 50 \u2192 derecha. 60 < 70 \u2192 izquierda de 70.<\/p>\n<p><strong>Paso 7: Insertar 80<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n    50\r\n   \/  \\\r\n  30   70\r\n \/  \\  \/ \\\r\n20  40 60 80\r\n<\/pre>\n<p>80 > 50 \u2192 derecha. 80 > 70 \u2192 derecha de 70.<\/p>\n<p><strong>Paso 8: Insertar 10<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n      50\r\n     \/  \\\r\n    30   70\r\n   \/  \\  \/ \\\r\n  20  40 60 80\r\n \/\r\n10\r\n<\/pre>\n<p>10 < 50 \u2192 izquierda. 10 < 30 \u2192 izquierda. 10 < 20 \u2192 izquierda de 20.<\/p>\n<p><strong>Paso 9: Insertar 25<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n      50\r\n     \/  \\\r\n    30   70\r\n   \/  \\  \/ \\\r\n  20  40 60 80\r\n \/  \\\r\n10  25\r\n<\/pre>\n<p>25 < 50 \u2192 izquierda. 25 < 30 \u2192 izquierda. 25 > 20 \u2192 derecha de 20.<\/p>\n<p><strong>\u00c1rbol final:<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n        50\r\n       \/  \\\r\n      30   70\r\n     \/  \\  \/ \\\r\n    20  40 60 80\r\n   \/ \\\r\n  10 25\r\n<\/pre>\n<h3><strong>Apartado b)<\/strong> B\u00fasqueda del elemento 25<\/h3>\n<p>El proceso de b\u00fasqueda compara el elemento buscado con cada v\u00e9rtice visitado y decide si continuar por la izquierda o derecha.<\/p>\n<p><strong>B\u00fasqueda de 25:<\/strong><\/p>\n<ol>\n<li><strong>Visitar ra\u00edz (50):<\/strong> 25 < 50 \u2192 ir a la izquierda<\/li>\n<li><strong>Visitar 30:<\/strong> 25 < 30 \u2192 ir a la izquierda<\/li>\n<li><strong>Visitar 20:<\/strong> 25 > 20 \u2192 ir a la derecha<\/li>\n<li><strong>Visitar 25:<\/strong> 25 = 25 \u2192 \u00a1Encontrado!<\/li>\n<\/ol>\n<p><strong>V\u00e9rtices visitados en orden:<\/strong> 50 \u2192 30 \u2192 20 \u2192 25<\/p>\n<p><strong>N\u00famero de comparaciones:<\/strong> 4<\/p>\n<h3><strong>Apartado c)<\/strong> Eliminaci\u00f3n del v\u00e9rtice 30<\/h3>\n<p>El v\u00e9rtice 30 tiene <strong>dos hijos<\/strong> (20 y 40), por lo que debemos aplicar el procedimiento de eliminaci\u00f3n para este caso.<\/p>\n<p><strong>Procedimiento est\u00e1ndar:<\/strong><\/p>\n<ol>\n<li>Buscar el <strong>sucesor inmediato<\/strong> de 30 (el menor elemento del sub\u00e1rbol derecho) o el <strong>predecesor inmediato<\/strong> (el mayor elemento del sub\u00e1rbol izquierdo).<\/li>\n<li>Reemplazar 30 con ese valor.<\/li>\n<li>Eliminar el v\u00e9rtice del sucesor\/predecesor (que tendr\u00e1 0 o 1 hijo).<\/li>\n<\/ol>\n<p><strong>Opci\u00f3n 1: Usar el sucesor (menor del sub\u00e1rbol derecho de 30)<\/strong><\/p>\n<p>Sub\u00e1rbol derecho de 30: solo contiene 40.<\/p>\n<p>Menor elemento: <strong>40<\/strong><\/p>\n<p><strong>Pasos:<\/strong><\/p>\n<ol>\n<li>Reemplazar 30 por 40<\/li>\n<li>Eliminar el v\u00e9rtice 40 original (que es hoja, f\u00e1cil de eliminar)<\/li>\n<\/ol>\n<p><strong>\u00c1rbol resultante:<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n        50\r\n       \/  \\\r\n      40   70\r\n     \/    \/ \\\r\n    20   60 80\r\n   \/ \\\r\n  10 25\r\n<\/pre>\n<p><strong>Opci\u00f3n 2: Usar el predecesor (mayor del sub\u00e1rbol izquierdo de 30)<\/strong><\/p>\n<p>Sub\u00e1rbol izquierdo de 30: contiene 20, 10, 25.<\/p>\n<p>Mayor elemento: <strong>25<\/strong><\/p>\n<p><strong>Pasos:<\/strong><\/p>\n<ol>\n<li>Reemplazar 30 por 25<\/li>\n<li>Eliminar el v\u00e9rtice 25 original (que es hoja)<\/li>\n<\/ol>\n<p><strong>\u00c1rbol resultante (alternativa):<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n        50\r\n       \/  \\\r\n      25   70\r\n     \/  \\  \/ \\\r\n    20  40 60 80\r\n   \/\r\n  10\r\n<\/pre>\n<p><strong>Ambas soluciones son v\u00e1lidas.<\/strong> La primera (usando el sucesor) es m\u00e1s com\u00fan en las implementaciones est\u00e1ndar.<\/p>\n<h3><strong>Apartado d)<\/strong> Inserci\u00f3n en orden ascendente<\/h3>\n<p>Si insertamos los elementos en orden ascendente: <strong>10, 20, 25, 30, 40, 50, 60, 70, 80<\/strong><\/p>\n<p><strong>Construcci\u00f3n paso a paso:<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\nInsertar 10:\r\n10\r\n\r\nInsertar 20:\r\n10\r\n  \\\r\n  20\r\n\r\nInsertar 25:\r\n10\r\n  \\\r\n  20\r\n    \\\r\n    25\r\n\r\nInsertar 30:\r\n10\r\n  \\\r\n  20\r\n    \\\r\n    25\r\n      \\\r\n      30\r\n\r\n... y as\u00ed sucesivamente\r\n<\/pre>\n<p><strong>\u00c1rbol resultante:<\/strong><\/p>\n<pre style=\"background-color: #f4f4f4; padding: 15px; border: 1px solid #ccc; font-family: monospace;\">\r\n10\r\n  \\\r\n  20\r\n    \\\r\n    25\r\n      \\\r\n      30\r\n        \\\r\n        40\r\n          \\\r\n          50\r\n            \\\r\n            60\r\n              \\\r\n              70\r\n                \\\r\n                80\r\n<\/pre>\n<p><strong>Problema observado:<\/strong><\/p>\n<p>El \u00e1rbol se convierte en una <strong>lista enlazada<\/strong> (o cadena lineal). Esto significa que:<\/p>\n<ul>\n<li><strong>Altura del \u00e1rbol:<\/strong> \\( n &#8211; 1 = 8 \\) (muy alto para 9 elementos)<\/li>\n<li><strong>Tiempo de b\u00fasqueda:<\/strong> En el peor caso, \\( O(n) \\) en lugar de \\( O(\\log n) \\)<\/li>\n<li><strong>Eficiencia perdida:<\/strong> Se pierde la principal ventaja de los ABB: b\u00fasqueda eficiente mediante divisi\u00f3n del espacio en mitades.<\/li>\n<\/ul>\n<p>Por tanto, para evitar esta degradaci\u00f3n, se usan <strong>\u00e1rboles balanceados<\/strong> (como AVL o \u00e1rboles rojo-negro) que garantizan altura logar\u00edtmica mediante rotaciones autom\u00e1ticas tras cada inserci\u00f3n\/eliminaci\u00f3n.<\/p>\n<\/div>\n<hr \/>\n<p><script>\n\/\/ Grafo 1: Grafo Ponderado\nvar cy1 = cytoscape({\n  container: document.getElementById('cy1'),  \n  elements: [\n    { data: { id: 'A' } },\n    { data: { id: 'B' } },\n    { data: { id: 'C' } },\n    { data: { id: 'D' } },\n    { data: { id: 'E' } },\n    { data: { id: 'F' } },\n    { data: { id: 'AB', source: 'A', target: 'B', weight: 5 } },\n    { data: { id: 'AC', source: 'A', target: 'C', weight: 3 } },\n    { data: { id: 'AD', source: 'A', target: 'D', weight: 6 } },\n    { data: { id: 'CD', source: 'C', target: 'D', weight: 2 } },\n    { data: { id: 'BE', source: 'B', target: 'E', weight: 4 } },\n    { data: { id: 'DE', source: 'D', target: 'E', weight: 7 } },\n    { data: { id: 'DF', source: 'D', target: 'F', weight: 8 } }\n  ],  \n  style: [\n    {\n      selector: 'node',\n      style: {\n        'background-color': '#3498db',\n        'label': 'data(id)',\n        'color': '#2c3e50',\n        'text-valign': 'center',\n        'text-halign': 'center',\n        'width': 40,\n        'height': 40,\n        'font-size': 16,\n        'font-weight': 'bold'\n      }\n    },\n    {\n      selector: 'edge',\n      style: {\n        'width': 3,\n        'line-color': '#95a5a6',\n        'label': 'data(weight)',\n        'text-rotation': 'autorotate',\n        'text-margin-y': -10,\n        'font-size': 14,\n        'color': '#e74c3c',\n        'font-weight': 'bold'\n      }\n    }\n  ],  \n  layout: {\n    name: 'preset',\n    positions: {\n      'A': { x: 100, y: 100 },\n      'B': { x: 300, y: 100 },\n      'C': { x: 100, y: 200 },\n      'D': { x: 200, y: 200 },\n      'E': { x: 300, y: 200 },\n      'F': { x: 200, y: 300 }\n    }\n  },\n  zoomingEnabled: false \/\/ Deshabilita el zoom con la rueda del rat\u00f3n\n});\ncy1.fit(undefined,40);\ncy1.center();\n\/\/ Grafo 2: \u00c1rbol con Ra\u00edz\nvar cy2 = cytoscape({\n  container: document.getElementById('cy2'),  \n  elements: [\n    { data: { id: 'A', level: 0 } },\n    { data: { id: 'B', level: 1 } },\n    { data: { id: 'C', level: 1 } },\n    { data: { id: 'D', level: 1 } },\n    { data: { id: 'E', level: 2 } },\n    { data: { id: 'F', level: 2 } },\n    { data: { id: 'G', level: 2 } },\n    { data: { id: 'H', level: 2 } },\n    { data: { id: 'I', level: 3 } },\n    { data: { id: 'AB', source: 'A', target: 'B' } },\n    { data: { id: 'AC', source: 'A', target: 'C' } },\n    { data: { id: 'AD', source: 'A', target: 'D' } },\n    { data: { id: 'BE', source: 'B', target: 'E' } },\n    { data: { id: 'BF', source: 'B', target: 'F' } },\n    { data: { id: 'DG', source: 'D', target: 'G' } },\n    { data: { id: 'DH', source: 'D', target: 'H' } },\n    { data: { id: 'EI', source: 'E', target: 'I' } }\n  ],  \n  style: [\n    {\n      selector: 'node',\n      style: {\n        'background-color': '#2ecc71',\n        'label': 'data(id)',\n        'color': '#2c3e50',\n        'text-valign': 'center',\n        'text-halign': 'center',\n        'width': 40,\n        'height': 40,\n        'font-size': 16,\n        'font-weight': 'bold'\n      }\n    },\n    {\n      selector: 'node[level = 0]',\n      style: {\n        'background-color': '#e74c3c'\n      }\n    },\n    {\n      selector: 'edge',\n      style: {\n        'width': 3,\n        'line-color': '#34495e',\n        'target-arrow-color': '#34495e',\n        'target-arrow-shape': 'triangle',\n        'curve-style': 'bezier'\n      }\n    }\n  ],  \n  layout: {\n    name: 'breadthfirst',\n    directed: true,\n    roots: '#A',\n    spacingFactor: 1.5,\n    padding: 10\n  },\n  zoomingEnabled: false \/\/ Deshabilita el zoom con la rueda del rat\u00f3n\n});\ncy2.fit(undefined,40);\ncy2.center();\n<\/script><\/p>\n<h2>5. \u00c1rboles enraizados<\/h2>\n<p>Un \u00e1rbol enraizado es un \u00e1rbol conexo y ac\u00edclico (con \\(n\u22121\\) aristas para \\(n\\) v\u00e9rtices) donde se selecciona un v\u00e9rtice como ra\u00edz, y las aristas se orientan t\u00edpicamente hacia abajo (hacia los hijos) o hacia la ra\u00edz. Esto genera una estructura jer\u00e1rquica \u00fanica: cada v\u00e9rtice, excepto la ra\u00edz, tiene exactamente un padre, y la ra\u00edz tiene grado de entrada 0 en su versi\u00f3n dirigida. En grafos dirigidos, se denomina arborescencia si las aristas apuntan lejos de la ra\u00edz, o anti-arborescencia si apuntan hacia ella. Lo que diferencia a los \u00e1rboles enraizados de los \u00e1rboles no dirigidos es que un \u00e1rbol enraizado contiene un v\u00e9rtice distinguido, llamado ra\u00edz. <\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/commons.wikimedia.org\/wiki\/File:Unlabeled_ordered_rooted_trees_of_4_edges_and_2_leaves.svg#\/media\/File:Unlabeled_ordered_rooted_trees_of_4_edges_and_2_leaves.svg\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/3\/33\/Unlabeled_ordered_rooted_trees_of_4_edges_and_2_leaves.svg\" alt=\"Unlabeled ordered rooted trees of 4 edges and 2 leaves.svg\" height=\"372\" width=\"277\"><\/a><br \/>By <a href=\"\/\/commons.wikimedia.org\/w\/index.php?title=User:%C5%98i%C5%A5opi%C4%8D&amp;action=edit&amp;redlink=1\" class=\"new\" title=\"User:\u0158i\u0165opi\u010d (page does not exist)\">\u0158i\u0165opi\u010d<\/a> &#8211; <span class=\"int-own-work\" lang=\"en\">Own work<\/span>, <a href=\"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\" title=\"Creative Commons Attribution-Share Alike 4.0\">CC BY-SA 4.0<\/a>, <a href=\"https:\/\/commons.wikimedia.org\/w\/index.php?curid=92284453\">Link<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>1. Definici\u00f3n y Caracterizaci\u00f3n Un \u00e1rbol es un grafo simple G = (V, E) que cumple cualquiera de las siguientes condiciones equivalentes: Conectividad y Ciclos: Es un grafo conexo y no contiene&#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-1040","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\/1040","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=1040"}],"version-history":[{"count":43,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1040\/revisions"}],"predecessor-version":[{"id":1108,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/1040\/revisions\/1108"}],"wp:attachment":[{"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1040"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1040"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/clases.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1040"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}