Teoria de grafos

La teoria de grafos o teoria de gràfiques és una branca de les matemàtiques, en aplicacions en les ciències de la computació i atres ciències, que estudia les propietats dels grafos. S'han denominat grafos per a distinguir del concepte homònim de gràficas, encara que també se'ls crida aixina.

Formalment, un grafo $G = (V, E)$ és una parella ordenada en la que $V$ és un conjunt no buit de vèrtiços i $E$ és un conjunt d'arestes, a on $E$ consta de parells no ordenats de vèrtiços, tals com ${x, y} \in E$ , i llavors es diu que $x$ i $y$ són adjacents. En el grafo, esta aresta no dirigida es representa per mig d'un segment de recta que unix a dits vèrtiços. Si el grafo és dirigit se li crida dígraf, es denota $D = (V, E)$ i es representa en una flecha que va de $x$ a $y$ , llavors el parell $(x, y)$ és un parell ordenat i el fet de que l'aresta siga dirigida es denota com $(x, y) \in E$ .^[1]

La teoria de grafos té els seus fonaments en la matemàtica discreta i de la matemàtica aplicada. Esta teoria requerix de diferents conceptes de diverses àrees com combinatòria, àlgebra, provabilitat, geometria de polígons, aritmètica i topología. Actualment ha tingut major influència en el camp de l'informàtica, les ciències de la computació i telecomunicacions. Per la gran cantitat d'aplicacions en l'optimisació de recorreguts, processos, fluix, algoritmes de busques, entre uns atres, es va generar tota una nova teoria que es coneix com anàlisis de rets.^[2]

Història

L'orige de la teoria de grafos es remonta a el XVIII en el problema dels ponts de Königsberg, el qual consistia en trobar un camí que recorreguera els sèt ponts del riu Pregel (Plantilla:Coord/input/ERROR</noinclude>) en la ciutat de Königsberg, actualment Kaliningrado, de modo que es recorregueren tots els ponts passant una sola volta per cada u d'ells. El treball de Leonhard Euler sobre el problema titulat Solutio problematis ad geometriam situs pertinentis^[3] (La solució d'un problema relatiu a la geometria de la posició) en 1736, és considerat el primer resultat de la teoria de grafos. També es considera un dels primers resultats topològics en geometria (que no depén de cap mida). Este eixemple ilustra la profunda relació entre la teoria de grafos i la topología.

Després, en 1847, Gustav Kirchhoff va utilisar la teoria de grafos per a l'anàlisis de rets elèctriques publicant les seues lleis dels circuits per a calcular el voltage i la corrent en els circuits elèctrics, conegudes com lleis de Kirchhoff, considerat la primera aplicació de la teoria de grafos a un problema d'ingenieria.

En 1852, Francis Guthrie va plantejar el problema dels quatre colors, el qual afirma que és possible, utilisant solament quatre colors, colorear qualsevol mapa de països de tal forma que dos països veïns mai tinguen el mateix color. Este problema, que no va ser resolt fins a un sigle despuix per Kenneth Appel i Wolfgang Haken en 1976, pot ser considerat com el naiximent de la teoria de grafos. En tractar de resoldre-ho, els matemàtics varen definir térmens i conceptes teòrics fonamentals dels grafos.

En 1857, Arthur Cayley va estudiar i va resoldre el problema d'enumeració dels isòmers, composts químics en idèntica composició (fòrmula) pero diferent estructura molecular. Per a això va representar cada compost, en este cas hidrocarburs saturats C_nH_2n+2, per mig d'un grafo arbre a on els vèrtiços representen àtoms i les arestes l'existència d'enllaços químics.

El terme «grafo», prové de l'expressió anglesa graphic notation («notació gràfica»), usada per primera volta per Edward Frankland^[4] i posteriorment adoptada per Alexander Crum Brown en 1884 i que feya referència a la representació gràfica dels enllaços entre els àtoms d'una molècula.

El primer llibre sobre teoria de grafos va ser escrit per Dénes Kőnig i publicat en 1936.^[5]

A fins dels anys 1940 i inicis dels anys 1950, junt en els primers estudis formals de cliques o caçoles en sociomatrices^[6]^[7] i de centralidad en sociogramas,^[8]^[9]^[10] es va introduir la teoria de grafos com a ferramenta clau per a la sociometría i l'anàlisis de rets socials.^[11]

Composició d'un grafo

Arestes: Són les llínees que unixen els vèrtiços d'un grafo.
- Arestes adjacents: Dos arestes són adjacents si convergixen en el mateix vèrtiç.
- Arestes paraleles: Dos arestes són paraleles si els vèrtiços inicials i finals són el mateix vèrtiç
- Arestes cíclicas: Arestes que partixen d'un vèrtiç per a entrar en el mateix.
- Creuament: Punt a on dos arestes es creuen.

Vèrtiços: Els vèrtiços, també cridats "nodos", són els elements que formen un grafo. Cada u du associada una valència característica segons la situació, que es correspon en la cantitat d'arestes que confluïxen en dit vèrtiç.

Camí: Es denomina camí a un conjunt de vèrtiços interconectados per arestes. Dos vèrtiços estan conectats si hi ha un camí entre ells.

Tipos de grafos

Grafo simple: O simplement grafo és aquell que accepta una sola aresta unint dos vèrtiços qualssevol. Açò és equivalent a dir que una aresta qualsevol és l'única que unix dos vèrtiços específics. És la definició estàndar d'un grafo.
Multigrafo o pseudografo: És el que accepta més d'una aresta entre dos vèrtiços. Estes arestes es diuen múltiples o llaços (loops en anglés). Els grafos simples són una subclasse d'esta categoria de grafos. També se'ls crida grafos general.
Grafo dirigit: grafo orientat o dígraf. Són grafos en els quals s'ha afegit una orientació a les arestes, representada gràficament per una flecha.
Grafo etiquetat: Grafos en els quals s'ha afegit un pes a les arestes (número entero generalment) o un etiquetage als vèrtiços.
Grafo aleatori: Grafo les arestes del qual estan associades a una provabilitat.
Hipergrafo: Grafos en els quals les arestes tenen més de dos extrems, és dir, les arestes són incidents a 3 o més vèrtiços.
Grafo infinit: Grafos en conjunt de vèrtiços i arestes de cardinal infinit.
Grafo pla: Els grafos plans són aquells els vèrtiços dels quals i arestes poden ser representats sense cap intersecció entre ells. Podem establir que un grafo és pla gràcies al Teorema de Kuratowski.
Grafo regular: Un grafo és regular quan tots els seus vèrtiços tenen el mateix grau de valència.
Grafo dual: El grafo dual $G^{'}$ d'un grafo $G$ (pla), és aquell que té un vèrtiç per cada regió de $G$ , i una aresta per cada aresta en $G$ unint dos regions veïnes.

Representació de grafos

Artícul principal → Grafo (estructura de senyes).

Existixen diferents formes de representar un grafo (simple), ademés de la geomètrica i molts métodos per a almagasenar-los en una computadora. l'estructura de senyes usada depén de les característiques del grafo i l'algoritme usat per a manipular-ho. Entre les estructures més senzilles i usades es troben les llistes i les matrius, encara que freqüentment s'usa una combinació d'abdós. Les llistes són preferides en grafos dispersos perque tenen un eficient us de la memòria. Per un atre costat, les matrius proveïxen accés ràpit, pero poden consumir grans cantitats de memòria.

Estructura de llista

Llista d'incidència - Les arestes són representades en un vector de parells (ordenats, si el grafo és dirigit), a on cada parell representa una de les arestes.^[12]

Llista de adyacencia - Cada vèrtiç té una llista de vèrtiços els quals són adjacents a ell. Açò causa redundància en un grafo no dirigit (ya que A existix en la llista de adyacencia de B i viceversa), pero les busques són més ràpides, al cost d'almagasenament extra.

Llista de graus - També cridada seqüència de graus o successió gràfica d'un grafo no-dirigit és una seqüència de números, que correspon als graus dels vèrtiços del grafo.

Estructures matriciales

Matriu de adyacencia - El grafo està representat per una matriu quadrada M de tamany $n^{2}$ , a on $n$ és el número de vèrtiços. Si hi ha una aresta entre un vèrtiç $x$ i un vèrtiç $y$ , llavors l'element $m_{x, y}$ és $1$ , de lo contrari, és $0$ .

Matriu d'incidència - El grafo està representat per una matriu de $A$ (arestes) per $V$ (vèrtiços), a on [vèrtiç, aresta] conté l'informació de l'aresta ( $1$ significa conectat i $0$ no conectat).

Grafo

G = (V, A)

Conjunts

Matriu de adyacencia

Matriu d'incidència

Seqüència de graus

Llista de adyacencia

Archiu:6n-graph2.svg

\begin{matrix} V = { & 1, 2, 3, 4, 5, 6} \\ A = { & {1, 1}, {1, 2}, {1, 5}, {2, 3}, \\ {2, 5}, {3, 4}, {4, 5}, {4, 6}} \end{matrix}

(\begin{matrix} 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{matrix})

(\begin{matrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})

(4, 3, 2, 3, 3, 1)


vèrtiç	llista de adyacencia
$1$	$1, 2, 5$
$2$	$1, 3, 5$
$3$	$2, 4$
$4$	$3, 5, 6$
$5$	$1, 2, 4$
$6$	$4$

Problemes de teoria de grafos

Subgrafos, subgrafos induïts i menors

Un problema comú, denominat problema d'isomorfisme de subgrafos, és trobar un grafo fix com subgrafo d'un grafo donat. Una raó per a estar interessat en esta qüestió és que moltes propietats de grafos són heretades de subgrafos, lo que significa que un grafo té una propietat si i solament si tots els seus subgrafos a la seua volta la posseïxen. Desafortunadament, trobar subgrafos màxims d'un cert tipo sol ser un problema NP-complet. Per eixemple:

Trobar el subgrafo complet més gran es diu problema de la clique.

Un problema similar és trobar un subgrafo induït en un grafo donat. De nou, algunes propietats importants són heretades sobre subgrafos induïts, lo que significa que un grafo té una propietat si i solament si tots els subgrafos induïts la tenen. Trobar subgrafos induïts màxims d'un determinat tipo és, de nou, un problema NP-complet. Com a eixemple:

Trobar el subgrafo induït més gran sense vores o conjunt independent es denomina problema del conjunt independent.

Un atre nou problema és el problema del menor contingut, que és trobar un grafo fix com a menor d'un grafo donat. Un menor o subcontración d'un grafo és qualsevol grafo obtingut prenent un subgrafo i contraent algunes vores. Moltes propietats de grafos són heretades de menors, lo que significa que un grafo la té solament si tots els seus menors la tenen també. Per eixemple, la teorema de Wagner estipula que:

Un grafo és pla si conté com a menor ni el grafo bipartito complet ni el grafo complet.

Un problema de les mateixes característiques és el problema de la subdivisió del contingut. Una subdivisió o homeomorfisme d'un grafo és qualsevol grafo obtingut subdividiendo algunes vores. La subdivisió del contingut està relacionada en les propietats dels grafos tals com la "planeza". Per eixemple, el teorema de Kuratowski establix que:

Un grafo és pla si conté una subdivisió ni el grafo bipartito ni el grafo complet.

Un atre problema en la subdivisió de contingut és la conjectura de Kelmans-Seymour:

Cada grafo de cinc vèrtiços conectats que no és pla conté una subdivisió del grafo complet de cinc vèrtiços.

Un atre problemes de classes tenen que vore en l'alcanç per a la qual vàries espècies i generalisacions de grafos estan determinades per les seues subgrafos de punts eliminats. Per eixemple, la conjectura de la reconstrucció.

Cicles i camins hamiltonianos

Artícul principal → Cicle hamiltoniano.

Archiu:Hamiltonian path.svg

Eixemple d'un cicle hamiltoniano.

Un cicle és una successió d'arestes adjacents, a on no es recorre dos voltes la mateixa aresta, i a on es retorna al punt inicial. Un cicle hamiltoniano té ademés que recórrer tots els vèrtiços exactament una volta (llevat el vèrtiç del que partix i al com aplega).

Per eixemple, en un museu gran, lo idòneu seria recórrer totes les sales una sola volta, açò és buscar un cicle hamiltoniano en el grafo que representa el museu (els vèrtiços són les sales, i les arestes els corredors o portes entre elles).

Es parla també de camí hamiltoniano si no s'impon retornar al punt de partida, com en un museu en una única porta d'entrada. Per eixemple, un cavall pot recórrer totes les caselles d'un tauler d'escacs sense passar dos voltes per la mateixa: és un camí hamiltoniano. Un eixemple de cicle hamiltoniano és el grafo del dodecaedre.

Hui en dia, no es coneixen métodos generals per a trobar un cicle hamiltoniano en temps polinòmic, sent la busca per força bruta de tots els possibles camins o atres métodos excessivament costosos. Existixen, no obstant, métodos per a descartar l'existència de cicles o camins hamiltonianos en grafos menuts.

El problema de determinar l'existència de cicles hamiltonianos, entra en el conjunt dels NP-complets.

Archiu:Grafo ejemplo 6.png

Un grafo és pla si es pot dibuixar sense creus d'arestes. El problema de les tres cases i els tres pous té solució sobre el bou, pero no en el pla.

Grafos plans

Artícul principal → Grafo pla.

Quan un grafo o multigrafo es pot dibuixar en un pla sense que dos segments es tallen, es diu que és pla.

Un problema molt conegut és el següent: Es dibuixen tres cases i tres pous. Tots els veïns de les cases tenen el dret d'utilisar els tres pous. Com no es duen be en absolut, no volen creuar-se jamai. ¿És possible traçar els nou camins que junten les tres cases en els tres pous sense que hi haja creus?

Qualsevol disposició de les cases, els pous i els camins implica la presència d'a lo manco un creuament.

Siga $K_{n}$ el grafo complet en $n$ vèrtiços, $K_{n, p}$ és el grafo bipartito de $n$ i $p$ vèrtiços.

El joc anterior equival a descobrir si el grafo bipartito complet $K_{3, 3}$ és pla, és dir, si es pot dibuixar en un pla sense que hi haja creus, sent la resposta que no. En general, pot determinar-se que un grafo no és pla, si en el seu disseny pot trobara una estructura anàloga (coneguda com a menor) a $K_{5}$ o a $K_{3, 3}$ .

Establir qué grafos són plans no és obvi, i és un problema que té que vore en topología.

Coloració de grafos

Artícul principal → Coloració de grafos.

Si $G = (V, E)$ és un grafo no dirigit, una coloració pròpia de $G$ , ocorre quan coloreamos els vèrtiços de $G$ de modo que si $a, b$ és una aresta en $G$ llavors $a$ i $b$ tenen diferents colors (per lo tant, els vèrtiços adjacents tenen colors diferents). El número mínim de colors necessaris per a una coloració pròpia de $G$ és el número cromàtic de $G$ i s'escriu com $C (G)$ . Siga $G$ un grafo no dirigit siga $λ$ el número de colors disponibles per a la coloració pròpia dels vèrtiços de $G$ . El nostre objectiu és trobar una funció polinomial $P (G, λ)$ , en la variable $λ$ , cridada polinomi cromàtic de $G$ , que nos indique el número de coloració pròpies diferents dels vèrtiços de $G$ , usant un màxim de $λ$ colors.

Descomposició de polinomis cromàtics. Si $G = (V, E)$ és un grafo conexo i $e \in E$ , llavors $P (G, λ) = P (G + e, λ) + P (G / e, λ)$ , a on $G / e$ és el grafo s'obté per contracció d'arestes.

Per a qualsevol grafo $G$ , el terme constant en $P (G, λ)$ és $0$ .

Siga $G = (V, E) \land | E | = 0$ , la suma dels coeficients de $P (G, λ)$ és $0$ .

Siga $G = (V, E)$ tal que ${a, b} \in E \land {a, b} = e \in̸ E$ , escrivim $G + e$ per al grafo que s'obté de $G$ en afegir l'aresta $e = {a, b}$ . En identificar els vèrtiços a i b en $G$ , obtenim el subgrafo $G + + e$ de $G$ .

Teorema dels quatre colors

Artícul principal → Teorema dels quatre colors.

Este problema famós relatiu als grafos tracta sobre la cantitat de colors que són necessaris per a dibuixar un mapa polític, en la condició òbvia que dos països adjacents no puguen tindre el mateix color. Se supon que els països són d'un sol péntol, i que el món és esfèric o pla. El mapa següent mostra que tres colors no basten: si s'escomença pel país central $a$ i s'esforça un en utilisar el menor número de colors, llavors en la corona al voltant de $a$ alternen dos colors. Aplegant al país $h$ es té que introduir un quart color. Lo mateixa succeïx en $i$ si s'ampra el mateix método. No obstant, si el mapa té forma de toroide, la teorema afirma que en quatre colors no sempre és possible realisar la coloració en les característiques requerides.

La forma precisa de cada país no importa; lo únic rellevant és saber qué país toca a quin un atre. Estes senyes estan incloses en el grafo a on els vèrtiços són els països i les arestes conecten els que justament són adjacents. Llavors la qüestió equival a atribuir a cada vèrtiç un color distint del dels seus veïns.

Hem vist que tres colors no són suficients, i demostrar que en cinc sempre s'aplega, és prou fàcil. Pero la teorema dels quatre colors no és res obvi. Prova d'això és que s'han tingut que amprar ordenadors per a acabar la demostració (s'ha fet un programa que va permetre verificar una multitut de casos, lo que va aforrar moltíssim temps als matemàtics). Va ser la primera volta que la comunitat matemàtica va acceptar una demostració assistida per ordenador, lo que va crear en el seu dia una certa polèmica dins de dita comunitat.

Caracterisació de grafos

Grafo simple

Un grafo és simple si com a molt existix una aresta unint dos vèrtiços qualssevol. Açò és equivalent a dir que una aresta qualsevol és l'única que unix dos vèrtiços específics.

Un grafo que no és simple es denomina multigrafo.

En la Teoria de grafos el concepte de grafo simple és molt recorregut en la definició d'atres ents, com els de grafos complets, grafos bipartidos complets, arbres i uns atres més.

Les definicions aporten una formalisació llògica a fets abstractes o naturals, moltes voltes ya definits de forma intuïtiva. En este cas l'image de grafo simple és fàcil de reconéixer davant un atre que no ho és; be per la presència de llaços o de més d'una aresta entre els parells de vèrtiços.

Grafos conexos

Artícul principal → Grafo conexo.

Un grafo conexo és aquell en que cada parell de vèrtiços està conectat per un camí; és dir, si per a qualsevol parell de vèrtiços (a, b), existix a lo manco un camí possible des de a cap a b.

Un grafo és doblement conexo si cada parell de vèrtiços està conectat per a lo manco dos camins disjuntos; és dir, és conexo i no existix un vèrtiç tal que en traure-ho el grafo resultant siga disconexo.

És possible determinar si un grafo és conexo usant un algoritme Busca en esgambi (BFS) o Busca en profunditat (DFS).

En térmens matemàtics la propietat d'un grafo (fortament) conexo permet establir una relació d'equivalència per als seus vèrtiços, la qual du a una partició d'estos en "components (fortament) conexos", és dir, porcions del grafo, que són (fortament) conexas quan es consideren com grafos aïllats. Esta propietat és important per a moltes demostracions en teoria de grafos.

Archiu:Grafos conexos y no conexos.png

Un grafo conexo (esquerra) i un no conexo (dreta).

Grafos complets

Artícul principal → Grafo complet.

Un grafo és complet si existixen arestes unint tots els parells possibles de vèrtiços. És dir, tot parell de vèrtiços (a, b) deu tindre una aresta i que els unix.

El conjunt dels grafos complets és denominat usualment $K$ , sent $K_{n}$ el grafo complet de $n$ vèrtiços.

Un $K_{n}$ , és dir, grafo complet de $n$ vèrtiços té exactament $\frac{n (n - 1)}{2}$ arestes.

La representació gràfica dels $K_{n}$ com els vèrtiços d'un polígon regular dona conte de la seua peculiar estructura.

Grafos bipartitos

Artícul principal → Grafo bipartito.

Un grafo G és bipartito si pot expressar com $G = {V_{1} \cup V_{2}, A}$ (és dir, els seus vèrtiços són l'unió de dos grups de vèrtiços), baixe les següents condicions:

$V_{1}$ i $V_{2}$ són disjuntos i no buits.
Cada aresta de $A$ unix un vèrtiç de $V_{1}$ en un de $V_{2}$ .
No existixen arestes unint dos elements de $V_{1}$ ; análogamente per a $V_{2}$ .

Baixe estes condicions, el grafo es considera bipartito, i pot descriure's informalmente com el grafo que unix o relaciona dos conjunts d'elements diferents, com aquells resultants dels eixercicis i rompecabezas en els que deu unir-se un element de la columna A en un element de la columna B.

Homeomorfisme de grafos

Artícul principal → Homeomorfisme de grafos.

Dos grafos $G_{1}$ i $G_{2}$ són homeomorfos si abdós poden obtindre's a partir del mateix grafo en una successió de subdivisions elementals d'arestes.

Arbres

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

Archiu:Grafo ejemplo 3 árbol.png

Eixemple d'arbre.

Un grafo que no té cicles i que conecta a tots els punts, es diu un arbre. En un grafo en n vèrtiços, els arbres tenen exactament n - 1 arestes, i hi ha n^n-2 arbres possibles. La seua importància radica que els arbres són grafos que conecten tots els vèrtiços utilisant el menor número possible d'arestes. Un important camp d'aplicació del seu estudi es troba en l'anàlisis filogenético, el de la filiació d'entitats que deriven unes d'atres en un procés evolutiu, que s'aplica sobretot a la desburgació del parentesc entre espècies; encara que s'ha usat també, per eixemple, en l'estudi del parentesc entre llengües.

Grafos ponderats o etiquetages

Artícul principal → Grafo ponderat.

En molts casos, cal atribuir a cada aresta un número específic, cridat valuación, ponderació o cost segons el context, i s'obté aixina un grafo ponderat. Formalment, és un grafo en una funció v: A → R₊.

Per eixemple, un representant comercial té que visitar n ciutats conectades entre sí per carreteres; el seu interés previsible serà minimisar la distància recorreguda (o el temps, si es poden prevore emboços). El grafo corresponent tindrà com a vèrtiços les ciutats, com a arestes les carreteres i la valuación serà la distància entre elles.

Diàmetro

Artícul principal → Distància (teoria de grafos).

Archiu:Grafo ejemplo 7.png

En la figura es nota que K₄ és pla (desviant l'aresta ab a l'exterior del quadrat), que K₅ no ho és, i que K₃,₂ ho és també (desviacions en grisa).

En un grafo, la distància entre dos vèrtiços és el menor número d'arestes d'un recorregut entre ells. El diàmetro, en una figura com un grafo, és la major distància entre tots els parells de punts de la mateixa.

El diàmetro dels $K_{n}$ és 1, i el dels $K_{n, p}$ és 2. Un diàmetro infinit pot significar que el grafo té una infinitat de vèrtiços o simplement que no és conexo. També es pot considerar el diàmetro promig, com el promig de les distàncies entre dos vèrtiços.

Una aplicació d'este concepte és l'hipòtesis coneguda com els sis graus de separació, que planteja que, si cada u dels habitants de la Terra es representa per un vèrtiç i dos persones estan conectades per una aresta si es coneixen personalment, la distància entre dos persones triades a l'encert entre tots els habitants de la Terra és de sis arestes o menys.

Internet permet de vore des d'un atre enfocament l'idea del diàmetro: considere's per eixemple que si es descarten els llocs que no tenen enllaços, i es trien dos pàgines web al encert, caldria preguntar-se en quants clics es pot passar del primer lloc al segon. Si se supon que de qualsevol lloc que enllace en atres llocs es pot aplegar a qualsevol un atre, llavors les major cantitat de clics necessaris per a aplegar de qualsevol web a una atra seria el "diàmetro" de la Ret, vista com un grafo els vèrtiços del qual són els llocs, i les arestes dels quals són els enllaços entre els llocs.

Este concepte reflectix millor la complexitat d'una ret que el número dels seus elements.

Aplicacions

La teoria de grafos és clau en la sociometría i l'anàlisis de rets socials.^[11] També s'ha utilisat en vàries àrees de les ciències socials, tals com l'antropologia,^[13]^[14]^[15] psicologia social,^[16]^[17] comunicació, negocis, investigació d'organisacions i geografia.^[18]^[19]^[20]

Gràcies a la teoria de grafos es poden resoldre diversos problemes com per eixemple la síntesis de circuits seqüencials, contadors o sistemes d'obertura. S'utilisa per a diferents àrees com poden ser el Dibuix computacional o en àrees d'Ingenieria.

Els grafos s'utilisen també per a modelar trayectes com el d'una llínea d'autobús a través dels carrers d'una ciutat, en el que es poden obtindre camins òptims per al trayecte aplicant diversos algoritmes com pot ser l'algoritme de Floyd.

Per a l'administració de proyectes, utilisem tècniques com tècnica de revisió i evaluació de programes (PERT) en les que es modelen els mateixos utilisant grafos i optimisant els temps per a concretar els mateixos.

Una important aplicació de la teoria de grafos és en el camp de l'informàtica, ya que ha servit per a la resolució d'importants i complexos algoritmes. Un clar eixemple és l'Algoritme de Dijkstra, utilisat per a la determinació del camí més curt en el recorregut d'un grafo en determinats pesos en els seus vèrtiços.

Dins d'este camp, un grafo és considerat un tipo de senya abstracta TAD.

El científic nortamericà Donald Knuth va establir els grafos plans com a base de determinats estudis i descobriments realisats per ell.

Per una atra part, destaca l'Algoritme de Kruskal, el qual nos permet buscar un subconjunt d'arestes que inclou tots els vèrtiços, establint com a mínim el valor de les arestes.

S'ampra en problemes de control de producció, per a proyectar rets d'ordenadors, per a dissenyar mòduls electrònics moderns i proyectar sistemes físics en paràmetros localisats (mecànics, acústics i elèctrics).

S'usa per a la solució de problemes de genètica i problemes d'automatisació de la proyecció (SAPR). Respal matemàtic dels sistemes moderns per al processament de l'informació. Acodix en les investigacions nuclears (tècnica de diagrames de Feynman).^[21]

Els grafos són importants en l'estudi de la biologia i hàbitat. El vèrtiç representa un hàbitat i les arestes (o "edges" en anglés) representa les senderes dels animals o les migracions. En esta informació, els científics poden entendre cóm açò pot canviar o afectar a les espècies en el seu hàbitat.

Mapes conceptuals

Mapes conceptuals
Pla d'estacions del metro.

Pla d'estacions del metro.
Pla d'autopistas.
Circuit elèctric
Sociograma d'una ret social
Topología de ret de computadorés
Organigramas
Isomeros

Isomeros
Arquitectura de rets de telefonia mòvil

Arquitectura de rets de telefonia mòvil
Draws d'eliminació directa (ej: tenis)

Algoritmes importants

Vore també

Referències

↑ Godsil, Chris and Royle, Gordon (2001). Algebraic Graph Theory, New York: Springer.
↑ CEPAL Charrades Sobre Sistemes Complexos Socials (CCSSCS): Analisis de Rets1: https://www.youtube.com/watch?v=oy8YxTshZhI&list=UUQbp2ya-gyew7I_tzgOI36A & Analisis de Rets2: https://www.youtube.com/watch?v=1abtP36Wx24&list=UUQbp2ya-gyew7I_tzgOI36A; Curs complet en llínea: http://www.martinhilbert.net/CCSSCS.html
↑ Euler, L.(1736).8
↑ http://booklens.com/l-r-foulds/graph-theory-applications pag 7
↑ (2001).«Graph Theory».Cambridge University Press..
↑ (1949).Human Relations.2
153-158.
↑ (1950).Sociometry.13
131-140.
↑ (1948).Human Organizations.7
16-30.
↑ (1950).Journal of the Acoustical Society of America.22
271-282.
↑ (1951).Journal of Abnormal and Social Psychology.46
38-50.
↑ ^11,0 ^11,1 Wasserman y Faust, 2013, «Notacions per a les senyes de rets socials», pp. 99-120.
↑ Eixemple d'una llista d'incidència
↑ (1980) Numerical Techniques in Social Anthropology, Filadèlfia: Institute for the Study of Human Issues.
↑ (1979).Annual Review of Anthropology.8
115-136.
↑ (1983) Structural Models in Anthropology, Cambridge: Cambridge University Press.
↑ Heider, F. (1958). The Psychology of Interpersonal Relations, Nova York: John Wiley and Sons.
↑ (1948).Human Organizations.7
16-30.
↑ (1965).The Proffesional Geographer.17
15-20.
↑ (1979).Social Networks.1
285-292.
↑ Wasserman y Faust, 2013, «Grafos i matrius» (per Dawn Iacobucci), pp. 121-188.
↑ Gorbátov:Fonaments de la matemàtica discreta

Bibliografia

(2013) Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.

Enllaços externs

Commons

Wikimedia Commons alberga contingut multimèdia sobre Teoria de grafos.
Wikilibros dispon d'un text de Glossari de teoria de grafos
El contenido de este artículo incorpora material de una entrada de la Enciclopedia Libre Universal, publicada en español bajo la licencia Creative Commons Compartir-Igual 3.0.

Referències

Este artícul conté una traducció derivada de «Teoría de grafos» 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] Godsil, Chris and Royle, Gordon (2001). Algebraic Graph Theory, New York: Springer.

[2] CEPAL Charrades Sobre Sistemes Complexos Socials (CCSSCS): Analisis de Rets1: https://www.youtube.com/watch?v=oy8YxTshZhI&list=UUQbp2ya-gyew7I_tzgOI36A & Analisis de Rets2: https://www.youtube.com/watch?v=1abtP36Wx24&list=UUQbp2ya-gyew7I_tzgOI36A; Curs complet en llínea: http://www.martinhilbert.net/CCSSCS.html

[3] Euler, L.(1736).8

[4] ttp://booklens.com/l-r-foulds/graph-theory-applications pag 7

[5] (2001).«Graph Theory».Cambridge University Press..

[6] (1949).Human Relations.2
153-158.

[7] (1950).Sociometry.13
131-140.

[8] (1948).Human Organizations.7
16-30.

[9] (1950).Journal of the Acoustical Society of America.22
271-282.

[10] (1951).Journal of Abnormal and Social Psychology.46
38-50.

[WF13.c3-11] 11,0 ^11,1 Wasserman y Faust, 2013, «Notacions per a les senyes de rets socials», pp. 99-120.

[12] Eixemple d'una llista d'incidència

[13] (1980) Numerical Techniques in Social Anthropology, Filadèlfia: Institute for the Study of Human Issues.

[14] (1979).Annual Review of Anthropology.8
115-136.

[15] (1983) Structural Models in Anthropology, Cambridge: Cambridge University Press.

[16] Heider, F. (1958). The Psychology of Interpersonal Relations, Nova York: John Wiley and Sons.

[17] (1948).Human Organizations.7
16-30.

[18] (1965).The Proffesional Geographer.17
15-20.

[19] (1979).Social Networks.1
285-292.

[WF13.c4-20] Wasserman y Faust, 2013, «Grafos i matrius» (per Dawn Iacobucci), pp. 121-188.

[21] Gorbátov:Fonaments de la matemàtica discreta

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]