{"id":88710,"date":"2001-02-02T00:00:00","date_gmt":"2001-02-02T00:00:00","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/extensiones-del-problema-de-coloracion-de-grafos\/"},"modified":"2001-02-02T00:00:00","modified_gmt":"2001-02-02T00:00:00","slug":"extensiones-del-problema-de-coloracion-de-grafos","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/matematicas\/extensiones-del-problema-de-coloracion-de-grafos\/","title":{"rendered":"Extensiones del problema de coloracion de grafos"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Javier Ramirez Rodriguez <\/strong><\/h2>\n<p>En este trabajo se presentan extensiones del problema de colocaci\u00f3n, al introducir el nuevo requerimiento de que el n\u00famero de colores no tiene que ser necesariamente el m\u00ednimo, esto permite modelizar otros problemas de planificaci\u00f3n del tiempo.  a este problema se le ha llamado el problema de coloraci\u00f3n robusta, y consiste en determinar una c-coloraci\u00f3ncon c colores que minimice el grado de rigidez; la rigidez de una coloraci\u00f3n distingue las aristas complementarias penaliz\u00e1ndolas cuando sus extremos comparten el mismo color.  distintas penalizaciones de las aristas complementarias permiten obtener coloraciones v\u00e1lidas con diferentes propiedades. En particular, se puede considerar el caso en que se a\u00f1adan nuevas aristas al grafo y el grado de rigidez de la coloraci\u00f3n penaliza la incompatibilidad de colores de los extremos de esas aristas a\u00f1adidas, de ah\u00ed el nombre de coloraci\u00f3n robusta.  se proponen dos algoritmos para encontrar soluciones aproximadas: uno es de enumeraci\u00f3n parcial y el otro es un h\u00edbrido de un gen\u00e9tico con uno voraz, cuyas soluciones se consideran aceptables despu\u00e9s de haber sido comparadas con las exactas,obtenidas de modelos de programaci\u00f3n matem\u00e1tica del problema.  tambi\u00e9n se presenta el problema de coloraci\u00f3n robusta generalizado, en que se relaja el concepto de incompatibilidad de una coloraci\u00f3n respecto al problema de coloraci\u00f3n robusta. Se propone un h\u00edbrido de una algoritmo gen\u00e9tico y uno voraz con el que se obtienen buenas soluciones.  finalmente se presentan dos generalizaciones difusas del problema de coloraci\u00f3n, una basada en la difuminaci\u00f3n del concepto de color y otra basada en el concepto de grafo difuso. A partir de este \u00faltimo, se introduce el concepto de n\u00famero crom\u00e1tico difuso.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Extensiones del problema de coloracion de grafos<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Extensiones del problema de coloracion de grafos <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Javier Ramirez Rodriguez <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Complutense de Madrid<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 02\/02\/2001<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Javier Ya\u00f1ez Gestoso<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: Francisco jose Cano sevilla <\/li>\n<li>Fernando Arriaga gomez (vocal)<\/li>\n<li>laureano Fernando Escudero bueno (vocal)<\/li>\n<li>\u00e1ngela Ribeiro seijas (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Javier Ramirez Rodriguez En este trabajo se presentan extensiones del problema de colocaci\u00f3n, al introducir el nuevo [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[1890,37303,6264,126,16555,11392],"tags":[37733,47785,4032,184974,6973,11396],"class_list":["post-88710","post","type-post","status-publish","format-standard","hentry","category-ciencia-de-los-ordenadores","category-heuristica","category-investigacion-operativa","category-matematicas","category-planificacion","category-programacion-entera","tag-angela-ribeiro-seijas","tag-fernando-arriaga-gomez","tag-francisco-jose-cano-sevilla","tag-javier-ramirez-rodriguez","tag-javier-yanez-gestoso","tag-laureano-fernando-escudero-bueno"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/88710","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=88710"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/88710\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=88710"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=88710"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=88710"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}