Tall (graf)
En teoria de grafs, un tall és una partició dels vèrtexs d'un graf en dos subconjunts disjunts. El conjunt de tall és el conjunt d'arestes que enllacen vèrtexs que estan en diferents subconjunts de la partició. Es diu que les arestes travessen el tall quan estan dins el conjunt de tall.
En un graf no dirigit i no ponderat, la mida o pes del tall és el nombre d'arestes que aquest travessa. En un graf ponderat, és la suma dels pesos de les arestes que són tallades.
En una xarxa de flux, un tall s-t és un tall en què la font i el pou estan en diferents subconjunts, i el conjunt de tall sols està compost per arestes que van des del costat de la font fins al costat del pou. La capacitat d'un tall s-t és definida per la suma de les capacitats de les arestes del conjunt de tall.
El tall d'un graf també pot referir-se al mateix conjunt de tall.
Definició matemàtica[modifica]
Un tall C = (S,T) és una partició de V del graf G = (V, E).
Un tall s-t C = (S,T) d'una xarxa N = (V, E) és un tall de N en que s és la font i t és el pou de N, i que s∈S i t∈T.
El conjunt de tall d'un tall C = (S,T) és el conjunt {(u,v)∈E | u∈S, v∈T}.
La mida d'un tall C = (S,T) és el nombre d'arestes dins el conjunt de tall. Si les arestes són ponderades, el valor del tall és la suma dels pesos.
Tall mínim[modifica]
Un tall és mínim si la mida del tall no és més gran en cap altre tall. La imatge de l'esquerra mostra un tall mínim: la mida d'aquest és 2, i no hi ha cap tall de mida 1 perquè el graf no té ponts.
El teorema de flux màxim tall mínim prova que el flux màxim que pot travessar una xarxa de flux i la mida de qualsevol tall s-t mínim són iguals. Existeixen mètodes prou eficients (ordre polinòmic) per solucionar el problema del tall mínim, per exemple l'algorisme d'Edmonds-Karp.
Tall màxim[modifica]
Un tall és màxim si la mida del tall no és més petita en cap altre tall. La imatge de la dreta mostra un tall màxim: la mida del tall és |E| − 1 = 5, i no hi ha un tall de mida |E| perquè el graf no és bipartit.
En general, buscar un tall màxim és difícil computacionalment.
Tall dispers[modifica]
El problema del tall dispers és partir en dos subconjunts els vèrtexs per tal de minimitzar la proporció entre el nombre d'arestes dins el conjunt de tall i el nombre de vèrtexs de la partició més petita (la partició amb menys vèrtexs). (poques arestes travessen el tall) i balancejat (prop de la bisecció). El millor algorisme conegut té un cost temporal , reconegut a Arora, Rao & Vazirani (2009).
Vegeu també[modifica]
Referències[modifica]
 |
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Tall |
- Arora, Sanjeev; Rao, Satish; Vazirani, Umesh «Expander flows, geometric embeddings and graph partitioning». J. ACM. ACM, 56, 2, 2009, pàg. 1–37. ISSN: 0004-5411.