{"id":2794,"date":"2022-08-13T20:12:15","date_gmt":"2022-08-13T20:12:15","guid":{"rendered":"https:\/\/pcyti.izt.uam.mx\/?p=2794"},"modified":"2022-08-13T20:12:15","modified_gmt":"2022-08-13T20:12:15","slug":"solucion-a-problemas-de-coloracion-clasicos-utilizando-coloracion-de-graficas-suaves","status":"publish","type":"post","link":"https:\/\/pcyti.izt.uam.mx\/?p=2794","title":{"rendered":"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves"},"content":{"rendered":"\n<p><a href=\"https:\/\/pcyti.izt.uam.mx\/wordpress\/wp-content\/uploads\/Propuesta-Col-Clasica-con-CGS-v0.3.pdf\" target=\"_blank\" rel=\"noreferrer noopener\">&nbsp;Descargar versi\u00f3n PDF<\/a><\/p>\n\n\n\n<p><strong>Profesores<\/strong>:&nbsp;<a href=\"https:\/\/pcyti.izt.uam.mx\/wordpress\/?page_id=198&amp;SingleProduct=195\">Dr.&nbsp;Pedro Lara Vel\u00e1zquez<\/a>&nbsp;y&nbsp;<a href=\"https:\/\/pcyti.izt.uam.mx\/wordpress\/?page_id=198&amp;SingleProduct=194\">Dr.&nbsp;Miguel \u00c1ngel Guti\u00e9rrez Andrade<\/a><\/p>\n\n\n\n<p><strong>Resumen<\/strong>:&nbsp;La coloraci\u00f3n de grafos es omnipresente en el modelado de aplicaciones del mundo real; por ejemplo, para mostrar asignaci\u00f3n de frecuencias en problemas de telecomunicaci\u00f3n; asignaci\u00f3n de registros en un sistema operativo, programaci\u00f3n de tareas; entre otras. La coloraci\u00f3n de grafos se presenta en una gran variedad de formas de las cuales, la Coloraci\u00f3n de Gr\u00e1ficas Suaves (CGS) es considerada una generalizaci\u00f3n del problema de coloraci\u00f3n de gr\u00e1ficas. &nbsp;El problema de Coloraci\u00f3n de Gr\u00e1ficas Suaves se ha utilizado recientemente en problemas de clasificaci\u00f3n y de reconocimiento de patrones en general. En este problema tenemos que, dada una gr\u00e1fica con ponderaciones en las aristas, el objetivo es encontrar una coloraci\u00f3n que minimice la suma de las aristas con el mismo color en ambos extremos; es decir, la suma de las penalizaciones&nbsp;denominada dureza. Asimismo, existen otros par\u00e1metros importantes en la Coloraci\u00f3n de Gr\u00e1ficas Suaves como lo son la solidez, la cual proporciona un valor promedio de las penalizaciones de la gr\u00e1fica y resilencia que permite encontrar una cantidad adecuada de colores. Es sabido que este problema es del tipo NP-duro y es necesario el uso de metaheur\u00edsticas en instancias mayores a 20 v\u00e9rtices.<\/p>\n\n\n\n<p><strong>Objetivo&nbsp;general<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Desarrollar un algoritmo que resuelva varios problemas cl\u00e1sicos de coloraci\u00f3n utilizando el enfoque de coloraci\u00f3n de gr\u00e1ficas suaves<\/li><\/ul>\n\n\n\n<p><strong>Objetivos espec\u00edficos<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Realizar un estudio del estado del arte de los problemas de coloraci\u00f3n cl\u00e1sicos, as\u00ed como su representaci\u00f3n como gr\u00e1fica suave<\/li><li>Compilaci\u00f3n de instancias benchmark cl\u00e1sicas de cada uno de los problemas que se estudiar\u00e1n<\/li><li>Desarrollo de los algoritmos de soluci\u00f3n<\/li><li>An\u00e1lisis de resultados y conclusiones<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp;Descargar versi\u00f3n PDF Profesores:&nbsp;Dr.&nbsp;Pedro Lara Vel\u00e1zquez&nbsp;y&nbsp;Dr.&nbsp;Miguel \u00c1ngel Guti\u00e9rrez Andrade Resumen:&nbsp;La coloraci\u00f3n de grafos es omnipresente en el modelado de aplicaciones del mundo real; por ejemplo, para mostrar asignaci\u00f3n de frecuencias en problemas de telecomunicaci\u00f3n; asignaci\u00f3n de registros en un sistema operativo, programaci\u00f3n de tareas; entre otras. La coloraci\u00f3n de grafos se presenta en una gran<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_lmt_disableupdate":"","_lmt_disable":"","footnotes":""},"categories":[80],"tags":[],"class_list":["post-2794","post","type-post","status-publish","format-standard","hentry","category-80"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.2 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/pcyti.izt.uam.mx\/?p=2794\" \/>\n<meta property=\"og:locale\" content=\"es_MX\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\" \/>\n<meta property=\"og:description\" content=\"&nbsp;Descargar versi\u00f3n PDF Profesores:&nbsp;Dr.&nbsp;Pedro Lara Vel\u00e1zquez&nbsp;y&nbsp;Dr.&nbsp;Miguel \u00c1ngel Guti\u00e9rrez Andrade Resumen:&nbsp;La coloraci\u00f3n de grafos es omnipresente en el modelado de aplicaciones del mundo real; por ejemplo, para mostrar asignaci\u00f3n de frecuencias en problemas de telecomunicaci\u00f3n; asignaci\u00f3n de registros en un sistema operativo, programaci\u00f3n de tareas; entre otras. La coloraci\u00f3n de grafos se presenta en una gran\" \/>\n<meta property=\"og:url\" content=\"https:\/\/pcyti.izt.uam.mx\/?p=2794\" \/>\n<meta property=\"og:site_name\" content=\"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/pcyti\/\" \/>\n<meta property=\"article:published_time\" content=\"2022-08-13T20:12:15+00:00\" \/>\n<meta name=\"author\" content=\"pcyti\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Escrito por\" \/>\n\t<meta name=\"twitter:data1\" content=\"pcyti\" \/>\n\t<meta name=\"twitter:label2\" content=\"Tiempo de lectura\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutos\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/pcyti.izt.uam.mx\/?p=2794#article\",\"isPartOf\":{\"@id\":\"https:\/\/pcyti.izt.uam.mx\/?p=2794\"},\"author\":{\"name\":\"pcyti\",\"@id\":\"https:\/\/pcyti.izt.uam.mx\/#\/schema\/person\/9d093e256d84249d175f986d409d857d\"},\"headline\":\"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves\",\"datePublished\":\"2022-08-13T20:12:15+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/pcyti.izt.uam.mx\/?p=2794\"},\"wordCount\":338,\"publisher\":{\"@id\":\"https:\/\/pcyti.izt.uam.mx\/#organization\"},\"articleSection\":[\"2016\"],\"inLanguage\":\"es\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/pcyti.izt.uam.mx\/?p=2794\",\"url\":\"https:\/\/pcyti.izt.uam.mx\/?p=2794\",\"name\":\"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\",\"isPartOf\":{\"@id\":\"https:\/\/pcyti.izt.uam.mx\/#website\"},\"datePublished\":\"2022-08-13T20:12:15+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/pcyti.izt.uam.mx\/?p=2794#breadcrumb\"},\"inLanguage\":\"es\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/pcyti.izt.uam.mx\/?p=2794\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/pcyti.izt.uam.mx\/?p=2794#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Inicio\",\"item\":\"https:\/\/pcyti.izt.uam.mx\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/pcyti.izt.uam.mx\/#website\",\"url\":\"https:\/\/pcyti.izt.uam.mx\/\",\"name\":\"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/pcyti.izt.uam.mx\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/pcyti.izt.uam.mx\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"es\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/pcyti.izt.uam.mx\/#organization\",\"name\":\"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\",\"url\":\"https:\/\/pcyti.izt.uam.mx\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"es\",\"@id\":\"https:\/\/pcyti.izt.uam.mx\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/pcyti.izt.uam.mx\/wp-content\/uploads\/2021\/12\/logo_pcyti_small.png\",\"contentUrl\":\"https:\/\/pcyti.izt.uam.mx\/wp-content\/uploads\/2021\/12\/logo_pcyti_small.png\",\"width\":71,\"height\":100,\"caption\":\"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n\"},\"image\":{\"@id\":\"https:\/\/pcyti.izt.uam.mx\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/pcyti\/\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/pcyti.izt.uam.mx\/#\/schema\/person\/9d093e256d84249d175f986d409d857d\",\"name\":\"pcyti\",\"url\":\"https:\/\/pcyti.izt.uam.mx\/?author=2\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/pcyti.izt.uam.mx\/?p=2794","og_locale":"es_MX","og_type":"article","og_title":"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","og_description":"&nbsp;Descargar versi\u00f3n PDF Profesores:&nbsp;Dr.&nbsp;Pedro Lara Vel\u00e1zquez&nbsp;y&nbsp;Dr.&nbsp;Miguel \u00c1ngel Guti\u00e9rrez Andrade Resumen:&nbsp;La coloraci\u00f3n de grafos es omnipresente en el modelado de aplicaciones del mundo real; por ejemplo, para mostrar asignaci\u00f3n de frecuencias en problemas de telecomunicaci\u00f3n; asignaci\u00f3n de registros en un sistema operativo, programaci\u00f3n de tareas; entre otras. La coloraci\u00f3n de grafos se presenta en una gran","og_url":"https:\/\/pcyti.izt.uam.mx\/?p=2794","og_site_name":"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","article_publisher":"https:\/\/www.facebook.com\/pcyti\/","article_published_time":"2022-08-13T20:12:15+00:00","author":"pcyti","twitter_card":"summary_large_image","twitter_misc":{"Escrito por":"pcyti","Tiempo de lectura":"2 minutos"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/pcyti.izt.uam.mx\/?p=2794#article","isPartOf":{"@id":"https:\/\/pcyti.izt.uam.mx\/?p=2794"},"author":{"name":"pcyti","@id":"https:\/\/pcyti.izt.uam.mx\/#\/schema\/person\/9d093e256d84249d175f986d409d857d"},"headline":"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves","datePublished":"2022-08-13T20:12:15+00:00","mainEntityOfPage":{"@id":"https:\/\/pcyti.izt.uam.mx\/?p=2794"},"wordCount":338,"publisher":{"@id":"https:\/\/pcyti.izt.uam.mx\/#organization"},"articleSection":["2016"],"inLanguage":"es"},{"@type":"WebPage","@id":"https:\/\/pcyti.izt.uam.mx\/?p=2794","url":"https:\/\/pcyti.izt.uam.mx\/?p=2794","name":"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves - Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","isPartOf":{"@id":"https:\/\/pcyti.izt.uam.mx\/#website"},"datePublished":"2022-08-13T20:12:15+00:00","breadcrumb":{"@id":"https:\/\/pcyti.izt.uam.mx\/?p=2794#breadcrumb"},"inLanguage":"es","potentialAction":[{"@type":"ReadAction","target":["https:\/\/pcyti.izt.uam.mx\/?p=2794"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/pcyti.izt.uam.mx\/?p=2794#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Inicio","item":"https:\/\/pcyti.izt.uam.mx\/"},{"@type":"ListItem","position":2,"name":"Soluci\u00f3n a problemas de coloraci\u00f3n cl\u00e1sicos utilizando Coloraci\u00f3n de Gr\u00e1ficas Suaves"}]},{"@type":"WebSite","@id":"https:\/\/pcyti.izt.uam.mx\/#website","url":"https:\/\/pcyti.izt.uam.mx\/","name":"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","description":"","publisher":{"@id":"https:\/\/pcyti.izt.uam.mx\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/pcyti.izt.uam.mx\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"es"},{"@type":"Organization","@id":"https:\/\/pcyti.izt.uam.mx\/#organization","name":"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n","url":"https:\/\/pcyti.izt.uam.mx\/","logo":{"@type":"ImageObject","inLanguage":"es","@id":"https:\/\/pcyti.izt.uam.mx\/#\/schema\/logo\/image\/","url":"https:\/\/pcyti.izt.uam.mx\/wp-content\/uploads\/2021\/12\/logo_pcyti_small.png","contentUrl":"https:\/\/pcyti.izt.uam.mx\/wp-content\/uploads\/2021\/12\/logo_pcyti_small.png","width":71,"height":100,"caption":"Posgrado en Ciencias y Tecnolog\u00edas de la Informaci\u00f3n"},"image":{"@id":"https:\/\/pcyti.izt.uam.mx\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/pcyti\/"]},{"@type":"Person","@id":"https:\/\/pcyti.izt.uam.mx\/#\/schema\/person\/9d093e256d84249d175f986d409d857d","name":"pcyti","url":"https:\/\/pcyti.izt.uam.mx\/?author=2"}]}},"modified_by":"pcyti","_links":{"self":[{"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/posts\/2794","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2794"}],"version-history":[{"count":0,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=\/wp\/v2\/posts\/2794\/revisions"}],"wp:attachment":[{"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2794"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2794"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/pcyti.izt.uam.mx\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2794"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}