Cea mai mică tăietură
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 18 iulie 2022; verificarea necesită 1 editare .Cea mai mică tăietură a unui grafic este o tăietură care este minimă într-un anumit sens ( o partiție a vârfurilor unui grafic în două mulțimi conectate care nu se intersectează).
Variante
Cele mai mici variante de tăiere:
- O tăietură cu numărul minim de muchii dintre toate tăieturile unei partiții date a graficului în două componente conectate. Astfel de tăieturi generează un spațiu vectorial de tăieturi grafice .
- O tăietură cu numărul minim de muchii dintre toate tăieturile dintr- un grafic nedirecționat . O astfel de tăiere determină conectivitatea marginii graficului. Algoritmul lui Karger oferă o metodă randomizată eficientă pentru găsirea unei astfel de tăieturi.
- Cea mai mică problemă în graficele ponderate nedirecționate poate fi rezolvată prin algoritmul Stöhr-Wagner .
- O generalizare a celei mai mici tăieturi neponderate și nedirecționate, cea mai mică k -cut , al cărei scop este de a împărți graficul în cel puțin k componente conectate prin eliminarea cât mai puține muchii posibil.
- Graph partitioning , o familie de probleme de optimizare combinatorie în care graficul este împărțit în două sau mai multe părți, cu condiția suplimentară de a echilibra dimensiunile tăieturii.
- Tăierea fluxului , care separă sursa de chiuvetă și minimizează greutatea totală a arcurilor direcționate de la partea care conține sursa către partea care conține chiuveta. După cum arată teorema Ford-Fulkerson , greutatea unei astfel de tăieturi este egală cu debitul maxim care poate fi trecut de la sursă la chiuvetă printr-o rețea dată. Alternativ, această variație a problemei poate fi rezolvată folosind algoritmul Karger .
- O tăietură a unei rețele ponderate nedirecționate care separă o pereche selectată de vârfuri și are ponderea minimă. Un sistem de tăiere care rezolvă problema pentru orice pereche de vârfuri poate fi asamblat într-o structură cunoscută sub numele de arborele Gomory-Hu unui grafic.
Numărul celor mai mici tăieturi
Un grafic cu n vârfuri poate avea cel mult cele mai mici tăieturi distincte.
Vezi și
- Cut (teoria graficelor) .
- Tăierea maximă a unui grafic care conține numărul maxim posibil de muchii
- Separator de vârfuri, un concept similar, dar vârfurile sunt eliminate, nu marginile
Note
- ↑ 4 Algoritmi Min-Cut . Consultat la 19 iunie 2017. Arhivat din original la 5 august 2016.