Tăierea (teoria graficelor)

În teoria graficelor , o tăietură este o partiție a vârfurilor unui grafic în două subseturi disjuncte .

Fiecare tăietură determină un set de tăieturi (sau tăieturi ), definit ca setul de arce care își au capetele în cele două subseturi ale partiției. Într-un grafic conectat , fiecare set de tăieturi este legat de o singură tăietură.

Într - o rețea de flux , o tăietură st este o tăietură astfel încât vârful sursei (e) și de scurgere (t) nu fac parte din același subset al peretelui despărțitor. Capacitatea unui punct tăiat este definită ca suma capacităților arcurilor aparținând setului de tăiere .

Definiție

O taietura $C=(S,T)$ ${\ displaystyle C = (S, T)}$ ${\ displaystyle C = (S, T)}$ este partiția vârfurilor $V.$ ${\ displaystyle V}$ $V.$ a unui grafic $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ în două subseturi disjuncte S și T.

Setul tăiat al unei tăieturi $C=(S,T)$ ${\ displaystyle C = (S, T)}$ ${\ displaystyle C = (S, T)}$ este setul $\{(u,v)\in E|u\in S,v\in T\}$ ${\ displaystyle \ {(u, v) \ in E | u \ in S, v \ in T \}}$ ${\ displaystyle \ {(u, v) \ in E | u \ in S, v \ in T \}}$ muchii care au o extremă în S și cealaltă în T. Având în vedere un grafic G conectat, condiția necesară și suficientă pentru care un set de margini să fie un set de tăieturi este ca eliminarea lor să facă G neconectat.

Într - o rețea de flux G, numit s și t , respectiv , sursa și drena G, o tăietură st este o tăietură specifică în care $s\in S$ ${\ displaystyle s \ în S}$ $s \ în S$ Și $t\in T$ ${\ displaystyle t \ in T}$ $t \ in T$ .

Într-un grafic neorientat și care nu este cântărit , dimensiunea (sau greutatea) unei tăieturi este numărul de arce care trec prin el. Într-un grafic ponderat, valoarea (sau greutatea) unei tăieturi este suma greutăților arcurilor care traversează tăierea însăși.

Proprietate

Intersecția unui set de tăieturi și a unui ciclu conține întotdeauna un număr par de arce. ^[1]

Tăiere minimă

O croială minimă

O tăietură este minimă dacă greutatea sa este cel mult egală cu cea a tuturor celorlalte tăieturi posibile. Imaginea din dreapta arată un exemplu de tăiere minimă: dimensiunea tăieturii este 2 și nu există tăieturi de dimensiunea 1, deoarece graficul nu are punți .

Debitul maxim și teorema de forfecare minimă demonstrează că debitul maxim al unei rețele este egal cu greutatea unui punct de forfecare. Există metode care rezolvă problema de forfecare minimă în timp polinomial , în special algoritmul Edmonds-Karp . ^[2]

Tăiere maximă

Același subiect în detaliu: tăiere maximă .

O tăiere maximă

O tăietură este maximă dacă greutatea sa este cel puțin egală cu cea a tuturor celorlalte tăieturi posibile. Imaginea din dreapta arată un exemplu de tăiere maximă: dimensiunea tăieturii este de 5 și nu există tăieturi de dimensiuni $6=|E|$ ${\ displaystyle 6 = | E |}$ ${\ displaystyle 6 = | E |}$ (numărul de muchii), deoarece graficul nu este bipartit .

În general, găsirea unei tăieturi maxime este dificil de calcul. ^[3] Problema de forfecare maximă este una dintre problemele Karp cu 21 NP-complete , ^[4] și este APX-dificilă , adică nu există scheme de aproximare în timp polinomial , cu excepția cazului în care P = NP. ^[5]

Cea mai slabă tăietură

Cea mai mică problemă de tăiere constă în împărțirea vârfurilor în așa fel încât să se reducă la minimum raportul dintre numărul de arce traversate de tăietură și cel al vârfurilor din cea mai mică jumătate a partiției.

Notă

^ (EN) Kevin Wayne, Greedy Algorithms II (PDF) pe cs.princeton.edu, Universitatea Princeton , Departamentul de Informatică, 18 februarie 2013. Accesat pe 13 septembrie 2016 (depus de „Original url 13 septembrie 2016) .
^ (EN) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein , Introduction to Algorithms , 2nd, MIT Press și McGraw-Hill, 2001, p. 563 , 655,1043, ISBN 0-262-03293-7 .
^ (EN) Michael R. Garey și David S. Johnson ,Computers and intractability: A Guide to Theory of NP-Completeness , WH Freeman, 1979 A2.2: ND16, pg.210, ISBN 0-7167-1045- 5 .
^ ( EN ) RM Karp , Reducibilitatea printre problemele combinatorii , în RE Miller și JW Thacher (eds), Complexity of Computer Computation , New York, Plenum Press, 1972, pp. 85-103.
^ (EN) S. Khot , G. Kindler, Mossel E. și R. O'Donnell, Rezultate de inapproximabilitate optimă pentru MAX-CUT și alte CSP-uri cu două variabile? ( PDF ), în Proceedings of the 45th IEEE Symposium on Foundations of Computer Science , 2004, pp. 146–154.

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre tăiere

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] (EN) Kevin Wayne, Greedy Algorithms II (PDF) pe cs.princeton.edu, Universitatea Princeton , Departamentul de Informatică, 18 februarie 2013. Accesat pe 13 septembrie 2016 (depus de „Original url 13 septembrie 2016) .

[2] (EN) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein , Introduction to Algorithms , 2nd, MIT Press și McGraw-Hill, 2001, p. 563 , 655,1043, ISBN 0-262-03293-7 .

[3] (EN) Michael R. Garey și David S. Johnson ,Computers and intractability: A Guide to Theory of NP-Completeness , WH Freeman, 1979 A2.2: ND16, pg.210, ISBN 0-7167-1045- 5 .

[4] ( EN ) RM Karp , Reducibilitatea printre problemele combinatorii , în RE Miller și JW Thacher (eds), Complexity of Computer Computation , New York, Plenum Press, 1972, pp. 85-103.

[5] (EN) S. Khot , G. Kindler, Mossel E. și R. O'Donnell, Rezultate de inapproximabilitate optimă pentru MAX-CUT și alte CSP-uri cu două variabile? ( PDF ), în Proceedings of the 45th IEEE Symposium on Foundations of Computer Science , 2004, pp. 146–154.

[1]

[2]

[3]

[4]

[5]