Grafu

En matemátiques y ciencies de la computación, un **grafu** (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.
Son oxetu d'estudiu de la teoría de grafos.

Típicamente, un grafu 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 grafu, 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 grafu, 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

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 grafu 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 grafu 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 grafu, 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
Un **grafu** G ye un par ordenáu G=(V,Y), onde:
* V ye un conxuntu de vértices o nodos, y 
* Y ye un conxuntu d'arestes o arcos, que rellacionen estos nodos.

De normal V suel ser finito. Munchos resultaos importantes sobre grafos nun son aplicables pa *grafos infinitos*.

Llámase **orde** del grafu G al so númberu de vértices, |V|.

El grau d'un vértiz o nodo v \in V 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.

### Grafu non empobináu

Un **grafu non empobináu ** o **grafu puramente dichu** ye un grafu G = (V, Y) onde:
* V\neq\emptyset
* Y\subseteq \{x\in\mathcal P(V): |x|=2\} ye un conxuntu de *pares ensin ordenar* d'elementos de V\,.

Un **par ensin ordenar** ye un conxuntu de la forma \{a, b\}, de manera que \{a, b\}=\{b, a\}. Pa los grafos, estos conxuntos pertenecen al conxuntu potencia de V, denotado \mathcal P(V), y son de cardinalidad 2.

### Grafu empobináu

Un **grafu empobináu** o **digrafo** ye un grafu  G = (V, Y) onde:
* V\neq\emptyset
* Y \subseteq \{(a,b) \in V \times V: a \neq b \}\, ye un conxuntu de pares ordenaos d'elementos de V\,.

Dada una aresta (a,b), a ye'l so *nodo inicial* y b el so *nodo final*.

Por definición, los grafos empobinaos nun contienen *bucles*.

Un **grafu 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
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 V o Y pueden ser un multiconjunto, pudiendo haber más d'una aresta ente cada par de vértices. La pallabra *grafu* (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 grafu puede llamase **simple**. Per otra parte, si quier asegurase la posibilidá de dexar múltiples arestes, el grafu 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
* **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
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 grafu. 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

La imaxe ye una representación del siguiente grafu:
* *V*:={1,2,3,4,5,6}
* *Y*:= 
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 grafu empobináu simple. Dos vértices *a*, *b* en *X* tán coneutaos por una aresta empobinada *ab* si *aRb*.

## Grafos particulares
Esisten grafos que tienen propiedaes destacables. Dellos exemplos básicos son:
* Grafu 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 grafu.
* Grafu vacíu: aquel que nun tien arestes.
* Grafu trivial: aquel que tien un vértiz y nenguna aresta.
* *Grafu 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.
* Grafu completu: grafu simple nel que cada par de vértices tán xuníos por una aresta, esto ye, contién toles posibles arestes.
* Grafu bipartitu: seya (W, X) una partición del conxuntu de vértices V, ye aquel onde cada aresta tien un vértiz en W y otru en X.
* Grafu bipartitu completu: seya (W, X) una partición del conxuntu de vértices V, ye aquel onde cada vértiz en W ye axacente *namái* a cada vértiz en X, y viceversa.
* Grafu planu: aquel que puede ser dibuxáu nel planu cartesianu ensin encruz d'arestes.
* Árbol: grafu conexu ensin ciclo.
* Grafu rueda: grafu con *n* vértices que se forma coneutando un únicu vértiz a tolos vértices d'un ciclu-(*n*-1).
* Grafu 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

## Ver tamién
* Grafu social
* Teoría de grafos

## Enllaces esternos