Diferencies ente revisiones de «Grafo»

Contenido eliminado Contenido añadido
m Preferencies llingüistíques
m Iguo testu: -"originalmente" +"orixinalmente"
Llinia 15:
== Hestoria y problema de les pontes de Königsberg ==
[[Archivu:Konigsberg bridges.png|frame|right|Los siete pontes de Königsberg.]]
El primer artículu científicu relativu a grafos foi escritu pol [[matemáticu]] [[Suiza|suizu]] [[Leonhard Euler]] en [[1736]]. Euler basar nel so artículu nel ''[[problema de les pontes de Königsberg]]''. La ciudá de [[Kaliningrado]], originalmenteorixinalmente ''Königsberg'', ye famosa polos sos siete [[ponte]]s que xunen dambes marxes del ríu [[Pregel]] con dos de les sos islles. Dos de les pontes xunen la islla mayor cola marxe oriental y otros dos cola marxe occidental. La islla menor ta conectada a cada marxe por una ponte y la séptima ponte xune dambes islles. El problema plantegaba lo siguiente: ¿ye posible dar un paséu empezando dende cualesquier d'estes rexones, pasando por toos les pontes, percorriendo solo una vegada cada unu y tornando al mesmu puntu de partida?
 
Abstrayendo esti problema y plantegándolo cola (entós entá básica) teoría de grafos, Euler consigue demostrar qu'el grafo acomuñáu al esquema de pontes de Königsberg nun tien solución, esto ye, nun ye posible tornar al vértiz de partida ensin pasar por dalguna aresta dos veces.
Llinia 100:
* [[Grafo planu]]: aquel que puede ser dibuxáu nel [[Coordenaes cartesianes|planu cartesianu]] ensin encruz d'arestes.
* [[Árbol (teoría de grafos)|Árbol]]: [[grafo conexu]] ensin [[Grafo ciclo|ciclo]].
* [[Grafo rueda]]: grafo con ''n'' vértices que se forma conectando un únicu vértiz a tolos vértices d'un ciclu-(''n''-1).
* [[Grafo perfectu]] aquel qu'el [[Coloración de grafos|númberu cromáticu]] de cada subgrafo inducíu ye igual al tamañu del mayor [[clique]] d'esi subgrafo.