{"id":50,"date":"2011-01-12T18:08:58","date_gmt":"2011-01-12T18:08:58","guid":{"rendered":"https:\/\/blogs.ua.es\/alvaroyuste\/?p=50"},"modified":"2011-01-12T18:08:58","modified_gmt":"2011-01-12T18:08:58","slug":"representacion-matricial-de-grafos","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/alvaroyuste\/2011\/01\/12\/representacion-matricial-de-grafos\/","title":{"rendered":"Representaci\u00f3n Matricial de Grafos"},"content":{"rendered":"<p><strong>Matriz de Adyacencia: <\/strong>Matriz cuadrada A, donde a<sub>ij<\/sub>, es el n\u00famero de aristas que unen el v\u00e9rtice v<sub>i<\/sub> con el v<sub>j<\/sub>, o el n\u00famero de arcos que van desde v<sub>i<\/sub> hasta v<sub>j<\/sub>.<\/p>\n<ul>\n<li>En <strong>grafos no dirigidos<\/strong> es una matriz sim\u00e9trica, y los bucles cuentan por 2. Adem\u00e1s la suma de los elementos de cada columna <em>i<\/em> o de cada fila <em>i<\/em> son el grado del\u00a0v\u00e9rtice\u00a0v<sub>i<\/sub>.<\/li>\n<li>En <strong>grafos dirigidos<\/strong> la suma de las elementos de la fila <em>i<\/em> es el grado de salida del v\u00e9rtice v<sub>i<\/sub>, mientras que la suma de los elementos de una columna <em>j<\/em> es el grado de entrada del v\u00e9rtice v<sub>j<\/sub>.<\/li>\n<\/ul>\n<p>Al elevar la matriz A a <em>r<\/em>, se obtiene <strong>A<sup><em>r<\/em><\/sup><\/strong>, otra matriz cuadrada cuyos elementos a<sub>ij<\/sub> son el n\u00famero de cadenas de longitud <em>r<\/em> que van desde v<sub>i<\/sub> hasta v<sub>j<\/sub>.<\/p>\n<p><strong>Matriz de Incidencia: <\/strong>Cada fila corresponde a un v\u00e9rtice y cada columna a un arco o arista.<\/p>\n<ul>\n<li>En <strong>grafos no dirigidos<\/strong>, el elemento m<sub>ij<\/sub> puede ser: 0 si v<sub>i<\/sub> no es incidene con e<sub>j<\/sub>; 1 si v<sub>i<\/sub> es incidene con e<sub>j<\/sub>; y 2 si en v<sub>i<\/sub>, e<sub>j<\/sub> forma un bucle.<\/li>\n<li>En <strong>grafos dirigidos<\/strong>, el elemento m<sub>ij<\/sub> puede ser: 0 si v<sub>i<\/sub> no es incidene con e<sub>j<\/sub>; 1 si v<sub>i<\/sub> es v\u00e9rtice inicial de e<sub>j<\/sub>; -1 si v<sub>i<\/sub> es v\u00e9rtice final de e<sub>j<\/sub>; y 2 si en v<sub>i<\/sub>, e<sub>j<\/sub> forma un bucle.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Matriz de Adyacencia: Matriz cuadrada A, donde aij, es el n\u00famero de aristas que unen el v\u00e9rtice vi con el vj, o el n\u00famero de arcos que van desde vi hasta vj. En grafos no dirigidos es una matriz sim\u00e9trica, y los bucles cuentan por 2. Adem\u00e1s la suma de los elementos de cada columna [&hellip;]<\/p>\n","protected":false},"author":1736,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-50","post","type-post","status-publish","format-standard","hentry","category-general"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/posts\/50","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/users\/1736"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/comments?post=50"}],"version-history":[{"count":2,"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/posts\/50\/revisions"}],"predecessor-version":[{"id":52,"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/posts\/50\/revisions\/52"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/media?parent=50"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/categories?post=50"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/alvaroyuste\/wp-json\/wp\/v2\/tags?post=50"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}