Malhotra-Kumara-Maheshwari-algoritme

Malhotra-Kumar-Maheshwari-algoritmen giver dig mulighed for at finde det maksimale flow i en graf.

Beskrivelse

Vi betragter et transportnetværk bestående af en rettet graf , hvor er et sæt af hjørner, er et sæt kanter og et flow . For hvert toppunkt indføres et strømningspotentiale svarende til det maksimale ekstra flow, der kan passere gennem dette toppunkt. Dernæst kommer cyklussen. Ved hver iteration bestemmes et toppunkt med et minimumspotentiale . Derefter startes en strøm af størrelse fra kilden til vasken, der passerer gennem dette toppunkt. I dette tilfælde, hvis kantens resterende kapacitet er lig med nul, fjernes denne kant. Alle hjørner, der ikke har nogen indgående og/eller udgående kanter, fjernes også. Når et toppunkt fjernes, fjernes alle tilstødende kanter. Der vil således blive fundet et blokerende (pseudo-maksimalt) flow. For at finde det maksimale flow i en graf, skal du søge efter et blokerende flow og derefter ændre grafen i overensstemmelse hermed, og så videre, indtil blokeringsflowet er lig nul. $G=(V,\;E)$ $V$ $E$ $f$ $v\in V$ $r$ $\rho$ $\rho$

Sværhedsgrad

Hvis information om indgående og udgående buer lagres i form af sammenkædede lister , vil der for at springe flowet ved hver iteration blive udført handlinger, hvor det svarer til antallet af kanter, for hvilke den resterende gennemstrømning er faldet, men forblevet positiv og til antallet af fjernede kanter. Der vil således blive truffet handlinger for at finde den blokerende tråd. Søgningen efter en blokerende tråd vil blive udført én gang, da antallet af kanter på stien fra kilde til synke i en blokerende tråd ikke vil falde. Så viser det hele sig at være handlinger. $O(\left|V\right|+\left|E_{i}\right|)$ $\venstre|V\højre|$ $\left|E_{i}\right|$ $\sum _{i}{O(\left|V\right|+\left|E_{i}\right|)}=O(\left|V\right|^{2})$ $O(\venstre|V\højre|)$ $O(\left|V\right|^{3})$

Litteratur

Malhotra VM, Kumar M. Pramodh, Maheshwari SN En O(IVI 3 ) algoritme til at finde maksimale strømme i netværk . - 1978.

Malhotra-Kumara-Maheshwari-algoritme

Beskrivelse

Sværhedsgrad

Litteratur

Noter