Leikkaa (graafiteoria)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. elokuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Virtausongelmissa leikattu graafi on sellainen kärkijoukkojen (S,T) pari, että

$S\cup T=V$ , missä on graafin kärkipisteiden joukko $V$
$S\cap T=\tyhjäsarja$
$s \in S, t \in T$ , missä on lähde, on viemäri. $s$ $t$

Leikkauksen koko on sellaisten reunojen kapasiteettien summa, jotka . $(i, j)$ $i\in S,j\in T$

Muita kaavion leikkauksen (osion) määritelmiä

Graafin leikkaus on joukko reunoja, jotka muodostavat kaksiosaisen aligraafin, jonka poistaminen jakaa graafin kahdeksi tai useammaksi komponentiksi, jotka voivat olla erityisesti eristettyjä solmuja. Sekä viiva, joka kulkee kaavion leikkauksen kaikkien reunojen läpi.

Ominaisuudet

Leikkausviivat voivat ylittää mielivaltaisen määrän reunoja ja jänteitä.
Kuvaajan pääosan saamiseksi on piirrettävä graafin leikkausviiva siten, että se leikkaa vain yhden graafin haaran mielivaltaisessa sointujen leikkauspisteessä.

Leikkaa (graafiteoria)

Muita kaavion leikkauksen (osion) määritelmiä

Ominaisuudet

Katso myös