{"id":15062,"date":"2022-04-16T21:42:55","date_gmt":"2022-04-16T20:42:55","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=15062"},"modified":"2024-02-13T07:43:00","modified_gmt":"2024-02-13T06:43:00","slug":"modelisation-en-graphe","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/","title":{"rendered":"22 Ejercicios corregidos: modelado en gr\u00e1ficos y \u00e1rboles."},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"15062\" class=\"elementor elementor-15062\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8103e19 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8103e19\" 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-9d8f919\" data-id=\"9d8f919\" 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-9caeffe elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9caeffe\" 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-596c548\" data-id=\"596c548\" 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-e1ffe00 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"e1ffe00\" 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-b6f08ce\" data-id=\"b6f08ce\" 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-822467c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"822467c\" 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-8e98553 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8e98553\" 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-2754a6a\" data-id=\"2754a6a\" 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-bef2e26 elementor-widget elementor-widget-heading\" data-id=\"bef2e26\" 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_86 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-modelado-en-grafos-y-arboles\/#Exercices-corriges-sur-les-bases-de-la-theorie-des-graphes-modelisation-en-graphe-et-arbres\" >Ejercicios corregidos sobre los fundamentos de la teor\u00eda de grafos (modelado de grafos y \u00e1rboles)<\/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-modelado-en-grafos-y-arboles\/#Exercice-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-modelado-en-grafos-y-arboles\/#Exercice-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-modelado-en-grafos-y-arboles\/#Exercice-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-modelado-en-grafos-y-arboles\/#Exercice-4\" >Ejercicio 4<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-5\" >Ejercicio 5<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-6\" >Ejercicio 6<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-7\" >Ejercicio 7<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-8\" >Ejercicio 8<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-9\" >Ejercicio 9<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-10\" >Ejercicio 10<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-11\" >Ejercicio 11<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-12\" >Ejercicio 12<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-13\" >Ejercicio 13<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-15\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-14\" >Ejercicio 14<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-16\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-15\" >Ejercicio 15<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-17\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-16\" >Ejercicio 16<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-18\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-17\" >Ejercicio 17<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-19\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-18\" >Ejercicio 18<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-20\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-19\" >Ejercicio 19<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-21\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-20\" >Ejercicio 20<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-22\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-21\" >Ejercicio 21<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-23\" href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/ejercicios-corregidos-modelado-en-grafos-y-arboles\/#Exercice-22\" >Ejercicio 22<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-sur-les-bases-de-la-theorie-des-graphes-modelisation-en-graphe-et-arbres\"><\/span>Ejercicios corregidos sobre los fundamentos de la teor\u00eda de grafos (modelado de grafos y \u00e1rboles)<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-708b154 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"708b154\" 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-20eb927\" data-id=\"20eb927\" 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-4abaf90 elementor-widget elementor-widget-text-editor\" data-id=\"4abaf90\" 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 muestra algunos ejercicios corregidos de modelado de gr\u00e1ficos y \u00e1rboles. El prop\u00f3sito de estos ejercicios es aprender a modelar un problema usando los conceptos y conceptos b\u00e1sicos de <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">Teor\u00eda de grafos<\/a>. La mayor\u00eda de los problemas presentados son tambi\u00e9n simples resolubles con el m\u00e9todo cl\u00e1sico.\u00a0<\/p><div class=\"elementor-divider\"><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"modelado en grafos y \u00e1rboles\" width=\"97\" height=\"97\" title=\"\"><\/div>\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-8c6313c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8c6313c\" 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-3b180c4\" data-id=\"3b180c4\" 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-d4b578e elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"d4b578e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-ca17b5e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ca17b5e\" 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-58701bc\" data-id=\"58701bc\" 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-d04ae4e elementor-widget elementor-widget-heading\" data-id=\"d04ae4e\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Ejercicio 1<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-769cb17 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"769cb17\" 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-f3c18b3\" data-id=\"f3c18b3\" 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-b14a1fc elementor-widget elementor-widget-text-editor\" data-id=\"b14a1fc\" 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>Dos jugadores tienen 2 o m\u00e1s conjuntos de partidos. Cada turno, el siguiente jugador puede eliminar un cierto n\u00famero de coincidencias de un lote (dependiendo de la regla elegida). El jugador que quita el \u00faltimo partido pierde.<\/p><p>Modele este juego con un gr\u00e1fico en el caso de que haya dos pilas, cada una de las cuales contiene tres f\u00f3sforos, y donde un jugador puede quitar uno o dos f\u00f3sforos cada uno.<br \/>\u00bfQu\u00e9 movimiento debe hacer el primer jugador para ganar el juego?<\/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-3e40f05 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3e40f05\" 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-871f815\" data-id=\"871f815\" 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-bba7009 elementor-widget elementor-widget-toggle\" data-id=\"bba7009\" 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-1961\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1961\" 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-1961\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1961\"><p><img decoding=\"async\" class=\"wp-image-10608 size-medium aligncenter\" title=\"Ejercicios Corregidos: Conceptos B\u00e1sicos de Teor\u00eda de Grafos 1\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image129-300x76.png\" alt=\"\" width=\"300\" height=\"76\" data-recalc-dims=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image129-300x76.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image129.png 319w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>El gr\u00e1fico debe leerse de izquierda a derecha. Un jugador comienza en el nodo 3.3 y cada movimiento toma el camino de un borde a otro nodo. El jugador que llega a 0.0 pierde.<\/p><p>Si el jugador 1 juega, ha ganado si el conjunto de caminos a 0.0 es de tama\u00f1o impar, que nunca es el caso, no hay una estrategia ganadora autom\u00e1tica.<\/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-4e9079d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4e9079d\" 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-9255d95\" data-id=\"9255d95\" 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-3b964b4 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"3b964b4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-007b198 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"007b198\" 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-02d9a22\" data-id=\"02d9a22\" 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-906fbad elementor-widget elementor-widget-heading\" data-id=\"906fbad\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Ejercicio 2<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-ce5c8b7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ce5c8b7\" 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-344fe88\" data-id=\"344fe88\" 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-932480d elementor-widget elementor-widget-text-editor\" data-id=\"932480d\" 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>El siguiente gr\u00e1fico muestra los pasillos de un museo. Un vigilante situado en un pasillo puede vigilar dos cruces situados en sus extremos. \u00bfCu\u00e1ntos guardias se necesitan (y c\u00f3mo deben colocarse) para que todas las intersecciones est\u00e9n vigiladas?<\/p><p>Si ahora colocamos guardias en las intersecciones, suponiendo que un guardia pueda monitorear todos los pasillos que conducen a esa intersecci\u00f3n, \u00bfcu\u00e1ntos guardias se necesitan?<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-10609 size-full\" title=\"Ejercicios Corregidos: Conceptos B\u00e1sicos de Teor\u00eda de Grafos 2\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image130.png?resize=193%2C167\" alt=\"Ejercicios corregidos sobre \u00e1rboles y modelado de teor\u00eda de grafos.\" width=\"193\" height=\"167\" data-recalc-dims=\"1\" \/><\/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-f8ddb2c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f8ddb2c\" 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-8e1962d\" data-id=\"8e1962d\" 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-372b574 elementor-widget elementor-widget-toggle\" data-id=\"372b574\" 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-5781\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5781\" 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-5781\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5781\"><p>Cada guardia se colocar\u00e1 en un borde y podr\u00e1 monitorear dos intersecciones (v\u00e9rtices). El gr\u00e1fico tiene 11 v\u00e9rtices; Se necesitar\u00e1n al menos seis guardias. Por lo tanto, es necesario encontrar un conjunto (m\u00ednimo) de al menos seis aristas, tal que cada v\u00e9rtice incida en al menos una de estas aristas. El siguiente gr\u00e1fico proporciona una soluci\u00f3n (bordes m\u00e1s gruesos).<\/p><p>Esta vez, los guardias est\u00e1n en las cimas y observan las crestas. Debe haber un conjunto de v\u00e9rtices tal que cada arista incida en al menos uno de estos v\u00e9rtices. El siguiente gr\u00e1fico proporciona una soluci\u00f3n utilizando 6 v\u00e9rtices (v\u00e9rtices blancos).<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10610 size-full\" title=\"Ejercicios Corregidos: Conceptos B\u00e1sicos de Teor\u00eda de Grafos 3\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image131.png?resize=194%2C168\" alt=\"Ejercicios corregidos sobre \u00e1rboles y modelado de teor\u00eda de grafos.\" width=\"194\" height=\"168\" data-recalc-dims=\"1\" \/><\/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-614b849 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"614b849\" 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-4ea89bf\" data-id=\"4ea89bf\" 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-83c85d6 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"83c85d6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-aa1f757 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"aa1f757\" 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-db7bb43\" data-id=\"db7bb43\" 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-ae580ba elementor-widget elementor-widget-heading\" data-id=\"ae580ba\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Ejercicio 3<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-01aac0e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"01aac0e\" 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-3aaf79b\" data-id=\"3aaf79b\" 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-2d2a8c2 elementor-widget elementor-widget-text-editor\" data-id=\"2d2a8c2\" 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>Skynet es una red de 15 v\u00e9rtices. Puede pasar de cada v\u00e9rtice a al menos otros siete v\u00e9rtices por enlace. \u00bfPodemos ir por enlace desde un v\u00e9rtice X a cada uno de los otros?<\/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-7b5b06d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7b5b06d\" 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-c345a57\" data-id=\"c345a57\" 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-65579c3 elementor-widget elementor-widget-toggle\" data-id=\"65579c3\" 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-1061\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1061\" 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-1061\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1061\"><p>Sea A cualquier v\u00e9rtice. X est\u00e1 vinculado a al menos 7 ciudades diferentes. Entonces tenemos una red de 8 v\u00e9rtices conectados por enlaces. Dentro de un v\u00e9rtice, tambi\u00e9n puede conectarse con al menos otros siete v\u00e9rtices; entonces hay una nueva red de 8 v\u00e9rtices. Debe haber un v\u00e9rtice compartido en estas redes, de lo contrario la red tendr\u00eda al menos 16 v\u00e9rtices. X est\u00e1 conectado a A en dos planos como m\u00e1ximo, por este v\u00e9rtice com\u00fan; est\u00e1 conectado con todas las dem\u00e1s ciudades.<\/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-ad2b87d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ad2b87d\" 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-3cfbd4a\" data-id=\"3cfbd4a\" 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-d57a450 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"d57a450\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-c1f03c8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c1f03c8\" 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-a2ed7cc\" data-id=\"a2ed7cc\" 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-256b04b elementor-widget elementor-widget-heading\" data-id=\"256b04b\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-4\"><\/span>Ejercicio 4<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-d9d4db1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d9d4db1\" 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-befa0c3\" data-id=\"befa0c3\" 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-2132388 elementor-widget elementor-widget-text-editor\" data-id=\"2132388\" 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>Una red est\u00e1 formada por siete f\u00e1bricas. Una ciudad est\u00e1 vinculada a exactamente dos f\u00e1bricas. Dos f\u00e1bricas comparten exactamente una ciudad. \u00bfCu\u00e1ntas ciudades son servidas por la red?<\/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-2939f95 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2939f95\" 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-b59a74e\" data-id=\"b59a74e\" 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-f10f07d elementor-widget elementor-widget-toggle\" data-id=\"f10f07d\" 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-2521\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2521\" 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-2521\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2521\"><p>Las f\u00e1bricas son los v\u00e9rtices y las ciudades est\u00e1n representadas por una arista que conecta dos v\u00e9rtices. La regla 2 implica que no hay aristas m\u00faltiples y que cualquier par de v\u00e9rtices son adyacentes; es decir, el gr\u00e1fico est\u00e1 completo; es K7, o 21 enlaces.<\/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-69790fc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"69790fc\" 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-2612102\" data-id=\"2612102\" 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-8097301 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"8097301\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-30f0d32 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"30f0d32\" 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-1e5e2b2\" data-id=\"1e5e2b2\" 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-1764602 elementor-widget elementor-widget-heading\" data-id=\"1764602\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-5\"><\/span>Ejercicio 5<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-48de914 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"48de914\" 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-279e8ee\" data-id=\"279e8ee\" 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-f66d933 elementor-widget elementor-widget-text-editor\" data-id=\"f66d933\" 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>Consider\u00e9moslo <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/\">programa lineal<\/a> Pr\u00f3ximo :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10611 size-full\" title=\"Ejercicios Corregidos: Conceptos B\u00e1sicos de Teor\u00eda de Grafos 4\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image132.png?resize=243%2C112\" alt=\"Ejercicios corregidos sobre \u00e1rboles y modelado de teor\u00eda de grafos.\" width=\"243\" height=\"112\" data-recalc-dims=\"1\" \/><\/p><p>Donde X es 0 o 1. Determinar, con un problema gr\u00e1fico, una soluci\u00f3n que maximice la funci\u00f3n objetivo (suma de las X).<\/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-c360bc3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c360bc3\" 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-235509f\" data-id=\"235509f\" 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-006f2ec elementor-widget elementor-widget-toggle\" data-id=\"006f2ec\" 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-4551\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-4551\" 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-4551\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-4551\"><p>Un v\u00e9rtice representa una variable. Dos v\u00e9rtices est\u00e1n conectados si est\u00e1n en la misma desigualdad. El problema es encontrar un conjunto m\u00e1ximo de v\u00e9rtices donde ning\u00fan par de v\u00e9rtices tenga un enlace directo.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10612 size-medium\" title=\"Ejercicios Corregidos: Conceptos B\u00e1sicos de Teor\u00eda de Grafos 5\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image133-300x139.png?resize=300%2C139\" sizes=\"(max-width: 300px) 100vw, 300px\" srcset=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image133.png?resize=300%2C139&amp;ssl=1 300w, https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image133.png?w=407&amp;ssl=1 407w\" alt=\"Ejercicios corregidos sobre \u00e1rboles y modelado de teor\u00eda de grafos.\" width=\"300\" height=\"139\" data-recalc-dims=\"1\" \/><\/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-86e6049 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"86e6049\" 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-8d514a9\" data-id=\"8d514a9\" 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-33d3690 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"33d3690\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-8adef31 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8adef31\" 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-b3cdfe0\" data-id=\"b3cdfe0\" 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-d4c303f elementor-widget elementor-widget-heading\" data-id=\"d4c303f\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-6\"><\/span>Ejercicio 6<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-ebfb021 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ebfb021\" 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-05cf4a7\" data-id=\"05cf4a7\" 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-cf356ec elementor-widget elementor-widget-text-editor\" data-id=\"cf356ec\" 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>Considerando un conjunto de fichas de domin\u00f3 utilizando los n\u00fameros 0, 1, 2, 3, 4, ya que cada ficha de domin\u00f3 consta de dos d\u00edgitos distintos, como son el 1 y el 3, se plantea el siguiente problema: \u00bfes posible alinear todas las fichas 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-a460e33 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a460e33\" 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-0708cc4\" data-id=\"0708cc4\" 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-055ced8 elementor-widget elementor-widget-toggle\" data-id=\"055ced8\" 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-5621\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5621\" 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-5621\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5621\"><p>Muestre el problema como un gr\u00e1fico completo K5. El problema es encontrar un ciclo euleriano en el gr\u00e1fico.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10624 size-full\" title=\"Ejercicios corregidos: teor\u00eda de grafos y coloreado 1\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1.png?resize=673%2C301\" sizes=\"(max-width: 673px) 100vw, 673px\" srcset=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1.png?w=673&amp;ssl=1 673w, https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1.png?resize=300%2C134&amp;ssl=1 300w\" alt=\"ejercicios corregidos teor\u00eda de grafos modelado problemas de coloraci\u00f3n\" width=\"673\" height=\"301\" data-recalc-dims=\"1\" \/><\/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-fce5d3f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fce5d3f\" 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-8a69a23\" data-id=\"8a69a23\" 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-d7a9452 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"d7a9452\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-e6e724a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e6e724a\" 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-a200653\" data-id=\"a200653\" 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-212070e elementor-widget elementor-widget-heading\" data-id=\"212070e\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-7\"><\/span>Ejercicio 7<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-29cb427 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"29cb427\" 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-3f58064\" data-id=\"3f58064\" 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-41802d1 elementor-widget elementor-widget-text-editor\" data-id=\"41802d1\" 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>En un grupo de personas, siempre hay dos individuos que conocen exactamente el mismo n\u00famero de miembros del grupo. Demuestra esto.<\/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-b0f7e56 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b0f7e56\" 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-7bf7dda\" data-id=\"7bf7dda\" 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-357ef51 elementor-widget elementor-widget-toggle\" data-id=\"357ef51\" 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-5601\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5601\" 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-5601\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5601\"><p>Debemos probar que en un grafo simple (sin dobles aristas, sin bucles), siempre hay dos v\u00e9rtices que tienen el mismo grado. Razonaremos por absurdo y supondremos que existe un grafo simple con n v\u00e9rtices del cual todos los grados son diferentes. Entonces los grados de los v\u00e9rtices est\u00e1n entre 0 y n\u22121, y por lo tanto si todos los grados son diferentes, como tenemos n v\u00e9rtices y simplemente n posibilidades para los grados, todas estas posibilidades deben tomarse.\u00a0<\/p><p>En particular, debe haber un v\u00e9rtice de grado 0 y un v\u00e9rtice de grado n\u22121. Pero es imposible, porque este \u00faltimo v\u00e9rtice deber\u00eda tener una arista hacia todos los dem\u00e1s, y no es posible ya que un v\u00e9rtice es de grado 0, por lo tanto aislado.<\/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-4768e6b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4768e6b\" 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-a5deabe\" data-id=\"a5deabe\" 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-4595cf8 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"4595cf8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-8e4f428 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8e4f428\" 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-2599a26\" data-id=\"2599a26\" 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-46463f5 elementor-widget elementor-widget-heading\" data-id=\"46463f5\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-8\"><\/span>Ejercicio 8<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-7bdaec9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7bdaec9\" 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-e0b2351\" data-id=\"e0b2351\" 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-6507a66 elementor-widget elementor-widget-text-editor\" data-id=\"6507a66\" 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>Sea G un grafo simple no dirigido de orden 2p (n\u00famero de aristas). Suponemos que el grado de cada v\u00e9rtice es al menos igual a p. Demuestra que esta gr\u00e1fica es conexa.<\/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-aab7adf elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"aab7adf\" 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-cead16a\" data-id=\"cead16a\" 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-4f42172 elementor-widget elementor-widget-toggle\" data-id=\"4f42172\" 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-8311\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-8311\" 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-8311\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-8311\"><p>Supongamos por absurdo que este grafo no es conexo, y sean x,y dos v\u00e9rtices tales que no hay camino que una x con y. Entonces, x tiene al menos p vecinos, al igual que y. Pero los vecinos de x son todos necesariamente distintos de los vecinos de y: de lo contrario, existir\u00eda una cadena de longitud 2 que une x con y.\u00a0<\/p><p>Por lo tanto, el gr\u00e1fico incluye al menos 1+1+p+p=2p+2 v\u00e9rtices (x, y, los vecinos de x, los vecinos de y). Obtenemos por tanto una contradicci\u00f3n ya que la gr\u00e1fica es de orden 2p.<\/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-faa71d8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"faa71d8\" 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-fdec89c\" data-id=\"fdec89c\" 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-4100e23 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"4100e23\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-563a7af elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"563a7af\" 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-b2efd2c\" data-id=\"b2efd2c\" 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-9a7a7c2 elementor-widget elementor-widget-heading\" data-id=\"9a7a7c2\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-9\"><\/span>Ejercicio 9<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-8db6804 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8db6804\" 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-80180bd\" data-id=\"80180bd\" 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-b2605a7 elementor-widget elementor-widget-text-editor\" data-id=\"b2605a7\" 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>Una cabra, un repollo y un lobo est\u00e1n en la orilla de un r\u00edo; un contrabandista desea transportarlos a la otra orilla pero, como su bote es demasiado peque\u00f1o, solo puede transportar uno de ellos a la vez. \u00bfC\u00f3mo debe proceder para no dejar nunca al lobo y la cabra, oa la cabra y la col, juntos y desatendidos?<\/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-bf5062e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"bf5062e\" 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-2d9eadd\" data-id=\"2d9eadd\" 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-91939e4 elementor-widget elementor-widget-toggle\" data-id=\"91939e4\" 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-1521\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1521\" 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-1521\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1521\"><p>Esta situaci\u00f3n se puede modelar usando un gr\u00e1fico. Designemos por P al barquero, por C a la cabra, por X al repollo y por L al lobo. Los v\u00e9rtices del gr\u00e1fico son pares que especifican qui\u00e9n est\u00e1 en el borde inicial, qui\u00e9n est\u00e1 en el otro borde.\u00a0<\/p><p>As\u00ed, la pareja (PCX,L) significa que el barquero est\u00e1 en la orilla inicial con la cabra y el repollo (que por lo tanto est\u00e1n bajo vigilancia), mientras que el lobo est\u00e1 en la otra orilla. Una arista conecta dos v\u00e9rtices cuando el colocador puede pasar de una situaci\u00f3n a otra.<\/p><p>Al transportar la cabra, el barquero pasa, por ejemplo, de la cima (PCX,L) a la cima (X,PCL). El grafo as\u00ed obtenido es bipartito: los v\u00e9rtices para los que el colocador est\u00e1 en la orilla inicial s\u00f3lo est\u00e1n conectados con los v\u00e9rtices para los que el colocador est\u00e1 en la otra orilla.<\/p><p>Naturalmente, no consideraremos los v\u00e9rtices de cu\u00e1l de los componentes es CX o LC porque estas situaciones est\u00e1n prohibidas. Entonces es suficiente encontrar un camino (el m\u00e1s corto por ejemplo) entre la situaci\u00f3n inicial (PCXL,-) y la situaci\u00f3n final deseada (-,PCXL). La siguiente figura da tal camino:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-19560\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe-300x113.png\" alt=\"repollo de cabra lobo\" width=\"300\" height=\"113\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe-300x113.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe-18x7.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe.png 365w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/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-5c49665 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5c49665\" 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-9c7c1be\" data-id=\"9c7c1be\" 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-727b0e0 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"727b0e0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-fa07a1b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fa07a1b\" 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-864f2c5\" data-id=\"864f2c5\" 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-f98b3b4 elementor-widget elementor-widget-heading\" data-id=\"f98b3b4\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-10\"><\/span>Ejercicio 10<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-52ae3be elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"52ae3be\" 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-6d98d8c\" data-id=\"6d98d8c\" 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-aae6225 elementor-widget elementor-widget-text-editor\" data-id=\"aae6225\" 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>En el siguiente gr\u00e1fico bipartito, los v\u00e9rtices T1,..., T6 representan trabajadores y los v\u00e9rtices E1,..., E6 puestos de trabajo. Un borde conecta a un trabajador con un trabajo si el trabajador tiene las calificaciones para ese trabajo. \u00bfC\u00f3mo asignar puestos de trabajo a los trabajadores para minimizar el n\u00famero de desempleados?<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-10806\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image19.png\" alt=\"problemas de caudal maximo ejercicios corregidos ford-fulkerson corte minimo corte minimo\" width=\"154\" height=\"148\" title=\"\"><\/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-d143ea3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d143ea3\" 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-d265058\" data-id=\"d265058\" 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-bb51900 elementor-widget elementor-widget-toggle\" data-id=\"bb51900\" 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-1961\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1961\" 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-1961\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1961\"><p>Asignar un trabajo a una persona es como &quot;seleccionar&quot; un borde. Cada persona solo puede tener un trabajo, y un trabajo solo puede ser realizado por una persona, por lo que es necesario seleccionar un n\u00famero m\u00e1ximo de aristas de tal manera que estas aristas no tengan un v\u00e9rtice com\u00fan (este conjunto se denomina m\u00e1ximo estable) .<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-10807\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image20.png\" alt=\"problemas de caudal maximo ejercicios corregidos ford-fulkerson corte minimo corte minimo\" width=\"154\" height=\"148\" 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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c5141fd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c5141fd\" 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-ce39fbb\" data-id=\"ce39fbb\" 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-6e92804 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"6e92804\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-4c92a20 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4c92a20\" 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-364757e\" data-id=\"364757e\" 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-527a419 elementor-widget elementor-widget-heading\" data-id=\"527a419\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-11\"><\/span>Ejercicio 11<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-a6aa301 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a6aa301\" 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-6b57fd5\" data-id=\"6b57fd5\" 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-2a8976c elementor-widget elementor-widget-text-editor\" data-id=\"2a8976c\" 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>Todos los d\u00edas, un grupo de 12 ni\u00f1os sale a caminar, en filas de dos. \u00bfCu\u00e1ntos d\u00edas pueden salir a pasear si no queremos que un ni\u00f1o tenga dos veces al mismo vecino? \u00bfY si ahora el paseo se hace en filas de tres?<\/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-6d68186 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6d68186\" 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-e259ab0\" data-id=\"e259ab0\" 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-a27fea7 elementor-widget elementor-widget-toggle\" data-id=\"a27fea7\" 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-1701\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1701\" 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-1701\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1701\"><p>Considere el gr\u00e1fico completo K12 con 12 v\u00e9rtices, cada v\u00e9rtice representa a un ni\u00f1o. El n\u00famero de aristas en este gr\u00e1fico es 12 x 11 \/ 2 = 66. Un paseo corresponde a un conjunto de 6 aristas no incidentes (que no tienen v\u00e9rtice en com\u00fan): cada arista representa una fila (dos ni\u00f1os) y cada ni\u00f1o solo puede pertenecen a una fila durante un viaje.<\/p><p>Por tanto, es necesario encontrar el mayor n\u00famero de conjuntos (11 = 66\/6) respetando esta regla:<\/p><p>1-2, 3-12, 4-11, 5-10, 6-9, 7-8 ;\u00a0<span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">2-3, 12-4, 11-5, 10-6, 9-7, 8-1 ;\u00a0<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">1-3, 4-2, 5-12, 6-11, 7-10, 8-9 ;\u00a0<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">3-4, 2-5, 12-6, 11-7, 10-8, 9-1 ;\u00a0<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">1-4, 5-3, 6-2, 7-12, 8-11, 9-10 ;\u00a0<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">4-5, 3-6, 2-7, 12-8, 11-9, 10-1 ;\u00a0<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">1-5, 6-4, 7-3, 8-2, 9-12, 10-11 ;\u00a0<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-size: 1.125rem; font-weight: var( --e-global-typography-text-font-weight );\">5-6, 4-7, 3-8, 2-9, 12-10, 11-1 ;\u00a0<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-size: 1.125rem; font-weight: var( --e-global-typography-text-font-weight );\">1-6, 7-5, 8-4, 9-3, 10-2, 11-12 ;\u00a0<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-size: 1.125rem; font-weight: var( --e-global-typography-text-font-weight );\">6-7, 5-8, 4-9, 3-10, 2-11, 12-1 ;\u00a0<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-size: 1.125rem; font-weight: var( --e-global-typography-text-font-weight );\">1-7, 2-12, 3-11, 4-10, 5-9, 6-8<\/span><\/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-b2cb520 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b2cb520\" 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-c9239b5\" data-id=\"c9239b5\" 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-c54a269 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"c54a269\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-8a40194 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8a40194\" 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-6344340\" data-id=\"6344340\" 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-00cea8f elementor-widget elementor-widget-heading\" data-id=\"00cea8f\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-12\"><\/span>Ejercicio 12<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-14a9a4d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"14a9a4d\" 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-e65d211\" data-id=\"e65d211\" 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-415bea7 elementor-widget elementor-widget-text-editor\" data-id=\"415bea7\" 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>Estamos interesados en grafos en los que todos los v\u00e9rtices son de grado tres. Construya tales gr\u00e1ficos que tengan 4 v\u00e9rtices, 5 v\u00e9rtices, 6 v\u00e9rtices, 7 v\u00e9rtices. \u00bfQu\u00e9 deduces de esto?<\/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-2c9ef5e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2c9ef5e\" 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-a4ef1e2\" data-id=\"a4ef1e2\" 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-183d184 elementor-widget elementor-widget-toggle\" data-id=\"183d184\" 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-2541\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2541\" 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-2541\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2541\"><p>Los gr\u00e1ficos con todos los v\u00e9rtices de grado tres se llaman gr\u00e1ficos 3-regulares o gr\u00e1ficos c\u00fabicos. La siguiente figura muestra dos gr\u00e1ficos c\u00fabicos, que tienen 4 y 6 v\u00e9rtices respectivamente. De hecho, es f\u00e1cil ver que no hay gr\u00e1ficos c\u00fabicos con un n\u00famero impar de v\u00e9rtices: el n\u00famero de aristas de un gr\u00e1fico c\u00fabico con n v\u00e9rtices es 3n\/2, que es solo un n\u00famero entero cuando n es par.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-19561\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe2.png\" alt=\"gr\u00e1fico de grado 3\" width=\"264\" height=\"100\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe2.png 264w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe2-18x7.png 18w\" sizes=\"(max-width: 264px) 100vw, 264px\" \/><\/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-f5560f2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f5560f2\" 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-e11bc5a\" data-id=\"e11bc5a\" 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-6b7f578 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"6b7f578\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-c9a309a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c9a309a\" 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-583f7a9\" data-id=\"583f7a9\" 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-05075ec elementor-widget elementor-widget-heading\" data-id=\"05075ec\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-13\"><\/span>Ejercicio 13<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-61b8552 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"61b8552\" 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-1754530\" data-id=\"1754530\" 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-ee10fa4 elementor-widget elementor-widget-text-editor\" data-id=\"ee10fa4\" 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>Un servidor puede enrutar un m\u00e1ximo de paquetes al mismo tiempo. Siete subestaciones est\u00e1n vinculadas a un servidor, una subestaci\u00f3n no puede enviar paquetes si algunas subestaciones ya est\u00e1n utilizando el enlace. La siguiente tabla muestra la capacidad de cada subestaci\u00f3n para enviar un paquete en relaci\u00f3n con las dem\u00e1s. Por ejemplo, un paquete de A no se puede enviar si ya hay un paquete de D, pero se puede enviar cuando B ha enviado 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 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>Representar los enlaces en un gr\u00e1fico. \u00bfCu\u00e1ntos paquetes debe manejar 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-8b46076 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8b46076\" 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-c82a692\" data-id=\"c82a692\" 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-56fd7c9 elementor-widget elementor-widget-toggle\" data-id=\"56fd7c9\" 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-9121\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-9121\" 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-9121\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-9121\"><p>Representamos cada subestaci\u00f3n por un v\u00e9rtice y dos v\u00e9rtices est\u00e1n unidos si no tienen que estar juntos. As\u00ed que despu\u00e9s de un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/clic-y-coloracion-estable\/\">colorante<\/a> de un gr\u00e1fico, dos v\u00e9rtices del mismo color pueden estar juntos.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10626 size-full\" title=\"Ejercicios corregidos: teor\u00eda de grafos y coloraci\u00f3n 3\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image3.png?resize=228%2C205\" alt=\"ejercicios corregidos teor\u00eda de grafos modelado problemas de coloraci\u00f3n\" width=\"228\" height=\"205\" data-recalc-dims=\"1\" \/><\/p><p>El gr\u00e1fico es cuatricrom\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-263d8b4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"263d8b4\" 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-dc71bd9\" data-id=\"dc71bd9\" 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-4873e2a elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"4873e2a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-b423433 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b423433\" 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-b8a2bcd\" data-id=\"b8a2bcd\" 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-2936649 elementor-widget elementor-widget-heading\" data-id=\"2936649\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-14\"><\/span>Ejercicio 14<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-310ba82 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"310ba82\" 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-1d1bb24\" data-id=\"1d1bb24\" 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-537b7a7 elementor-widget elementor-widget-text-editor\" data-id=\"537b7a7\" 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>Una escuela debe pasar pruebas escritas a cuatro estudiantes: Pierre, Jean, Guillermo e Ibrahim. Siete disciplinas est\u00e1n involucradas: <a href=\"https:\/\/complex-systems-ai.com\/es\/logica-matematica-27\/\">Matem\u00e1ticas<\/a>, f\u00edsica, biolog\u00eda, franc\u00e9s, ingl\u00e9s, espa\u00f1ol e historia.<\/p><p>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.<\/p><p>\u00bfCu\u00e1l es el n\u00famero m\u00ednimo de franjas horarias que se deben proporcionar para que ning\u00fan alumno tenga que realizar dos pruebas simult\u00e1neamente? \u00bfCu\u00e1l es el n\u00famero crom\u00e1tico de un grafo completo? \u00bfC\u00f3mo enlazar 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-f3d8930 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f3d8930\" 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-a6dc78d\" data-id=\"a6dc78d\" 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-1079022 elementor-widget elementor-widget-toggle\" data-id=\"1079022\" 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-1721\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1721\" 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-1721\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1721\"><p>Un v\u00e9rtice representa una disciplina, un borde conecta dos disciplinas si no pueden tener lugar al mismo tiempo. El problema se puede resolver buscando un n\u00famero m\u00ednimo de colores. El subgrafo 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. Por experimento, el gr\u00e1fico es tricrom\u00e1tico.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10627 size-full\" title=\"Ejercicios corregidos: teor\u00eda de grafos y coloreado 4\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image4.png?resize=278%2C250\" alt=\"ejercicios corregidos teor\u00eda de grafos modelado problemas de coloraci\u00f3n\" width=\"278\" height=\"250\" data-recalc-dims=\"1\" \/><\/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-23f96c4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"23f96c4\" 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-35cb152\" data-id=\"35cb152\" 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-6271594 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"6271594\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-4efc12f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4efc12f\" 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-c203b36\" data-id=\"c203b36\" 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-aec21df elementor-widget elementor-widget-heading\" data-id=\"aec21df\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-15\"><\/span>Ejercicio 15<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-7a13e11 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7a13e11\" 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-527f0ee\" data-id=\"527f0ee\" 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-8ce48a7 elementor-widget elementor-widget-text-editor\" data-id=\"8ce48a7\" 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>El siguiente diagrama representa una encrucijada.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-19562\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe3.png\" alt=\"gr\u00e1fico de encrucijada\" width=\"259\" height=\"180\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe3.png 259w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe3-18x12.png 18w\" sizes=\"(max-width: 259px) 100vw, 259px\" \/><\/p><p>Cada ramal tiene su propio sem\u00e1foro con indicaci\u00f3n de flecha de la direcci\u00f3n autorizada, y aqu\u00ed est\u00e1n los posibles cruces de este cruce.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19563 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe4.png\" alt=\"gr\u00e1fico de encrucijada\" width=\"365\" height=\"60\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe4.png 365w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe4-300x49.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe4-18x3.png 18w\" sizes=\"(max-width: 365px) 100vw, 365px\" \/><\/p><p>Los autom\u00f3viles con luz verde no deben cruzarse, por lo que no se pueden autorizar AC y BE simult\u00e1neamente.<\/p><p>Proponer una soluci\u00f3n que permita alternar la autorizaci\u00f3n de sem\u00e1foros en esta intersecci\u00f3n.<\/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-86302e2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"86302e2\" 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-8a8ea1d\" data-id=\"8a8ea1d\" 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-a2c259c elementor-widget elementor-widget-toggle\" data-id=\"a2c259c\" 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-1701\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1701\" 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-1701\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1701\"><p>El gr\u00e1fico que modela la encrucijada se muestra a continuaci\u00f3n. Su n\u00famero crom\u00e1tico es igual a 4 (es de 4 colores y contiene un K4 que agrupa los v\u00e9rtices AC, BD, CD y DA). Un conjunto de v\u00e9rtices del mismo color, por ejemplo ED, AC, AE y CA agrupa un conjunto de caminos que se pueden realizar al mismo tiempo (sin incompatibilidad).\u00a0<\/p><p>El n\u00famero crom\u00e1tico corresponde entonces al n\u00famero m\u00ednimo de &quot;ciclos&quot; que deben respetar los sem\u00e1foros de este cruce.<\/p><p>Para nuestro ejemplo tendremos: 1. ED, AC, AE y CA 2. BA, BE, BD y EC 3. DC y DA 4. CD. Por supuesto, son posibles otras soluciones (cuatro colores).<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-19564\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe5.png\" alt=\"gr\u00e1fico de encrucijada\" width=\"272\" height=\"243\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe5.png 272w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe5-13x12.png 13w\" sizes=\"(max-width: 272px) 100vw, 272px\" \/><\/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-a640919 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a640919\" 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-dc98a2c\" data-id=\"dc98a2c\" 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-099dc55 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"099dc55\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-94bc24e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"94bc24e\" 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-0836440\" data-id=\"0836440\" 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-735338e elementor-widget elementor-widget-heading\" data-id=\"735338e\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-16\"><\/span>Ejercicio 16<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-4aacbd6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4aacbd6\" 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-627f6ac\" data-id=\"627f6ac\" 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-3ba0d3c elementor-widget elementor-widget-text-editor\" data-id=\"3ba0d3c\" 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>Considere un gr\u00e1fico no dirigido con v\u00e9rtices. Demostrar que todas las siguientes propiedades son equivalentes:<\/p><ul><li>es un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/arboles-y-arboles\/\">\u00e1rbol<\/a><\/li><li>es conexo y si quitamos una arista, el grafo ya no es conexo<\/li><li>est\u00e1 conectado con n-1 aristas<\/li><li>no tiene ciclo hasta que agregamos un borde<\/li><li>no tiene ciclo con borde n-1<\/li><li>un solo camino entre cualquier par de v\u00e9rtices<\/li><\/ul><p>\u00a1No hay soluci\u00f3n ya que est\u00e1 en el curso de los \u00e1rboles!<\/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-9ee9f85 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9ee9f85\" 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-e57b3b5\" data-id=\"e57b3b5\" 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-9fc9ee5 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"9fc9ee5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-a0fd2e6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a0fd2e6\" 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-5ee600a\" data-id=\"5ee600a\" 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-6a431ab elementor-widget elementor-widget-heading\" data-id=\"6a431ab\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-17\"><\/span>Ejercicio 17<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-4bac68b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4bac68b\" 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-c9fa8ec\" data-id=\"c9fa8ec\" 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-83ab6c0 elementor-widget elementor-widget-text-editor\" data-id=\"83ab6c0\" 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>Queremos agregar una granja en una red. El siguiente gr\u00e1fico muestra el costo de enviar energ\u00eda entre dos subestaciones de la red y la cantidad de energ\u00eda enviada por una subestaci\u00f3n. Debe colocar la bater\u00eda en una subestaci\u00f3n mientras minimiza el costo total.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10613 size-full\" title=\"Ejercicios Corregidos: Conceptos B\u00e1sicos de Teor\u00eda de Grafos 6\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image134.png?resize=321%2C157\" sizes=\"(max-width: 321px) 100vw, 321px\" srcset=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image134.png?w=321&amp;ssl=1 321w, https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image134.png?resize=300%2C147&amp;ssl=1 300w\" alt=\"Ejercicios corregidos sobre \u00e1rboles y modelado de teor\u00eda de grafos.\" width=\"321\" height=\"157\" data-recalc-dims=\"1\" \/><\/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-ea8ad0f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ea8ad0f\" 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-fffecfd\" data-id=\"fffecfd\" 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-bc1c925 elementor-widget elementor-widget-toggle\" data-id=\"bc1c925\" 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-1971\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1971\" 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-1971\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1971\"><p>Calcule la suma de todos los costos en cada subestaci\u00f3n, es decir, el costo de cada ruta entre cualquier subestaci\u00f3n y la subestaci\u00f3n elegida (borde * v\u00e9rtice).<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10614 size-full\" title=\"Ejercicios Corregidos: Conceptos B\u00e1sicos de Teor\u00eda de Grafos 7\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image135.png?resize=402%2C164\" sizes=\"(max-width: 402px) 100vw, 402px\" srcset=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image135.png?w=402&amp;ssl=1 402w, https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image135.png?resize=300%2C122&amp;ssl=1 300w\" alt=\"Ejercicios corregidos sobre \u00e1rboles y modelado de teor\u00eda de grafos.\" width=\"402\" height=\"164\" data-recalc-dims=\"1\" \/><\/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-7f43f2a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7f43f2a\" 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-5b59bff\" data-id=\"5b59bff\" 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-e096e22 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"e096e22\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-4401678 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4401678\" 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-440c3cc\" data-id=\"440c3cc\" 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-437fd1c elementor-widget elementor-widget-heading\" data-id=\"437fd1c\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-18\"><\/span>Ejercicio 18<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-861cb72 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"861cb72\" 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-403fdd2\" data-id=\"403fdd2\" 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-2d98ac5 elementor-widget elementor-widget-text-editor\" data-id=\"2d98ac5\" 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>Vamos a ver un principio muy importante en la teor\u00eda de grafos (relacionado con temas sociales) que es la centralidad (hay mucho c\u00e1lculo de centralidad).<\/p><p>Un robot camina sobre el siguiente gr\u00e1fico. Partiendo de cualquier v\u00e9rtice s, llamado v\u00e9rtice de almacenamiento, debe dejar caer un cubo en cada uno de los otros v\u00e9rtices. Tiene suficientes cubos en el v\u00e9rtice de almacenamiento, pero solo puede transportar un cubo a la vez (por lo que debe pasar por el v\u00e9rtice de almacenamiento antes de entregar otro cubo).<\/p><p>Calcula, para cada uno de los v\u00e9rtices del gr\u00e1fico, el camino m\u00ednimo que debe recorrer el robot si este v\u00e9rtice es un v\u00e9rtice de almacenamiento. \u00bfCu\u00e1l es el &quot;mejor&quot; v\u00e9rtice de almacenamiento?<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-19565\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe6.png\" alt=\"gr\u00e1fico de centralidad\" width=\"251\" height=\"103\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe6.png 251w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe6-18x7.png 18w\" sizes=\"(max-width: 251px) 100vw, 251px\" \/><\/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-84326ae elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"84326ae\" 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-f9f3095\" data-id=\"f9f3095\" 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-7a0e7e5 elementor-widget elementor-widget-toggle\" data-id=\"7a0e7e5\" 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-1271\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1271\" 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-1271\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1271\"><p>Para un v\u00e9rtice dado, es necesario calcular la suma de las longitudes de los caminos m\u00e1s cortos desde este v\u00e9rtice a los otros v\u00e9rtices (f\u00e1cil ya que estamos tratando con casi un \u00e1rbol). La siguiente figura da este valor para el v\u00e9rtice A, luego para todos los v\u00e9rtices del gr\u00e1fico. Por lo tanto, el mejor v\u00e9rtice de almacenamiento es el v\u00e9rtice X.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19566 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe7.png\" alt=\"gr\u00e1fico de centralidad\" width=\"504\" height=\"117\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe7.png 504w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe7-300x70.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe7-18x4.png 18w\" sizes=\"(max-width: 504px) 100vw, 504px\" \/><\/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-e0722ab elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e0722ab\" 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-c4cecd7\" data-id=\"c4cecd7\" 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-bb2b2bb elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"bb2b2bb\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-03e81bc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"03e81bc\" 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-5a55820\" data-id=\"5a55820\" 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-115cd00 elementor-widget elementor-widget-heading\" data-id=\"115cd00\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-19\"><\/span>Ejercicio 19<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-e28a4af elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e28a4af\" 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-f36da33\" data-id=\"f36da33\" 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-1c7ed88 elementor-widget elementor-widget-text-editor\" data-id=\"1c7ed88\" 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>La puesta en marcha de un nuevo yacimiento minero requiere la realizaci\u00f3n de un determinado n\u00famero de tareas. La siguiente tabla representa estas diferentes tareas con sus relaciones de anterioridad.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19567 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe8.png\" alt=\"gr\u00e1fico de programaci\u00f3n\" width=\"618\" height=\"241\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe8.png 618w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe8-300x117.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe8-18x7.png 18w\" sizes=\"(max-width: 618px) 100vw, 618px\" \/><\/p><p>Un v\u00e9rtice de un gr\u00e1fico de programaci\u00f3n contiene 3 elementos:<\/p><ul><li>El nombre de la tarea, la hora de finalizaci\u00f3n m\u00e1s temprana y la hora de finalizaci\u00f3n m\u00e1s tard\u00eda.<\/li><li>Un arco muestra la dependencia de una tarea respecto a otra con una ponderaci\u00f3n del n\u00famero de d\u00edas de la tarea anterior. Entonces A y B est\u00e1n vinculados con un peso de 120.<\/li><\/ul><p>(en lugar de un arco, tambi\u00e9n es posible hacer un gr\u00e1fico jer\u00e1rquico, es decir, el v\u00e9rtice m\u00e1s alto es la ra\u00edz, sus sucesores directos est\u00e1n en la siguiente altura).<\/p><p>Un v\u00e9rtice delgado est\u00e1 relacionado con tareas sin sucesor.<\/p><p>El tiempo de finalizaci\u00f3n m\u00e1s temprano es el camino m\u00e1s largo de una tarea a otra en el sentido de la jerarqu\u00eda.<\/p><p>El \u00faltimo tiempo de finalizaci\u00f3n es la ruta m\u00e1s corta en la direcci\u00f3n opuesta de la jerarqu\u00eda.<\/p><p>El camino cr\u00edtico es el camino desde la primera tarea hasta el final cuyos tiempos m\u00e1s tempranos y \u00faltimos coinciden.<\/p><p>Construya el gr\u00e1fico de programaci\u00f3n.<\/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-e203c20 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e203c20\" 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-c994eb5\" data-id=\"c994eb5\" 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-8009fe4 elementor-widget elementor-widget-toggle\" data-id=\"8009fe4\" 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-1341\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1341\" 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-1341\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1341\"><p>Al usar el <a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-planificacion\/metodo-mpm-2\/\">M\u00e9todo MPM<\/a>, obtenemos el siguiente gr\u00e1fico. Las fechas m\u00e1s tempranas y m\u00e1s tard\u00edas se calculan &quot;por niveles&quot;. Las tareas cr\u00edticas y la ruta cr\u00edtica se indican en negrita. El tiempo m\u00ednimo de finalizaci\u00f3n del conjunto se puede leer en la parte superior FIN: 1170 d\u00edas.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19568 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe9.png\" alt=\"Gr\u00e1fico de programaci\u00f3n de BPM\" width=\"402\" height=\"611\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe9.png 402w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe9-197x300.png 197w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe9-8x12.png 8w\" sizes=\"(max-width: 402px) 100vw, 402px\" \/><\/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-a38daec elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a38daec\" 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-56445a4\" data-id=\"56445a4\" 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-853baea elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"853baea\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-787ca14 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"787ca14\" 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-811a251\" data-id=\"811a251\" 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-798fffd elementor-widget elementor-widget-heading\" data-id=\"798fffd\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-20\"><\/span>Ejercicio 20<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-68c49d8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"68c49d8\" 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-04be0d7\" data-id=\"04be0d7\" 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-6ae49ec elementor-widget elementor-widget-text-editor\" data-id=\"6ae49ec\" 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>Un grupo de 9 alumnos se re\u00fane todos los d\u00edas en torno a una mesa redonda. \u00bfCu\u00e1ntos d\u00edas pueden encontrarse si no queremos que ninguno tenga dos veces el mismo vecino?<\/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-a104ab9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a104ab9\" 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-797153b\" data-id=\"797153b\" 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-9b38ee4 elementor-widget elementor-widget-toggle\" data-id=\"9b38ee4\" 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-1621\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1621\" 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-1621\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1621\"><p>Denotemos por 1,2,\u2026,9 las 9 personas y consideremos el grafo completo K9 con 9 v\u00e9rtices. Una composici\u00f3n de la tabla corresponde a un ciclo. <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/hamiltoniano-y-euleriano\/\">hamiltoniano<\/a> de K9 (un ciclo que pasa una y s\u00f3lo una vez por cada v\u00e9rtice).\u00a0<\/p><p>Si dos composiciones de mesa corresponden a dos ciclos que tienen un borde com\u00fan, significa que las dos personas conectadas por este borde se encuentran una al lado de la otra. As\u00ed, el problema consiste en determinar el n\u00famero de ciclos hamiltonianos disjuntos de K9.<\/p><p>El gr\u00e1fico K9 tiene 9 x 8 \/ 2 = 36 aristas y cada ciclo usa 9 aristas, este n\u00famero es como m\u00e1ximo igual a 4\u2026 Es efectivamente igual a 4, como lo demuestran los siguientes 4 ciclos hamiltonianos disjuntos:<\/p><p>1,2,3,9,4,8,5,7,6 \u2014 1,3,4,2,5,9,6,8,7 \u2014 1,4,5,3,6,1,7, 9.8 \u2014 1.5,6,4,7,2,8,1.9<\/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-84ec02d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"84ec02d\" 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-05c3790\" data-id=\"05c3790\" 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-2c779a9 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"2c779a9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-2debdf1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2debdf1\" 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-815ab0e\" data-id=\"815ab0e\" 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-9eb1aad elementor-widget elementor-widget-heading\" data-id=\"9eb1aad\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-21\"><\/span>Ejercicio 21<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-d9199ee elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d9199ee\" 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-3ae11da\" data-id=\"3ae11da\" 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-2e3ba4e elementor-widget elementor-widget-text-editor\" data-id=\"2e3ba4e\" 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>En esta ocasi\u00f3n, estas reuniones diarias se refieren a un grupo de 12 alumnos, 6 chicas y 6 chicos. Siempre queremos que nadie tenga dos veces al mismo vecino, pero esta vez tambi\u00e9n queremos que cada chica est\u00e9 rodeada de dos chicos. \u00bfCu\u00e1ntos d\u00edas se pueden encontrar?<\/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-4ef7f77 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4ef7f77\" 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-9355320\" data-id=\"9355320\" 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-1e29661 elementor-widget elementor-widget-toggle\" data-id=\"1e29661\" 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-3161\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-3161\" 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-3161\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-3161\"><p>La idea b\u00e1sica es la misma que en el ejercicio anterior, pero esta vez, debido a la alternancia impuesta entre ni\u00f1a y ni\u00f1o, razonamos sobre el grafo bipartito completo K6,6 (seis ni\u00f1as y seis ni\u00f1os).<\/p><p>Este gr\u00e1fico incluye 6 x 6 = 36 aristas, y cada ciclo hamiltoniano requiere 12 de ellas, por lo que hay como m\u00e1ximo 3 soluciones. De hecho, son posibles tres soluciones (fi representa a la i-\u00e9sima ni\u00f1a, gi al i-\u00e9simo ni\u00f1o), por ejemplo:<\/p><p>(f1,g1,f2,g2,f3,g3,f4,g4,f5,g5,f6,g6) \u2014 (f1,g3,f2,g4,f3,g5,f4,g6,f5,g1,f6,g2 ) \u2014<br \/>(f1,g5,f2,g6,f3,g1,f4,g2,f5,g3,f6,g4)<\/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-820ef75 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"820ef75\" 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-fecf717\" data-id=\"fecf717\" 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-ccdd7de elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"ccdd7de\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-c615fb0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c615fb0\" 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-3ea7b6e\" data-id=\"3ea7b6e\" 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-4e69909 elementor-widget elementor-widget-heading\" data-id=\"4e69909\" 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<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-22\"><\/span>Ejercicio 22<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-e029ba0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e029ba0\" 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-cc08a10\" data-id=\"cc08a10\" 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-e58ac27 elementor-widget elementor-widget-text-editor\" data-id=\"e58ac27\" 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>Un grupo de ocho personas se re\u00fanen para cenar. El gr\u00e1fico de al lado especifica las \u201cincompatibilidades de humor\u201d entre las personas de este grupo (un borde que conecta a dos personas indica que se llevan muy moderadamente\u2026).<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-19569\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe10.png\" alt=\"gr\u00e1fico hamiltoniano\" width=\"253\" height=\"194\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe10.png 253w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2023\/07\/graphe10-16x12.png 16w\" sizes=\"(max-width: 253px) 100vw, 253px\" \/><\/p><p>Proponga un plan de asientos (la mesa es redonda) para este grupo, evitando colocar a dos personas \u201cincompatibles\u201d una al lado de la otra.<\/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-8123340 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8123340\" 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-3ec9bbb\" data-id=\"3ec9bbb\" 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-5f12f43 elementor-widget elementor-widget-toggle\" data-id=\"5f12f43\" 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-9961\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-9961\" 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-9961\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-9961\"><p>Esta vez se trata de encontrar ciclos hamiltonianos en el complemento de la gr\u00e1fica. Aqu\u00ed hay uno: B,C,H,A,F,G,E,D.<\/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>P\u00e1gina de inicio de Wiki de teor\u00eda de grafos Ejercicios corregidos sobre los conceptos b\u00e1sicos de la teor\u00eda de grafos (modelado de gr\u00e1ficos y \u00e1rboles) Esta p\u00e1gina muestra algunos... <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-15062","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15062","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=15062"}],"version-history":[{"count":27,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15062\/revisions"}],"predecessor-version":[{"id":20533,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15062\/revisions\/20533"}],"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=15062"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}