Enteoria de grafs, ungraf és una representació abstracta d'un conjunt d'objectes on alguns parells dels objectes estan connectats per enllaços. Els objectes interconnectats són representats per abstraccions matemàtiques anomenadesvèrtexs, i els enllaços que connecten alguns parells de vèrtexs s'anomenenarestes. Típicament, un graf es descriu de forma esquemàtica com a conjunt de punts o cercles per als vèrtexs, units per línies o corbes per les arestes. Els grafs són un dels objectes d'estudi de lamatemàtica discreta.
Les arestes poden ser dirigides o no dirigides. Per exemple, un graf es pot construir escollint com a vèrtexs els primers 1000 enters positius, i definint que hi ha una arestaentre dos vèrtexs si i només si els dos enters corresponents tenen com a mínim una xifra decimal en comú. En altres casos la relació entre vèrtexs no és simètrica: per exemple, un graf es pot construir escollint els vèrtexs per ser els primers 1000 enters positius, i definint que hi ha un vèrtexdes d'i fins a j sii és un divisor dej. Aquest tipus de graf s'anomena ungrafdirigit i les arestes s'anomenen arestesdirigides oarcs; per contrast, un graf on no es dirigeixen els arestes s'anomenano dirigit.
Els vèrtexs també s'anomenennodes opunts, i les arestes també s'anomenenlínies. Els grafs són el tema bàsic estudiat per lateoria de grafs.
Les definicions en la teoria de grafs varien. Les següents són qualcunes de les maneres més bàsiques de definir un graf i les estructures matemàtiques relacionades.
En el sentit més comú de la paraula,[1] ungraf és unparell ordenat que comprèn unconjunt devèrtexs onodes juntament amb un conjunt d'arestes olínies, les quals són conjunts de dos elements de. Per evitar ambigüitats, aquest tipus de graf es defineix de forma precisa com a grafno dirigit isimple.
Altres interpretacions degraf provenen de concepcions diferents del conjunt d'arestes. En una noció més generalitzada,[2] és un conjunt juntament amb una relació d'incidència que associa dos vèrtexs amb cada aresta. En una altra noció generalitzada, és unmulticonjunt de parells desordenats de (no necessàriament distints) vèrtexs. Molts autors anomenen aquest tipus d'objecte unmultigraf o pseudograf.
Totes aquestes variants i d'altres són descrites de manera detallada més avall.
Els vèrtexs que pertanyen a una aresta s'anomenenextrems,punts extrems, ovèrtexs extrems de l'aresta. Un vèrtex pot existir a un graf i no pertànyer a una aresta (vèrtex aïllat).
Normalment es considera queV iE són finits, i molts dels resultats coneguts no són veritables (o són diferents) per a grafs infinits, perquè molts dels arguments fallen en el cas infinit. L'ordre d'un graf és el nombre de vèrtexs i es denota. Lamida d'un graf és el nombre d'arestes i es denota. Elgrau d'un vèrtex és el nombre d'arestes que hi connecten, on una aresta que connecta el vèrtex als dos extrems (unbucle) es compta dues vegades.
Les arestes d'un graf no dirigit indueixen una relació binària simètrica ~ a que s'anomena la relació d'adjacència de G. Específicament, per a cada aresta {u,v} els vèrtexsu iv es diuen que sónadjacents l'un de l'altre, que es denotau ~v.
Per a una aresta {u,v}, els teòrics de grafs normalment utilitzen la notació una mica més curtauv.
Com s'ha dit a dalt, en contexts diferents pot ser útil definir el termegraf amb graus diferents de generalitat. Quan sigui necessari fer una distinció estricta, s'utilitzen els termes següents. En general, en texts moderns sobre teoria de grafs, llevat que no es digui el contrari, graf significa "graf finit simple no dirigit" (vegi les definicions sota).
unconjunt els elements del qual s'anomenen vèrtexs o nodes, i
un conjunt de parells ordenats de vèrtexs, anomenatsarcs,arestes dirigides, ofletxes.
Un arc es considera dirigitdea; s'anomena elcap i s'anomena lacua de l'arc; es diu que és unsuccessor directe d', i es diu que és unpredecessor directe d'. Si uncamí porta des de fins a, llavors s'anomena unsuccessor de iaccessible des d', i es diu que és unpredecessor d'. L'arc es diu l'arc invertit.
Un graf dirigitD s'anomenasimètric si, per a tots els arcs aD, l'arc invertit corresponent també pertany aD. Un graf dirigit simètric sense buclesD = (V,A) és equivalent a un graf no dirigit simpleG = (V,E), on els parells d'arcs inversos aA es corresponen un a un amb les arestes a E; així les arestes a G són |E| = |A|/2, o la meitat del nombre d'arcs a D.
Una variació sobre aquesta definició és el graf orientat, al qual només un d'entre i pot ser un arc.
Ungraf mixt G és un graf que pot contenir tant arestes dirigides com no dirigides. S'escriu com un triplet ordenatG := (V, E, A) ambV,E, iA definit com a dalt. Els grafs dirigits i no dirigits en són casos especials.
Unbucle és una aresta (dirigida o no dirigida) que comença i acaba en el mateix vèrtex; aquests es poden permetre o no segons l'aplicació. En aquest context, una aresta amb dos extrems diferents s'anomena un enllaç.
El terme "multigraf" denota normalment que es permetenarestes múltiples (i a vegades bucles). Quan els grafs es defineixen per tal depermetre bucles i arestes múltiples, un multigraf es defineix sovint com un grafsense bucles,[3] mentre que, allà on els grafs es defineixen per tal deno permetre bucles i arestes múltiples, el terme es defineix sovint per significar un "graf" que pot tenir tantarestes múltiples combucles,[4] encara que molts utilitzen el terme "pseudograf" per aquest significat.[5]
Un graf simple amb tres vèrtex i tres arestes. Cada vèrtex té grau 2, així que també és un graf regular.
En contraposició a un multigraf, un graf simple és un graf no dirigit que no té capbucle i no més d'una aresta entre dos vèrtexs diferents qualssevol. En un graf simple les arestes del graf formen un conjunt (en comptes d'un multiconjunt) i cada aresta és un parell de vèrtexsdistints. En un graf simple ambn vèrtexs tots els vèrtexs tenen un grau menor quen (el contrari, però, no és veritable - existeixen grafs no simples ambn vèrtexs en els quals tots els vèrtexs tenen grau menor an).
Un graf és un graf ponderat si un nombre (pes) s'assigna a cada aresta. Tals pesos podrien representar, per exemple, costos, llargades o capacitats, depenent del problema considerat.
El pes del gràfic és suma dels pesos donats a totes les arestes.
Ungraf regular és un graf on cada vèrtex té el mateix nombre de veïns, i. e., tots els vèrtexs tenen el mateix grau o valència. Un graf regular amb vèrtexs de grauk s'anomena un grafk-regular o graf regular de grauk.
Un graf finit és un grafG = (V,E) tal queV(G) iE(G) sónconjunts finits. Un graf infinit és aquest amb conjunts de vèrtexs o arestes, o tots dos,infinits.
Més comunament en la teoria de grafs s'implica que els grafs de què es parla són finits, i.e., els grafs finits s'anomenen simplement "grafs", mentre que quan els grafs són infinits se sol explicitar.
En ungraf no dirigitG, dos vèrtexsu iv s'anomenenconnexos siG conté un camí des d'u fins av. Altrament, s'anomeneninconnexos. Un graf s'anomenaconnex si tots els parells de vèrtexs distints del graf estan connectats idesconnex altrament.
Un graf s'anomenak-vèrtex-connex ok-aresta-connex si la supressió dek o més vèrtexs (respectivament, arestes) fa el graf desconnex. Un grafk-vertex-connex s'anomena sovint simplementk-connex.
Ungraf dirigit s'anomenafeblement connex si canviar totes les seves arestes dirigides per arestes no dirigides produeix un graf connex (no dirigit). Ésfortament connex ofort si conté un camí dirigit des d'u av i un camí dirigit des dev au per a tots els parells de vèrtexsu,v.
Dues arestes d'un graf s'anomenenadjacents (a vegadescoincidents) si comparteixen un vèrtex comú. Dues fletxes d'un graf dirigit s'anomenenconsecutives si el cap del primer és al final de la segona, d'aquesta manera, les arestes {x,a},{a,y} serien consecutives. De manera similar, dos vèrtexs s'anomenen adjacents si comparteixen una aresta comuna (consecutius si són al cap i final d'una fletxa); en aquest cas es diu que l'aresta comunauneix els dos vèrtexs. Una aresta i un vèrtex en aquella aresta s'anomenenincidents.
El graf amb només un vèrtex i cap aresta s'anomena elgraf trivial. Un graf amb només vèrtexs i cap aresta es coneix com a grafdegenerat. El graf amb cap vèrtex i cap aresta s'anomena a vegades elgraf nul ograf buit, però no tots els matemàtics permeten aquest objecte.
En un grafponderat o dígraf, cada aresta està associada amb qualque valor, diversament anomenatcost,pes,llargada o altres termes depenent de l'aplicació; tals grafs sorgeixen en molts contexts, per exemple en problemes d'encaminament òptims com elproblema del viatjant de comerç.
Normalment, els vèrtexs d'un graf, per la seva natura com a elements d'un conjunt, són distingibles. Aquesta classe de graf es pot anomenar com avèrtex-etiquetat. Tanmateix, per a moltes qüestions és millor tractar els vèrtexs com indistingibles; llavors el graf es pot anomenarno etiquetat (naturalment, els vèrtexs poden ser encara distingibles degut a les propietats del mateix graf, p. ex., pel nombre d'arestes incidents). Els mateixos comentaris s'apliquen a les arestes, de manera que els grafs que tenen arestes etiquetades s'anomenen grafs d'arestes etiquetades. Els grafs amb etiquetes a les arestes o als vèrtexs es designen més generalment cometiquetats. Consegüentment, els grafs en els quals els vèrtexs són indistingibles i les arestes són també indistingibles s'anomenenno etiquetats. (Fixi's que en la literatura el termeetiquetat es pot aplicar a unes altres classes de marcatge, a més a més de la que serveix només per distingir vèrtexs diferents o arestes.)
categoria petita es pot considerar un multigraf dirigit amb els objectes com vèrtexs i els morfismes com arestes dirigides. Els functors entre categories indueixen qualcuns, però no necessàriament tots, dels morfismes de dígraf.
En ungraf complet cada parell de vèrtexs és unit per una aresta, és a dir, el graf conté totes les arestes possibles.
En ungraf bipartit, els vèrtexs es poden dividir en dos conjunts,W iX, de manera que totes les arestes tinguin un vèrtex en cada un dels dos conjunts, o equivalentment on cap parell de vèrtexs deW és adjacent i cap parell de vèrtexs deX és adjacent. També es pot definir com un graf ambnúmero cromàtic 2.
En ungraf bipartit complet, el conjunt de vèrtex és la unió de dos subconjunts disjunts,W iX, de manera que tots els vèrtexs aW siguin adjacents a tots els vèrtexs aX però no hi hagi cap aresta dins deW oX.
En ungraf lineal ograf camí de llargadan, els vèrtexs es poden llistar en ordre,v0,v1,...,vn, de manera que les arestes siguinvi−1vi per cadai = 1, 2, ...,n. Si un graf lineal és unsubgraf d'un altre graf, llavors és també uncamí en aquest graf.
Ungraf cicle de llargadan és un camí tancat sense autointerseccions; equivalentment, és un grafconnex2-regular. Els seus vèrtexs es poden anomenarv1,...,vn de manera que les arestes siguinvi−1vi per cadai = 2,...,n ivnv1. Si un graf cicle és un subgraf d'un altre graf, llavors és també uncicle en aquest graf.
Ungraf planar es pot dibuixar en un pla sense arestes que es creuin (és a dir,incrustades en un pla).
Hi ha diverses operacions que produeixen grafs nous a partir de vells, que es podrien classificar en les categories següents:
Operacions elementals, a vegades anomenades "operacions d'edició" sobre grafs, que creen un graf nou des de l'original mitjançant un canvi simple i local, com addició o supressió d'un vèrtex o una aresta, fusió i partició de vèrtexs, etc.
Operacions de reescriptura de grafs que canvien l'aparició d'algun patró dins del graf amfitrió per una instància del corresponent graf de substitució.
Operacions unàries, que creen un graf significativament nou des del vell. Exemples:
En unhipergraf, una aresta pot unir més de dos vèrtexs.
Un graf no dirigit es pot veure com uncomplex simplicial que consta d'1-símplexs (les arestes) i 0-símplexs (els vèrtexs). Com a tal, els complexos són generalitzacions de grafs, ja que tenen en compte símplexs de dimensions més grans.
En lateoria de models, un graf és només una estructura. Però en aquest cas, no hi ha cap limitació sobre el nombre d'arestes: pot ser qualsevolnombre cardinal.
En labiologia computacional, l'anàlisi de grafs de potència introdueix grafs de potència com a representació alternativa de grafs no dirigits.
Berge, Claude.Théorie des graphes et ses applications (en francès). Dunod, Paris: Collection Universitaire de Mathématiques, II, 1958, p. viii+277. Translation: [1962]{{{títol}}} (en anglès). Dover, New York: Wiley, 2001.
