Mit jelent a potenciál gráfelméletben, operaciókutatás tantárgyból?

Tényleg csak egy függvény. Minden csúcshoz hozzárendelsz egy valós számot.

Amikor használod, akkor néha úgy képzelheted, hogy magasságot rendeltél az adott csúcshoz, innen a neve.

Néha jól jön. Például van egy konzervatív c költségfüggvényed, és az s és t csúcsok közötti legolcsóbb utakra vagy kíváncsi. Ekkor s-ből minden csúcsra meghatározhatod az oda menő legolcsóbb út hosszát, ez egy megengedett potenciál. Ha a pi(v)-pi(u) potenciálkülönbségeket levonod c-ből (kapod c' költségfüggvényt), akkor látod, hogy c' szerint minden él költsége 0 vagy nagyobb (és s-ből mindenki elérhető 0 költségű úton).

Ekkor az eredeti problémádat úgy tudod elképzelni, hogy van az s valahol egy hegységben, az összes többi csúcs valamilyen magasságban (s felett vagy alatt), és az eredeti c költségfüggvény az éleken abból áll össze, hogy a magasságkülönbség pi(v)-pi(u) költsége + valami c' veszteség (súrlódás), ahol c' >= 0.

Ha levonod a potenciálkülönbséget c-ből, akkor a magasságkülönbségek kiesnek, és csak a c' súrlódás költsége marad meg, így az s és t közötti legolcsóbb utak éppen az olyan utak, amik az olyan éleket használják, ahol a súrlódás 0. Tehát a c'(uv)=0 éleket tartalmazó részgráfban minden st út legolcsóbb, és minden legolcsóbb st út csak ilyen éleket használhat. (+ gyorsan meghatározható ez a részgráf.)

De nem biztos, hogy minden alkalmazásnál hasznos ez az analógia.

Hm.. Ez az 1.3.14-es tétel (Legolcsóbb utak részgráfjának tétele) a Frank András: Operációkutatás (2013)-ban.

Amúgy a könyv addig szinte kivétel nélkül megengedett potenciálokról ír (a potenciált talán nem is definiálja sehol, bár használja).