W trakcie wykładu przedstawię, w prosty sposób, algorytm Edmondsa-Karpa wyznaczający maksymalny przepływ w sieci. Następnie uczniowie zastosują ten algorytm do rozwiązania postawionego problemu.
Celem spotkania, poza dobra zabawą, jest uświadomienie uczniom szkół średnich, że Informatyka to nie tylko gry, Internet i komputery. Informatyka to dziedzina nauki, której celem jest wspomaganie działań we wszystkich aspektach życia.
Sieć przepływowa to skierowany graf prosty, ważony (z wartościami przepustowości na krawędziach), posiadający dwa wyróżnione wierzchołki: źródło (tj. wierzchołek, do którego nie prowadzi żadna krawędź) i ujście (tj. wierzchołek, z którego żadna krawędź nie wychodzi). Wyznaczanie przepływu w sieci polega na przyporządkowaniu każdej krawędzi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez tą krawędź. Ograniczenia przepustowości sieci stanowią istotne zagadnienie w transporcie publicznym, w telekomunikacji, w procesach produkcyjnych, w sieciach ciepłowniczych, itd. …