Vágás (gráfelmélet)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. augusztus 11-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Az áramlási problémákban kivágott gráf csúcshalmazok (S,T) párja úgy, hogy

$S\cup T=V$ , ahol a gráf csúcsainak halmaza $V$
$S\cap T=\emptyset$
$s \in S, t \in T$ , hol a forrás, az a lefolyó. $s$ $t$

A vágás mérete az olyan élek kapacitásának összege, amelyek . $(i, j)$ $i\in S,j\in T$

A gráf kivágásának (szakaszának) egyéb meghatározásai

A gráfvágás olyan élek halmaza, amelyek egy kétrészes részgráfot alkotnak, amelyek eltávolításával a gráf két vagy több komponensre osztható, amelyek különösen izolált csomópontok lehetnek. Valamint egy vonal, amely a grafikon metszetének minden élén áthalad.

Jellemzők

A metszetvonalak tetszőleges számú élt és húrt keresztezhetnek.
A gráf fő szakaszának megszerzéséhez úgy kell megrajzolni a gráf metszetvonalát, hogy az csak a gráf egyik ágát metszi egy tetszőleges húrmetszéspontban.

Vágás (gráfelmélet)

A gráf kivágásának (szakaszának) egyéb meghatározásai

Jellemzők

Lásd még