Wikipedia

Teoría de grafos: Diferenzas entre revisións

Explorar o historial de forma interactiva
← Edición máis vellaEdición máis nova →
Contido eliminado Contido engadido
VisualTexto wiki
Jglamela (conversa | contribucións)
41.144 edicións
Jglamela (conversa | contribucións)
41.144 edicións
Arranxos
Liña 1:
{{enuso}}
{{Imaxe múltiple|dirección=vertical|ancho=200|foto3=Dodecahedral graph.neato.svg|foto1=Fish graph.svg|foto2=Dart graph.svg|texto=LosOs ''grafos'' son elo objetoobxecto de estudioestudo de estadesta rama de lasdas matemáticas. Arriba elo [[''grafo pez]]peixe'', enno medio elo [[''grafo arco]] y abajo el [[grafo dodecaedro]].}}A '''teoría dos grafos''' é unha rama das [[matemáticas]] e asabaixo [[ciencias da computación]] que estuda as propiedades dos [[Grafo|grafos]]. Formalmente<math />,o ''ungrafo grafododecaedro'' .}}
A '''teoría dos grafos''' é unha rama das [[matemáticas]] e as [[ciencias da computación]] que estuda as propiedades dos [[grafo]]s. Formalmente, un grafo <math>G=(V,E)</math> é unha parella ordenada na que <math>V</math> é un conxunto non baleiro de vértices e <math>E</math> é un conxunto de arestas. <math>E</math> consta de pares non ordenados de vértices, tales que se {<math>{x,y}</math>}<math>\in E</math> dise entón que <math>x</math> e <math>y</math> son adxacentes; no grafo represéntase mediante unha liña non orientada que une os devanditos vértices. Se o grafo é dirixido chámase ''digrafo'', denótase <math>D</math> e entón o par <math>(x,y)</math> é un par ordenado, e represéntase cunha frecha que vai de <math>x</math> a <math>y</math>, e dise que <math>(x,y)\in A</math>.<ref>{{Cita libro|apelidos1=Godsil|nome1=Chris|apelidos2=Royle|nome2=Gordon|título=Algebraic Graph Theory|data=2001|editorial=Springer|lugar=Nova York|lingua=en}}</ref>
G
=
(
V
,
E
)
{\displaystyl<math /> G=(<math />,E)}
é unha parella ordenada na que
<math />
{<math />}
é un conxunto non baleiro de vértices e
E {<math />}
é un conxunto de arestas.<math /> <math />
{<math /> E}
consta de pares non ordenados de vértic<math />s, tales que se {
x
,
e
{\displaystyle {<math /><nowiki>,e}}
}</nowiki>
<math />
E
{<math />}
entón dise que
<math />
{<math />}
e
e
{<math />}
son adxacentes; no grafo represéntase mediante unha liña non orientada que une os devanditos vértices.<math /> Se o grafo é dirixi<math />do chámase<math /> ''digrafo'', de<math />nótase
D
{<math />}
, e e<math />ntón o par
(
<math />
,
e
)
{\displaystyle (<math />,e)}
é un par ordenado, e represéntase cunha frecha que vai de
<math />
{<math />}
a e
{<math />}
, e dise que
(
x
,
e
)
<math />
A {\displaystyle
(x,e)\in A}
.<math /><ref>{{Cita libro|título=Algebraic Graph Theory|editorial=Springer}}</ref>
 
A teoría de grafos ten os seus fundamentos nasna [[Matemáticamatemática discreta|matemáticas discretas]] e nasna [[Matemáticamatemática aplicada|matemáticas aplicadas.]]. É unha teoría que require de diferentes conceptos de diversas áreas como [[combinatoria]], [[álxebra]], [[probabilidade]], [[xeometría]] de polígonos, [[aritmética]] e [[Topoloxía|topología.topoloxía]]. Actualmente ten maior preponderancia no campo da [[informática]], as [[ciencias da computación]] e as [[Telecomunicacións|telecomunicacións.]]. Debido á gran cantidade de aplicacións na [[optimización]] de percorridos, procesos, fluxos, e algoritmos de procuras, entre outros, xerouse toda unha nova teoría que se coñece como [[Análisis de redes|análise de redes]].<ref>CEPAL Charlas Sobre Sistemas Complejos Sociales (CCSSCS): Analisis de Redes1: https://www.youtube.com/watch?v=oy8YxTshZhI&list=UUQbp2yA-gyew7E_tzgOI36A & Analisis de Redes2: https://www.youtube.com/watch?v=1abtP36Wx24&list=UUQbp2yA-gyew7E_tzgOI36A; Curso completo en linealiña: http://www.martinhilbert.net/CCSSCS.html</ref>
 
== Historia ==
Liña 78 ⟶ 15:
En 1857, [[Arthur Cayley]] estudou e resolveu o problema de enumeración dos [[Isomería|isómeros]], compostos químicos con idéntica composición (fórmula) pero diferente [[estrutura molecular]]. Para iso representou cada [[Composto químico|composto]], nese caso [[Hidrocarburo|hidrocarburos saturados]] C<sub>n</sub>H<sub>2n+2</sub>, mediante un grafo onde os vértices representan [[átomo]]s e as arestas a existencia de [[Enlace químico|enlaces químicos]].
 
O termovocábulo ''«grafo»'', provén da expresión ''«graphic notation»'' usada por primeira vez por [[Edward Frankland]]<ref>[http://booklens.com/l-r-foulds/graph-theory-applications pag 7]</ref> e posteriormente adoptada por [[Alexander Crum Brown]] en 1884, e facía referencia á representación gráfica dos enlaces entre os átomos dunha [[molécula]].
 
O primeiro libro sobre teoría de grafos foi escrito por [[Dénes Kőnig]] e publicado en 1936.<ref>{{cita libro|apelidos=Tutte|nome=W.T.|ligazón-autor=W. T. Tutte|título=Graph Theory|editorial=Cambridge University Press|year=2001|isbn=978-0-521-79489-3|páxina=30|url=http://books.google.com/books?id=uTGhooU37h4C&pg=PA30}}.</ref>
Liña 85 ⟶ 22:
Grazas á teoría de grafos pódense resolver diversos problemas por exemplo a síntese de circuítos secuenciais, contadores ou sistemas de apertura. Utilízase para diferentes áreas por exemplo, debuxo computacional, en todas as áreas da enxeñaría.
 
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|algoritmosalgoritmo]]s como pode ser o algoritmo de [[Robert W. Floyd|Floyd]].
 
Para a administración de proxectos, utilízansutilí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|optimizando]] os tempos para concretar os mesmos.
 
A teoría dos 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.
Traído desde «https://gl.wikipedia.org/wiki/Teoría_de_grafos»