Graf (matemàtiques)
estructura matemàtica / From Wikipedia, the free encyclopedia
En teoria de grafs, un graf é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 anomenades vèrtexs, i els enllaços que connecten alguns parells de vèrtexs s'anomenen arestes. 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 la matemà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 aresta entre 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èrtex des d'i fins a j si i és un divisor de j. Aquest tipus de graf s'anomena un graf dirigit i les arestes s'anomenen arestes dirigides o arcs; per contrast, un graf on no es dirigeixen els arestes s'anomena no dirigit.
Els vèrtexs també s'anomenen nodes o punts, i les arestes també s'anomenen línies. Els grafs són el tema bàsic estudiat per la teoria de grafs.