Grafu

Pa ver la teoría en redol a esti oxetu matemáticu, Teoría de grafos.

En matemátiques y ciencies de la computación, un grafu^[1] (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.^[2] 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:={{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 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

↑ Rubén Fernández Martínez (14 d'abril de 2010). Terminoloxía Matemática. Centru de Terminoloxía Asturiana.
↑ Trudeau, Richard J. (1993). Dover Pub.: Introduction to Graph Theory (Edición correxida y aumentada.). ISBN 978-0-486-67870-2.

Ver tamién

Enllaces esternos

[TERMAST_matematicos-1] Rubén Fernández Martínez (14 d'abril de 2010). Terminoloxía Matemática. Centru de Terminoloxía Asturiana.

[2] Trudeau, Richard J. (1993). Dover Pub.: Introduction to Graph Theory (Edición correxida y aumentada.). ISBN 978-0-486-67870-2.

[1]

[2]