{"id":357,"date":"2011-01-09T18:56:09","date_gmt":"2011-01-09T16:56:09","guid":{"rendered":"https:\/\/blogs.ua.es\/jabibics\/?p=357"},"modified":"2012-01-08T21:17:40","modified_gmt":"2012-01-08T19:17:40","slug":"capitulo-16-grafos-ponderados","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/jabibics\/2011\/01\/09\/capitulo-16-grafos-ponderados\/","title":{"rendered":"Cap\u00edtulo 16 \u201cGrafos Ponderados\u201d"},"content":{"rendered":"<p>Un grafo simple G = (V,A) diremos que es un grafo <span style=\"text-decoration: underline\">ponderado<\/span> si cada arista\/arco tiene un peso (puede ser negativo) denotado por wij.<\/p>\n<blockquote><p>Cada arco o arista tiene un peso, por ejemplo en el grafo dirigido Wbd = 21.<\/p><\/blockquote>\n<h3 style=\"text-align: center\">Grafo A \/ Grafo B<\/h3>\n<p style=\"text-align: center\"><img decoding=\"async\" class=\"aligncenter\" src=\"https:\/\/blogs.ua.es\/jabibics\/files\/2011\/01\/ponderacion.png\" alt=\"\" \/><\/p>\n<p><!--more--><br \/>\nLa<span style=\"text-decoration: underline\"> matriz de peso<\/span> contendr\u00e1 el peso de los arcos\/aristas, si el v\u00e9rtice x no es adyacente con y en la matriz pondremos Wxy = \u221e<\/p>\n<blockquote><p>Las matrices de pesos de los grafos anteriores son:<\/p><\/blockquote>\n<p style=\"text-align: center\"><img decoding=\"async\" class=\"aligncenter\" src=\"https:\/\/blogs.ua.es\/jabibics\/files\/2011\/01\/mpeso.png\" alt=\"\" \/><\/p>\n<p>En un grafo ponderado llamamos <span style=\"text-decoration: underline\">peso de un camino<\/span> a la suma de los pesos de las aristas\/arcos que lo forman.<\/p>\n<p>En un grafo ponderado llamamos <span style=\"text-decoration: underline\">camino mas corto<\/span> entre dos v\u00e9rtices al camino de menor peso entre los v\u00e9rtices.<\/p>\n<p>En un grafo ponderado llamamos <span style=\"text-decoration: underline\">camino cr\u00edtico<\/span> entre dos v\u00e9rtices al camino de peso m\u00e1ximo entre los v\u00e9rtices.<\/p>\n<p style=\"text-align: center\"><img decoding=\"async\" class=\"aligncenter\" src=\"https:\/\/blogs.ua.es\/jabibics\/files\/2011\/01\/ej.png\" alt=\"\" \/><\/p>\n<blockquote><p>Ejemplo:<\/p>\n<p>Peso del camino A,C<\/p>\n<p style=\"padding-left: 30px\">Wab + Wbc = 4<\/p>\n<p>Camino m\u00e1s corto A, F<\/p>\n<p>Camino cr\u00edticio A, F<\/p>\n<p style=\"padding-left: 30px\">Wab + Wbc + Wcd + Wdf = 10 (mayor peso)<\/p>\n<p style=\"padding-left: 30px\">Wae + Wef = 8 (menor peso)<\/p>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Un grafo simple G = (V,A) diremos que es un grafo ponderado si cada arista\/arco tiene un peso (puede ser negativo) denotado por wij. Cada arco o arista tiene un peso, por ejemplo en el grafo dirigido Wbd = 21. Grafo A \/ Grafo B<\/p>\n","protected":false},"author":1760,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10961],"tags":[],"class_list":["post-357","post","type-post","status-publish","format-standard","hentry","category-grafos"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts\/357","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/users\/1760"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/comments?post=357"}],"version-history":[{"count":22,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts\/357\/revisions"}],"predecessor-version":[{"id":459,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/posts\/357\/revisions\/459"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/media?parent=357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/categories?post=357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/jabibics\/wp-json\/wp\/v2\/tags?post=357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}