{"id":10619,"date":"2020-11-05T20:14:11","date_gmt":"2020-11-05T19:14:11","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=10619"},"modified":"2021-12-06T13:10:02","modified_gmt":"2021-12-06T12:10:02","slug":"corrected-exercises-graph-theory-and-coloring","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-teoria-de-grafos-y-coloracion\/","title":{"rendered":"Ejercicios corregidos: teor\u00eda de grafos y coloreado"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"10619\" class=\"elementor elementor-10619\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8b55bb7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8b55bb7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-7f7169f\" data-id=\"7f7169f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e6741d8 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"e6741d8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Teor\u00eda de grafos<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-34054fe\" data-id=\"34054fe\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-01a1991 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"01a1991\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Pagina de inicio<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-af7b2fa\" data-id=\"af7b2fa\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-65380c4 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"65380c4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Graph_theory\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1af20ba elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1af20ba\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b0594fa\" data-id=\"b0594fa\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e28354c elementor-widget elementor-widget-heading\" data-id=\"e28354c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenido<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-teoria-de-grafos-y-coloracion\/#Corrected-exercises-about-graph-theory-and-coloring\" >Ejercicios corregidos sobre teor\u00eda de grafos y coloraci\u00f3n.<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-teoria-de-grafos-y-coloracion\/#Exercise-1\" >Ejercicio 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-teoria-de-grafos-y-coloracion\/#Exercise-2\" >Ejercicio 2<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-teoria-de-grafos-y-coloracion\/#Exercise-3\" >Ejercicio 3<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-teoria-de-grafos-y-coloracion\/#Exercise-4\" >Ejercicio 4<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Corrected-exercises-about-graph-theory-and-coloring\"><\/span>Ejercicios corregidos sobre teor\u00eda de grafos y coloraci\u00f3n.<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f0b562a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f0b562a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-219b3c9\" data-id=\"219b3c9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-980c5c2 elementor-widget elementor-widget-text-editor\" data-id=\"980c5c2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Esta p\u00e1gina contiene varios ejercicios corregidos sobre modelado de teor\u00eda de grafos y problemas de coloraci\u00f3n. Consulte la p\u00e1gina de teor\u00eda de grafos para conocer los conceptos b\u00e1sicos de la teor\u00eda de grafos y varios problemas de la teor\u00eda de grafos.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ead03a1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ead03a1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-eeacd41\" data-id=\"eeacd41\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0fdb7ab elementor-widget elementor-widget-text-editor\" data-id=\"0fdb7ab\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<h2><span class=\"ez-toc-section\" id=\"Exercise-1\"><\/span><strong><b>Ejercicio 1<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Considerando un juego de domin\u00f3 utilizando los n\u00fameros 0, 1, 2, 3, 4, ya que en cada domin\u00f3 se incluyen dos d\u00edgitos distintos, como 1 y 3, se propone el siguiente problema: \u00bfEs posible alinear todas las fichas de domin\u00f3 de modo que cuando dos peones &quot;tocan&quot; los n\u00fameros &quot;en contacto&quot; son id\u00e9nticos?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-33f0542 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"33f0542\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-846124f\" data-id=\"846124f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-44c5802 elementor-widget elementor-widget-toggle\" data-id=\"44c5802\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-7211\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-7211\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-7211\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-7211\"><p>Muestre el problema como un gr\u00e1fico completo K5. El problema es encontrar un ciclo euleriano en la gr\u00e1fica.<\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-10624 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1.png\" alt=\"ejercicios corregidos teor\u00eda de grafos modelado problemas de coloraci\u00f3n\" width=\"673\" height=\"301\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1.png 673w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1-300x134.png 300w\" sizes=\"(max-width: 673px) 100vw, 673px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2fc4075 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2fc4075\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-793bb6b\" data-id=\"793bb6b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a586094 elementor-widget elementor-widget-text-editor\" data-id=\"a586094\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<h2><span class=\"ez-toc-section\" id=\"Exercise-2\"><\/span><strong><b>Ejercicio 2<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Considere que la secuencia 01110100 est\u00e1 organizada en un patr\u00f3n circular. Observe que cada uno de los ocho posibles triples binarios: 000, 001, 011 ,. . . , 111 aparecen exactamente una vez en la lista circular. \u00bfPuedes construir una lista similar de longitud 16 donde los cuatro patrones de d\u00edgitos binarios aparezcan exactamente una vez cada uno?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-81b2709 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"81b2709\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2f44ef1\" data-id=\"2f44ef1\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fac9a2a elementor-widget elementor-widget-toggle\" data-id=\"fac9a2a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2621\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2621\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2621\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2621\"><p>Es un gr\u00e1fico con cuatro v\u00e9rtices, cada uno etiquetado con uno de los posibles pares de d\u00edgitos binarios. Imagina que cada nodo son los dos \u00faltimos d\u00edgitos del patr\u00f3n hasta ahora. Las flechas que se alejan de un v\u00e9rtice est\u00e1n etiquetadas como 0 o 1: los dos valores posibles para el siguiente d\u00edgito que se pueden agregar al patr\u00f3n, y los extremos de las flechas indican los nuevos dos d\u00edgitos finales. Por ejemplo, el nodo 00 va a 01 con un arco llamado 1 y va a 00 con un arco llamado 0.<\/p><p>\u00a0Para lograr todas las combinaciones posibles de tres d\u00edgitos, necesitamos recorrer la gr\u00e1fica con un ciclo euleriano. Debido al resultado del problema anterior, siempre hay dos flechas hacia afuera y dos flechas hacia cada v\u00e9rtice, y debido al resultado del problema anterior, debe haber un circuito euleriano.<\/p><p>La situaci\u00f3n es la misma para cualquier n\u00famero de d\u00edgitos, excepto que el gr\u00e1fico se volver\u00e1 cada vez m\u00e1s complejo. Para la versi\u00f3n de 4 d\u00edgitos, habr\u00e1 8 v\u00e9rtices y 16 aristas, y as\u00ed sucesivamente. Pero en todos los casos, habr\u00e1 dos aristas entrando y dos saliendo de cada v\u00e9rtice, por lo que es posible un circuito euleriano.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-10625 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image2.png\" alt=\"ejercicios corregidos teor\u00eda de grafos modelado problemas de coloraci\u00f3n\" width=\"320\" height=\"448\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image2.png 320w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image2-214x300.png 214w\" sizes=\"(max-width: 320px) 100vw, 320px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-08e6a0b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"08e6a0b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c8487df\" data-id=\"c8487df\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-263561a elementor-widget elementor-widget-text-editor\" data-id=\"263561a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<h2><span class=\"ez-toc-section\" id=\"Exercise-3\"><\/span><strong><b>Ejercicio 3<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Un servidor puede enrutar un m\u00e1ximo de paquetes al mismo tiempo. Siete subestaciones est\u00e1n conectadas a un servidor, una subestaci\u00f3n no puede enviar paquetes si algunas subestaciones ya utilizan el enlace. La siguiente tabla presenta cada subestaci\u00f3n de la capacidad de enviar un paquete en funci\u00f3n de las dem\u00e1s. Por ejemplo, un paquete de A no se puede enviar si ya existe un paquete de D, pero se puede enviar cuando B envi\u00f3 un paquete.<\/p><table><tbody><tr><td width=\"118\"><p>Subestaci\u00f3n<\/p><\/td><td width=\"71\"><p>PARA<\/p><\/td><td width=\"71\"><p>B<\/p><\/td><td width=\"71\"><p>VS<\/p><\/td><td width=\"71\"><p>D<\/p><\/td><td width=\"71\"><p>mi<\/p><\/td><td width=\"71\"><p>F<\/p><\/td><td width=\"71\"><p>GRAMO<\/p><\/td><\/tr><tr><td width=\"118\"><p>No esta permitido con<\/p><\/td><td width=\"71\"><p>DE<\/p><\/td><td width=\"71\"><p>D, E, F, G<\/p><\/td><td width=\"71\"><p>P.EJ<\/p><\/td><td width=\"71\"><p>A, B, E<\/p><\/td><td width=\"71\"><p>A, B, C, D, F, G<\/p><\/td><td width=\"71\"><p>B, E, G<\/p><\/td><td width=\"71\"><p>B, C, E, F<\/p><\/td><\/tr><\/tbody><\/table><p>Representa los enlaces en un gr\u00e1fico. \u00bfCu\u00e1ntos paquetes tiene que gestionar el servidor al mismo tiempo (valor m\u00e1ximo)?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a5f412e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a5f412e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b5d7554\" data-id=\"b5d7554\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c181903 elementor-widget elementor-widget-toggle\" data-id=\"c181903\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2021\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2021\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2021\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2021\"><p><img decoding=\"async\" class=\"aligncenter wp-image-10626 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image3.png\" alt=\"ejercicios corregidos teor\u00eda de grafos modelado problemas de coloraci\u00f3n\" width=\"228\" height=\"205\" title=\"\"><\/p><p>El gr\u00e1fico es 4 crom\u00e1tico.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-89099db elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"89099db\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0f7369a\" data-id=\"0f7369a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a96ba5e elementor-widget elementor-widget-text-editor\" data-id=\"a96ba5e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<h2><span class=\"ez-toc-section\" id=\"Exercise-4\"><\/span><strong><b>Ejercicio 4<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><p>Una escuela debe aprobar pruebas escritas a cuatro estudiantes: Pierre, Jean, Guillermo e Ibrahim. Est\u00e1n involucradas siete disciplinas: matem\u00e1ticas, f\u00edsica, biolog\u00eda, franc\u00e9s, ingl\u00e9s, espa\u00f1ol e historia.<br \/>Pierre debe aprobar matem\u00e1ticas, f\u00edsica e ingl\u00e9s, Jean matem\u00e1ticas, biolog\u00eda y franc\u00e9s, Guillermo matem\u00e1ticas, ingl\u00e9s y espa\u00f1ol e Ibrahim f\u00edsica, franc\u00e9s e historia.<br \/>\u00bfCu\u00e1l es la cantidad m\u00ednima de franjas horarias que se puede esperar para que ning\u00fan estudiante tenga que aprobar dos pruebas simult\u00e1neamente? \u00bfCu\u00e1l es el n\u00famero crom\u00e1tico de una gr\u00e1fica completa? \u00bfC\u00f3mo unir n\u00fameros crom\u00e1ticos en un gr\u00e1fico?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e560248 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e560248\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-304ce16\" data-id=\"304ce16\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-07d522e elementor-widget elementor-widget-toggle\" data-id=\"07d522e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-8211\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-8211\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Soluci\u00f3n<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-8211\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-8211\"><p>Un v\u00e9rtice representa una disciplina, un borde une dos disciplinas si no pueden tener lugar al mismo tiempo. El problema se puede solucionar buscando un n\u00famero m\u00ednimo de colores. El subgr\u00e1fico completo m\u00e1s grande es K3, por lo que hay al menos 3 colores. El grado m\u00e1ximo es cinco, por lo que hay como m\u00e1ximo 5 colores. Experimentando, el gr\u00e1fico es tricrom\u00e1tico.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10627 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image4.png\" alt=\"ejercicios corregidos teor\u00eda de grafos modelado problemas de coloraci\u00f3n\" width=\"278\" height=\"250\" title=\"\"><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Teor\u00eda de grafos P\u00e1gina principal Wiki Ejercicios corregidos sobre teor\u00eda de grafos y coloreado Esta p\u00e1gina contiene varios ejercicios corregidos sobre teor\u00eda de grafos, modelado y coloreado... <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"elementor_header_footer","meta":{"footnotes":""},"class_list":["post-10619","page","type-page","status-publish","hentry"],"amp_enabled":false,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/10619","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=10619"}],"version-history":[{"count":0,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/10619\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=10619"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}