Grafo

Per a atres usos d'este terme vore Grafo (desambiguació).

Per a la teoria entorn a este objecte matemàtic vore Teoria de grafos.

En matemàticas i ciències de la computació, un grafo (del grec grafos: dibuix, image)^[1] és un conjunt d'objectes cridats vèrtiços o nodos units per enllaços cridats arestes o arcs, que permeten representar relacions binarias entre elements d'un conjunt.^[2] Són objecte d'estudi de la teoria de grafos.^[3]

Típicament, un grafo es representa gràficament com un conjunt de punts units per llínees (arestes o arcs).

Des d'un punt de vista pràctic, els grafos permeten estudiar les interrelacions entre unitats que interactuen unes en unes atres. Per eixemple, una ret de computadores pot representar-se i estudiar-se per mig d'un grafo, en el qual els vèrtiços representen terminals i les arestes representen conexions (les quals, a la seua volta, poden ser cables o conexions inalàmbriques).

Pràcticament qualsevol problema pot representar-se per mig d'un grafo, i el seu estudi transcendix a les diverses àrees de les ciències exactes i les ciències socials.

Per lo general, un grafo es representa en forma de diagrama com un conjunt de punts o círculs per als vèrtiços, units per llínees o curves per a les vores. Els grafos són un dels objectes d'estudi de les matemàtiques discretes.

Les vores poden ser dirigits o no dirigits. Per eixemple, si els vèrtiços representen persones en una festa i hi ha una aresta entre dos persones si es donen la mà, llavors este grafo no està dirigit perque qualsevol persona A pot donar-li la mà a una persona B solament si B també li dona la mà a A. Pel contrari, si una aresta d'una persona A a una persona B significa que A li deu diners a B , llavors este grafo és dirigit, perque el deute no és necessàriament recíproca.

Els grafos són el tema bàsic estudiat per la teoria de grafos. La paraula «grafo» (en anglés, graph) va ser utilisada per primera volta en este sentit per James Joseph Sylvester en 1878 per una relació directa entre les matemàtiques i l'estructura química (lo que ell va cridar una image químic-gràfica).^[4]

La teoria de grafos va nàixer en 1736 a través d'un artícul científic escrit pel matemàtic suís Leonhard Euler, a on va resoldre el problema dels ponts de Königsberg utilisant els conceptes actualment coneguts com camins i grau sobre multigrafos.

Definicions

Un grafo $G$ és un parell ordenat $G = (V, E)$ , a on:

$V$ és un conjunt de vèrtiços o nodos, i
$E$ és un conjunt d'arestes o arcs, que relacionen estos nodos.

Normalment $V$ sol ser finito. Molts resultats importants sobre grafos no són aplicables per a grafos infinits.

Es diu orde del grafo $G$ al seu número de vèrtiços, $| V |$ .

El grau d'un vèrtiç o nodo $v \in V$ és igual al número d'arcs que ho tenen com a extrem.

Un bucle és una aresta que relaciona al mateix nodo; és dir, una aresta a on el nodo inicial i el nodo final coincidixen.

Dos o més arestes són paraleles si relacionen el mateix parell de vèrtiços.

Grafo no dirigit

Artícul principal → Grafo no dirigit.

Un grafo no dirigit o grafo pròpiament dit és un grafo $G = (V, E)$ a on:

$V \neq \emptyset$
$E \subseteq {x \in 𝒫 (V) : | x | = 2}$ és un conjunt de parells no ordenats d'elements de $V$ .

Un parell no ordenat és un conjunt de la forma ${a, b}$ , de manera que ${a, b} = {b, a}$ . Per als grafos, estos conjunts pertanyen al conjunt potencia de $V$ , denotat $𝒫 (V)$ , i són de cardinalidad 2.

Grafo dirigit

Artícul principal → Grafo dirigit.

Un grafo dirigit o digrafo és un grafo $G = (V, E)$ a on:

$V \neq \emptyset$
$E \subseteq {(a, b) \in V \times V : a \neq b}$ és un conjunt de parells ordenats d'elements de $V$ .

Donada una aresta $(a, b)$ , $a$ és el seu nodo inicial i $b$ el seu nodo final.

Un grafo mixt és aquell que es definix en la capacitat de poder contindre arestes dirigides i no dirigides. Tant els grafos dirigits com els no dirigits són casos particulars d'est.

Variants sobre les definicions principals

Algunes aplicacions requerixen extensions més generals a les dos propostes clàssiques de grafos. Encara que la definició original els permet, segons l'aplicació concreta poden ser vàlits o no. A voltes $V$ o $E$ poden ser un multiconjunto, podent haver més d'una aresta entre cada parell de vèrtiços. La paraula grafo (a seques) pot permetre o no múltiples arestes entre cada parell de vèrtiços, depenent de l'autor de la referència consultada. Si es vol remarcar l'inexistència de múltiples arestes entre cada parell de vèrtiços (i en el cas no dirigit, excloure bucles) el grafo pot cridar-se simple. Per una atra part, si es vol assegurar la possibilitat de permetre múltiples arestes, el grafo pot cridar-se multigrafo (a voltes s'utilisa el terme pseudografo per a indicar que es permeten tant bucles com a múltiples arestes entre cada parell de vèrtiços).

Propietats

Adyacencia: dos arestes són adjacents si tenen un vèrtiç en comú, i dos vèrtiços són adjacents si una aresta els unix.
Incidència: una aresta és incident a un vèrtiç si esta ho unix a un atre.
Ponderació: correspon a una funció que a cada aresta li associa un valor (cost, pes, llongitut, etc.), per a aumentar l'expressivitat del model. Açò s'usa molt per a problemes d'optimisació, com el del venedor viager o del camí més curt.
Etiquetage: distinció que es fa als vèrtiços i/o arestes per mig d'una marca que els fa unívocamente distinguibles del restant.

Representació

Les dos representacions principals de grafos són les següents:

Matriu de adyacencia (MA): S'utilisa una matriu de tamany n × n a on les files i les columnes fan referència als vèrtiços per a almagasenar en cada casella la llongitut entre cada parell de vèrtiços del grafo. La cela MA[i, j] almagasena la llongitut entre el vèrtiç i i el vèrtiç j. Si el seu valor és infinit significa que no existix aresta entre eixos vèrtiços, i MA[i, i] = 0.

Llista de adyacencia (LA): S'utilisa un vector de tamany n (un element per cada vèrtiç) a on LA[i] almagasena la referència a una llista dels vèrtiços adjacents a i. En una ret esta llista almagasenarà també la llongitut de l'aresta que va des d'i al vèrtiç adjacent.

Eixemples

L'image és una representació del següent grafo:

V:={1,2,3,4,5,6}
I:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

El fet que el vèrtiç 1 siga adjacent en el vèrtiç 2 pot ser denotat com 1 2.

En la teoria de les categories una categoria pot ser considerada com un multigrafo dirigit, en els objectes com a vèrtiços i els morfismos com a arestes dirigides.
En ciències de la computació els grafos dirigits són usats per a representar màquines d'estat finito i algunes atres estructures discretes.
Una relació binaria R en un conjunt X és un grafo dirigit simple. Dos vèrtiços a, b en X estan conectats per una aresta dirigida ab si aRb.

Tipos de grafos

Grafo orientat

Una definició de grafo orientat és que és un grafo dirigit en el que com a molt un de (x, i) i (i, x) poden ser arestes del grafo. És dir, és un grafo dirigit que pot formar-se com una orientació d'un grafo no dirigit (simple).

Alguns autors utilisen "grafo orientat" en el mateix significat que "grafo dirigit". Alguns autors usen "grafo orientat" per a referir-se a qualsevol orientació d'un grafo no dirigit o multigrafo dau.

Grafo regular

Artícul principal → Grafo regular.

Un grafo regular és un grafo en el que cada vèrtiç té el mateix número de veïns, és dir, cada vèrtiç té el mateix grau. Un grafo regular en vèrtiços de grau k es diu grafo k -regular o grafo regular de grau k.

Grafo complet

Artícul principal → Grafo complet.

Un grafo complet és un grafo en el que cada parell de vèrtiços està unit per una aresta. Un grafo complet conté totes les arestes possibles.

Grafo finito

Un grafo finito és un grafo en el que el conjunt de vèrtiços i el conjunt d'arestes són conjunts finitos. En cas contrari, es denomina grafo infinit.

Comunament en teoria de grafos s'implica que els grafos discutits són finitos. Si els grafos són infinits, sol indicar-se específicament.

Grafo conectat

Artícul principal → Conectivitat (teoria de grafos).

En un grafo no dirigit, un parell desordenat de vèrtiços Plantilla:Mset es diu conectat si un camí du de x a i. En cas contrari, el parell desordenat es denomina desconectat.

Un grafo conexo és un grafo no dirigit en el que cada parell desordenat de vèrtiços del grafo està conexo. En cas contrari, es denomina "grafo desconectat".

En un grafo dirigit, un parell ordenat de vèrtiços (x, i) es diu fortament conectat si un camí dirigit du de x a i. En cas contrari, el parell ordenat es denomina débilmente conectat si un camí no dirigit va de x a i despuix de reemplaçar totes les seues arestes dirigides per arestes no dirigides. En cas contrari, el parell ordenat es denomina desconectat.

Un grafo fortament conectat és un grafo dirigit en el que cada parell ordenat de vèrtiços del grafo està fortament conectat. En cas contrari, es denomina grafo débilmente conectat si cada parell ordenat de vèrtiços del grafo està débilmente conectat. En cas contrari, es denomina grafo desconectat.

Un grafo k-conectat per vèrtiços o grafo k-conectat per arestes' és un grafo en el que cap conjunt de k - 1 vèrtiços (respectivament, arestes) que, quan s'eliminen, desconecten el grafo. Un grafo conectat per vèrtiços k a sovint es diu simplement grafo conectat per k.

Grafo bipartito

Artícul principal → Grafo bipartito.

Un grafo bipartito és un grafo simple en el que el conjunt de vèrtiços pot ser particionado en dos conjunts, W i X, de modo que no hi ha dos vèrtiços en W que compartixquen una aresta comuna i no hi ha dos vèrtiços en X que compartixquen una aresta comuna. Alternativament, és un grafo en un número cromàtic de 2.

En un grafo bipartito complet, el conjunt de vèrtiços és l'unió de dos conjunts disjuntos, W i X, de modo que cada vèrtiç en W és adjacent a cada vèrtiç en X pero no hi ha arestes dins de W o X.

Grafo de trayectòries

Artícul principal → Grafo camine.

Un grafo de camins o grafo llineal d'orde n ≥ 2 és un grafo en el que els vèrtiços es poden enumerar en un orde v₁, v₂, ... , v_n tal que les arestes són les {mset}} a on i = 1, 2, ..., n - 1. Els grafos de sendera es poden caracterisar com grafos conexos en els que el grau de tots els vèrtiços menys dos és 2 i el grau dels dos vèrtiços restants és 1. Si un grafo de sendera apareix com un subgrafo d'un atre grafo, és un camí en eixe grafo.

Grafo pla

Artícul principal → Grafo pla.

Un grafo pla és un grafo els vèrtiços del qual i arestes es poden dibuixar en un pla de manera que cap de les arestes es creue en una atra.

Grafo cíclico

Artícul principal → Grafo cicle.

Un grafo de cicle o grafo circular d'orde n ≥ 3 és un grafo en el que els vèrtiços es poden enumerar en un orde v₁, v₂, ... , v_n tal que les arestes són les Plantilla:Mset a on i = 1, 2, ... , n - 1, més l'aresta Plantilla:Mset. Els grafos de cicle poden caracterisar-se com grafos conexos en els que el grau de tots els vèrtiços és 2. Si un grafo de cicle apareix com subgrafo d'un atre grafo, és un cicle o circuit en eixe grafo.

Arbre

Artícul principal → Arbre (teoria de grafos).

Un arbre és un grafo no dirigit en el que dos vèrtiços qualssevol estan conectats per exactament una trayectòria, o equivalentemente un conectat no dirigit acíclic.

Un bosc és un grafo no dirigit en el que dos vèrtiços qualssevol estan conectats per com a molt un camí, o equivalentemente un grafo acíclic no dirigit, o equivalentemente una unió disjunta d'arbres.

Poliarbol

Artícul principal → Poliárbol.

Un poliárbol (o arbre dirigit o arbre orientat o ret uniconexa) és un grafo acíclic dirigit (DAG) que el seu grafo no dirigit subjacent és un arbre.

Un polibosque (o bosc dirigit o bosc orientat) és un grafo acíclic dirigit que el seu grafo no dirigit subjacent és un bosc.

Classes alvançades

Classes més alvançades de grafos són:

grafo de Petersen i les seues generalisacions;
grafo perfectes;
cografos;
grafo cordals;
atres grafos en grans automorfisme de grafos: transitivo de vèrtiços, transitivo d'arcs i Grafo distancia-transitivo;
grafo fortament regular i les seues generalisacions grafo regular a distància.

Grafos particulars

Existixen grafos que posseïxen propietats destacables. Alguns eixemples bàsics són:

Grafo nul: aquell que no té vèrtiços ni arestes. Note's que algunes persones exigixen que el conjunt de vèrtiços no siga buit en la definició de grafo.
Grafo buit: aquell que no té arestes.
Grafo trivial: aquell que té un vèrtiç i cap aresta.
Grafo simple: aquell que no posseïx bucles ni arestes paraleles. Consultar variants en esta definició.
Multigrafo (o pseudografo): G és multigrafo si i solament si no és simple. Consultar variants en esta definició.

Grafo complet: grafo simple en el que cada parell de vèrtiços estan units per una aresta, és dir, conté totes les possibles arestes.
Grafo bipartito: siga $(W, X)$ una partició del conjunt de vèrtiços $V$ , és aquell a on cada aresta té un vèrtiç en $W$ i un atre en $X$ .
Grafo bipartito complet: siga $(W, X)$ una partició del conjunt de vèrtiços $V$ , és aquell a on cada vèrtiç en $W$ és adjacent només a cada vèrtiç en $X$ , i viceversa.
Grafo pla: aquell que pot ser dibuixat en el pla cartesiano sense creuament d'arestes.
Arbre: grafo conexo sense cicles.
Grafo roda: grafo en n vèrtiços que es forma conectant un únic vèrtiç a tots els vèrtiços d'un cicle-(n-1).
Grafo perfecte aquell que el número cromàtic de cada subgrafo induït és igual al tamany del major clique d'eixe subgrafo.

Una generalisació dels grafos són els cridats hipergrafos.

Vore també

Referències

↑ grafo Diccionario de la lengua española
↑ Trudeau, Richard J. (1993). Dover Pub. (ed.). Introduction to Graph Theory (Edició corregida i aumentada.). ISBN 978-0-486-67870-2.
↑ Trudeau, Richard J. (1993). Introduction to Graph Theory, Corrected, enlarged republication. edició, New York: Dover Pub., pp. 19. ISBN 978-0-486-67870-2. «A graph is an object consisting of two sets called its vertex set and its edge set.»
↑
See:
- J. J. Sylvester (February 7, 1878) "Chemistry and algebra," [1] archivat en Wayback Machine. Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."
- J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," [2] archivat en Wayback Machine. American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436. Plantilla:JSTOR. The term "graph" first appears in this paper on page 65.

Enllaços externs

Commons

Archiu:Commons-logo.svg Wikimedia Commons alberga contingut multimèdia sobre Grafo.

Referències

Este artícul conté una traducció derivada de «Grafo» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] rafo Diccionario de la lengua española

[2] Trudeau, Richard J. (1993). Dover Pub. (ed.). Introduction to Graph Theory (Edició corregida i aumentada.). ISBN 978-0-486-67870-2.

[:0-3] Trudeau, Richard J. (1993). Introduction to Graph Theory, Corrected, enlarged republication. edició, New York: Dover Pub., pp. 19. ISBN 978-0-486-67870-2. «A graph is an object consisting of two sets called its vertex set and its edge set.»

[4] See:
J. J. Sylvester (February 7, 1878) "Chemistry and algebra," [1] archivat en Wayback Machine. Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," [2] archivat en Wayback Machine. American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436. Plantilla:JSTOR. The term "graph" first appears in this paper on page 65.

[5] J. J. Sylvester (February 7, 1878) "Chemistry and algebra," [1] archivat en Wayback Machine. Nature, 17 : 284. doi:10.1038/017284a0. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

[6] J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," [2] archivat en Wayback Machine. American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. doi:10.2307/2369436. Plantilla:JSTOR. The term "graph" first appears in this paper on page 65.

[1]

[2]

[3]

[4]