Teoría de grafos: Diferenzas entre revisións
Contido eliminado Contido engadido
ligazóna |
m Arranxos varios |
||
Liña 23:
Os grafos utilízanse tamén para modelar traxectos como o dunha liña de autobús a través das rúas dunha cidade, no que se poden obter camiños óptimos para o traxecto aplicando diversos [[algoritmo]]s como pode ser o algoritmo de [[Robert W. Floyd|Floyd]].
Para a administración de proxectos, utilízanse técnicas como a técnica de revisión e avaliación de programas (PERT) nas que se modelan os mesmos empregando grafos e [[optimización matemática
A teoría de grafos tamén serviu de inspiración para as ciencias sociais, en especial para desenvolver un concepto non metafórico de [[rede social]] que substitúe os nodos polos actores sociais e verifica a posición, centralidade e importancia de cada actor dentro da rede. Esta medida permite cuantificar e abstraer relacións complexas, de xeito que a estrutura social pode representarse graficamente. Por exemplo, unha rede social pode representar a estrutura de poder dentro dunha sociedade ao identificar os vínculos (arestas), a súa dirección e intensidade e dá idea da maneira en que o poder se transmite e a quen.
Liña 62:
=== Estrutura de lista ===
* '''Lista de incidencia''' - As arestas son representadas cun [[vector]] de pares (ordenados, se o grafo é dirixido), onde cada par representa unha das arestas.<ref>[//upload.wikimedia.org/wikipedia/commons/thumb/1/18/Incidence_list_2.svg/500px-Incidence_list_2.svg.png Ejemplo de una lista de incidencia]</ref>
* '''Lista de adxacencia''' - Cada vértice ten unha lista de vértices os cales son adxacentes a el. Isto causa redundancia nun grafo non dirixido (xa que A existe na lista de adxacencia de B e viceversa), pero as procuras son máis rápidas, a cambio dun almacenamento extra.
* '''Lista de graos''' - Tamén chamada ''secuencia de graos'' ou ''sucesión gráfica'' dun grafo non-dirixido é unha secuencia de números, que corresponde aos graos dos vértices do grafo.
=== Estruturas matriciales ===
* '''Matriz de adxacencia''' - O grafo está representado por unha matriz cadrada M de tamaño <math>n^2</math>, onde <math>n</math> é o número de vértices. Se hai unha aresta entre un vértice ''x'' e un vértice ''y'', entón o elemento <math>m_{x, y}</math> é 1, senón, é 0.
* '''Matriz de incidencia''' - O grafo está representado por unha [[Matriz (matemáticas)|matriz]] de A (arestas) por V (vértices), onde [vértice, aresta] contén a información da aresta (1 - conectado, 0 - non conectado)
<center class="">
Liña 111 ⟶ 108:
=== Bibliografía ===
* Czumaj, A., Jansen, K., Meyer auf der Heide, F., & Schiermeyer, I. (2006). Algorithmic Graph Theory. ''Oberwolfach Reports'', 379–460.
* Hinz, A. M. (2012). Graph theory of tower tasks. In ''Behavioural Neurology'' (Vol. 25, pp.
* Lohmann, G., Margulies, D. S., Horstmann, A., Pleger, B., Lepsien, J., Goldhahn, D., … Turner, R. (2010). Eigenvector centrality mapping for analyzing connectivity patterns in fMRI data of the human brain. ''PLoS ONE'', 5(4). <nowiki>http://doi.org/10.1371/journal.pon.0010232</nowiki>
* Pavlopoulos, G. a, Secrier, M., Moschopoulos, C. N., Soldatos, T. G., Kossida, S., Aerts, J., … Bagos, P. G. (2011). Using graph theory to analyze biological networks. ''BioData Mining'', 4(1), 10. Retrieved from <nowiki>http://www.biodatamining.org/content/4/1/10</nowiki>
Liña 118 ⟶ 115:
* [[Ciclo hamiltoniano]]
{{Control de autoridades}}
[[Categoría:Topoloxía]]
|