Another example where bipartite graphs appear naturally is in the (NP-complete) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations.
Un alt exemplu unde grafurile bipartite apar în mod natural este problema optimizării căilor ferate (NP-completă), în care intrarea este un orar al trenurilor și stațiilor, iar scopul este să se găsească o mulțime de stații de tren cât mai mică cu putință, astfel încât fiecare tren să viziteze cel puțin una dintre stațiile alese.