Klip (grafteori)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 11. august 2021; checks kræver 2 redigeringer .

Et grafsnit i strømningsproblemer er et par toppunktssæt (S,T) sådan

$S\kop T=V$ , hvor er sættet af grafens toppunkter $V$
$S\cap T=\emptyset$
$s \i S, t \i T$ , hvor er kilden, er afløbet. $s$ $t$

Størrelsen af snittet er summen af kapaciteterne af sådanne kanter , der . $(i, j)$ $i\in S,j\in T$

Andre definitioner af et snit (udsnit) af en graf

Et grafsnit er et sæt kanter, der danner en todelt undergraf, hvis fjernelse deler grafen i to eller flere komponenter, som især kan være isolerede noder. Samt en linje, der går gennem alle kanterne af grafens snit.

Karakteristika

Snitlinjer kan krydse et vilkårligt antal kanter og akkorder.
For at få grafens hovedafsnit er det nødvendigt at tegne grafens snitlinje på en sådan måde, at den kun skærer én gren af grafen ved et vilkårligt skæringspunkt af akkorder.

Klip (grafteori)

Andre definitioner af et snit (udsnit) af en graf

Karakteristika

Se også