Wprowadzenie do teorii grafów
Przypomnij sobie definicję grafów z lekcji matematyki. Przykładowy graf znajdziesz w e‑materiale Sposoby określania funkcjiSposoby określania funkcji.
Czy wiesz, co takiego łączy listonosza planującego drogę z przesyłkami po osiedlu oraz swatkę, która na podstawie dwóch grup kojarzy małżeństwa? Odpowiedź brzmi: teoria grafów.
Teoria grafów definiuje graf jako strukturę matematyczną, która bada i przedstawia relacje między obiektami. W przypadku drogi listonosza jest to zatem relacja między kolejnymi domami, które musi odwiedzić, a swatki – swatanymi ludźmi.
Czy wiesz jednak, co kryje się pod hasłem „teoria grafów”? Wyjaśnienie znajdziesz w tym e‑materiale.
Zagadnienie to w kontekście wybranych języków programowania zostało omówione w e‑materiałach:
Wprowadzenie do teorii grafów w języku C++Wprowadzenie do teorii grafów w języku C++,
Wprowadzenie do teorii grafów w języku JavaWprowadzenie do teorii grafów w języku Java,
Wprowadzenie do teorii grafów w języku PythonWprowadzenie do teorii grafów w języku Python.
Wyjaśnisz, w jaki sposób można reprezentować dane i powiązania między nimi za pomocą grafów.
Zbadasz najważniejsze pojęcia teorii grafów: sąsiedztwo, stopień, droga, graf, sieć, wierzchołek, krawędź, cykl.
Rozwiążesz ćwiczenia utrwalające wiedzę z zakresu podstawowych pojęć teorii grafów.