Pienin leikkaus
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 18. heinäkuuta 2022 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .Graafin pienin leikkaus on leikkaus , joka on jossain mielessä minimaalinen ( graafin kärkien osio kahdeksi ei-leikkaavaksi yhdistettyyn joukkoon).
Muunnelmia
Pienimmät leikkausvariaatiot:
- Leikkaus , jossa on minimimäärä reunoja kaikkien graafin tietyn osion kahdeksi yhdistetyksi komponentiksi leikattujen leikkausten joukossa. Tällaiset leikkaukset luovat graafisen leikkauksen vektoriavaruuden .
- Leikkaus, jolla on minimaalinen määrä reunoja ohjaamattoman graafin kaikista leikkauksista . Tällainen leikkaus määrittää graafin reunaliitettävyyden . Kargerin algoritmi tarjoaa tehokkaan satunnaistetun menetelmän tällaisen leikkauksen löytämiseen.
- Suuntaamattomien painotettujen graafien vähiten leikattu ongelma voidaan ratkaista Stöhr-Wagner-algoritmilla .
- Yleistys painottamattomasta ja suuntaamattomasta pienimmästä leikkauksesta, pienimmästä k - leikkauksesta , jonka tavoitteena on osioida graafi vähintään k :ksi yhdistetyksi komponentiksi poistamalla mahdollisimman vähän reunoja.
- Kuvaajan osiointi , kombinatoristen optimointiongelmien perhe, jossa kaavio jaetaan kahteen tai useampaan osaan lisäehdona leikkauksen mittojen tasapainottaminen.
- Virtausleikkaus , joka erottaa lähteen nielusta ja minimoi lähteen sisältävästä osasta altaan sisältävään osaan suuntautuvien valokaarien kokonaispainon. Kuten Ford-Fulkersonin lause osoittaa , tällaisen leikkauksen paino on yhtä suuri kuin suurin virtaus, joka voidaan siirtää lähteestä nieluun tietyn verkon läpi. Vaihtoehtoisesti tämä ongelman muunnelma voidaan ratkaista käyttämällä Karger-algoritmia .
- Painotetun suuntaamattoman verkon leikkaus, joka erottaa valitun kärkiparin ja jolla on vähimmäispaino. Leikkausjärjestelmä, joka ratkaisee minkä tahansa pisteparin ongelman, voidaan koota rakenteeksi, joka tunnetaan graafin Gomory-Hu-puuna
Pienimpien leikkausten määrä
Graafilla, jossa on n kärkeä, voi olla korkeintaan erilliset pienimmät leikkaukset.
Katso myös
- Leikkaa (graafiteoria) .
- Kuvaajan enimmäisleikkaus, joka sisältää suurimman mahdollisen määrän reunoja
- Vertex separator , samanlainen käsite, mutta kärjet poistetaan, ei reunoja
Muistiinpanot
- ↑ 4 min-leikkausalgoritmia . Haettu 19. kesäkuuta 2017. Arkistoitu alkuperäisestä 5. elokuuta 2016.