Grafo
Esti artículu o seición necesita referencies qu'apaezan nuna publicación acreitada, como revistes especializaes, monografíes, prensa diaria o páxines d'Internet fiables. |
En matemátiques y ciencies de la computación, un grafo (del griegu grafos: dibuxu, imaxe) ye un conxuntu d'oxetos llamaos vértices o nodos xuníos por enllaces llamaos arestes o arcos, que dexen representar rellaciones binaries ente elementos d'un conxuntu.[1] Son oxetu d'estudiu de la teoría de grafos.
Típicamente, un grafo represéntase gráficamente como un conxuntu de puntos (vértices o nodos) xuníos per llinia (arestes).
Dende un puntu de vista práuticu, los grafos dexen estudiar les interrellaciones ente unidaes que interactúan unes con otres. Por casu, una rede d'ordenadores puede representase y estudiase por aciu un grafo, nel cual los vértices representen terminales y les arestes representen conexones (les cualos, de la mesma, pueden ser cables o conexones inalámbriques).
Práuticamente cualquier problema puede representase por aciu un grafo, y el so estudiu tesciende a les diverses árees de les ciencies exactes y les ciencies sociales.
Historia y problema de les pontes de Königsberg
[editar | editar la fonte]El primer artículu científicu relativu a grafos foi escritu pol matemáticu suizu Leonhard Euler en 1736. Euler basar nel so artículu nel problema de les pontes de Königsberg. La ciudá de Kaliningráu, orixinalmente Königsberg, ye famosa polos sos siete pontes que xunen dambes márxenes 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 coneutada 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 toles 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 que'l 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.
Ello ye que Euler resuelve'l problema más xeneral: ¿qué condiciones tien de satisfaer un grafo pa garantizar que puede tornase al vértiz de partida ensin pasar pola mesma aresta más d'una vegada? Si definimos como «grau» al númberu de llinies que s'atopen nun puntu d'un grafo, entós la respuesta al problema ye que les pontes d'un pueblu pueden travesase esautamente una vegada si, salvu a lo sumo dos, tolos puntos tienen un grau par.
Definiciones
[editar | editar la fonte]Un grafo ye un par ordenáu , onde:
- ye un conxuntu de vértices o nodos, y
- ye un conxuntu d'arestes o arcos, que rellacionen estos nodos.
De normal suel ser finito. Munchos resultaos importantes sobre grafos nun son aplicables pa grafos infinitos.
Llámase orde del grafo al so númberu de vértices, .
El grau d'un vértiz o nodo ye igual al númberu d'arcos que lu tienen como estremu.
Un bucle ye una aresta que rellaciona al mesmu nodo; esto ye, una aresta onde'l nodo inicial y el nodo final coinciden.
Dos o más arestes son paraleles si rellacionen el mesmu par de vértices.
Grafo non empobináu
[editar | editar la fonte]Un grafo non empobináu o grafo puramente dichu ye un grafo onde:
- ye un conxuntu de pares ensin ordenar d'elementos de .
Un par ensin ordenar ye un conxuntu de la forma , de manera que . Pa los grafos, estos conxuntos pertenecen al conxuntu potencia de , denotado , y son de cardinalidad 2.
Grafo empobináu
[editar | editar la fonte]Un grafo empobináu o digrafo ye un grafo onde:
- ye un conxuntu de pares ordenaos d'elementos de .
Dada una aresta , ye'l so nodo inicial y el so nodo final.
Por definición, los grafos empobinaos nun contienen bucles.
Un grafo mistu ye aquel que se define cola capacidá de poder contener arestes empobinaes y non empobinaes. Tanto los grafos empobinaos como los non empobinaos son casos particulares d'este.
Variantes sobre les definiciones principales
[editar | editar la fonte]Delles aplicaciones riquen estensiones más xenerales a los dos propuestes clásiques de grafos. Anque la definición orixinal dexar, según l'aplicación concreta pueden ser válidos o non. Dacuando o pueden ser un multiconjunto, pudiendo haber más d'una aresta ente cada par de vértices. La pallabra grafo (a seques) puede dexar o non múltiples arestes ente cada par de vértices, dependiendo del autor de la referencia consultada. Si quier remarcase la inesistencia de múltiples arestes ente cada par de vértices (y nel casu non empobináu, escluyir bucles) el grafo puede llamase simple. Per otra parte, si quier asegurase la posibilidá de dexar múltiples arestes, el grafo puede llamase multigrafo (dacuando utilízase'l términu pseudografo pa indicar que se dexen tanto bucles como múltiples arestes ente cada par de vértices).
Propiedaes
[editar | editar la fonte]- Axacencia: dos arista son axacentes si tienen un vértiz de mancomún, y dos vértices son axacentes si una aresta xunir.
- Incidencia: una aresta ye incidente a un vértiz si ésta xunir a otru.
- Ponderación: correspuende a una función qu'a cada aresta acomúñalu un valor (costu, pesu, llargor, etc.), p'aumentar la espresividá del modelu. Esto úsase enforma pa problemes de optimización, como'l del vendedor viaxeru o del camín más curtiu.
- Etiquetáu: distinción que se fai a los vértices y/o arestes por aciu una marca que los fai unívocamente estremables del restu.
Representación
[editar | editar la fonte]Los dos representaciones principales de grafos son les siguientes:
- Matriz d'axacencia (MA): Utilízase una matriz de tamañu n × n onde les files y les columnes faen referencia a los vértices p'almacenar en cada caxellu'l llargor ente cada par de vértices del grafo. La celda MA[i, j] almacena'l llargor ente'l vértiz i y el vértiz j. Si'l so valor ye infinitu significa que nun esiste aresta ente esos vértices, y MA[i, i] = 0.
- Llista d'axacencia (LA): Utilízase un vector de tamañu n (un elementu per cada vértiz) onde LA[i] almacena la referencia a una llista de los vértices axacentes a i. Nuna rede esta llista va almacenar tamién el llargor de l'aresta que va dende i al vértiz axacente.
Exemplos
[editar | editar la fonte]La imaxe ye una representación del siguiente grafo:
- V:={1,2,3,4,5,6}
- Y:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}
El fechu que'l vértiz 1 seya axacente col vértiz 2 pue ser denotado como 1 ~ 2.
- Na teoría de les categoríes una categoría puede ser considerada como un multigrafo empobináu, colos oxetos como vértices y los morfismos como arestes empobinaes.
- En ciencies de la computación los grafos empobinaos son usaos pa representar máquines d'estáu finito y dalgunes otres estructures discretes.
- Una rellación binaria R nun conxuntu X ye un grafo empobináu simple. Dos vértices a, b en X tán coneutaos por una aresta empobinada ab si aRb.
Grafos particulares
[editar | editar la fonte]Esisten grafos que tienen propiedaes destacables. Dellos exemplos básicos son:
- Grafo nulu: aquel que nun tien vértices nin arestes. Nótese que delles persones esixen que'l conxuntu de vértices nun seya vacíu na definición de grafo.
- Grafo vacíu: aquel que nun tien arestes.
- Grafo trivial: aquel que tien un vértiz y nenguna aresta.
- Grafo simple: aquel que nun tener bucles nin arestes paraleles. Consultar variantes nesta definición.
- Multigrafo (o pseudografo): G ye multigrafo si y solu si nun ye simple. Consultar variantes nesta definición.
- Grafo completu: grafo simple nel que cada par de vértices tán xuníos por una aresta, esto ye, contién toles posibles arestes.
- Grafo bipartitu: seya una partición del conxuntu de vértices , ye aquel onde cada aresta tien un vértiz en y otru en .
- Grafo bipartitu completu: seya una partición del conxuntu de vértices , ye aquel onde cada vértiz en ye axacente namái a cada vértiz en , y viceversa.
- Grafo planu: aquel que puede ser dibuxáu nel planu cartesianu ensin encruz d'arestes.
- Árbol: grafo conexu ensin ciclo.
- Grafo rueda: grafo con n vértices que se forma coneutando un únicu vértiz a tolos vértices d'un ciclu-(n-1).
- Grafo perfectu aquel que'l númberu cromáticu de cada subgrafo inducíu ye igual al tamañu del mayor clique d'esi subgrafo.
Una xeneralización de los grafos son los llamaos hipergrafos.
Referencies
[editar | editar la fonte]- ↑ Trudeau, Richard J. (1993). Dover Pub.: Introduction to Graph Theory (Edición correxida y aumentada.). ISBN 978-0-486-67870-2.
Ver tamién
[editar | editar la fonte]Enllaces esternos
[editar | editar la fonte]