wprowadzenie

Graf to zbiór krawędzi i wierzchołków.

Może to brzmi abstrakcyjnie, może pomyślisz: „Po co nam te grafy?”. Ale grafy są także odzwierciedleniem życia codziennego. Potem przy bardziej skomplikowanych problemach mają z życiem codziennym coraz mniej wspólnego, ale na początek zobaczmy taki przykład:

Weźmy sobie jakąś mapkę. Skrzyżowania oznaczymy jako wierzchołki, a następnie połączymy je wzdłuż dróg, które łączą te skrzyżowania. I tak oto powstał nam całkiem ładny graf i chyba już pojawia się w nas intuicja, że te grafy mogą jednak być użyteczne.

Aby odzwierciedlenie rzeczywistości było jeszcze lepsze, możemy krawędziom dodać wagi – czyli powiedzmy ilość kilometrów, która dzieli dane dwa skrzyżowania lub liczba minut jaką potrzebujemy, żeby przejechać tą drogą. W mieście zdarzają się też ulice jednokierunkowe – ale i na to mamy sposób, ponieważ istnieją grafy skierowane, czyli zamiast krawędzi w postaci linii prostych, rysujemy strzałki.

Często będziemy używać pojęcia ścieżki – jest to pewien ciąg wierzchołków sąsiadujących ze sobą lub możemy to rozumieć jako ciąg krawędzi łączących kolejne wierzchołki w ciągu wierzchołków ścieżki. Często mówiąc ścieżka mamy na myśli ścieżkę prostą, czyli taką, w której nie ma powtarzających się wierzchołków.

Z jednego skrzyżowania do drugiego czasem możemy dostać się na więcej niż jeden sposób, np. zamiast jechać najbliższą drogą, pojedziemy naokoło (może właśnie tak będzie szybciej, więc dlaczego nie?) – to oznacza, że w grafie istnieje cykl.

Cykl prosty to taka droga, w której koniec wraca do początku (pierwszy wierzchołek na ścieżce jest równocześnie wierzchołkiem ostatnim).

Teraz znamy już podstawowe pojęcia związane z grafami. Możemy przejść dalej, do rodzajów grafów.


STRONA GŁÓWNA WPROWADZENIE DO GRAFÓW RODZAJE GRAFÓW PRZESZUKIWANIA W GRAFACH GRAFY HAMILTONOWSKIE GRAFY EULEROWSKIE NAJKRÓTSZE ŚCIEŻKI SORTOWANIE TOPOLOGICZNE
	Wprowadzenie Przykładowy graf z zaznaczonym cyklem.	Graf to zbiór krawędzi i wierzchołków. Może to brzmi abstrakcyjnie, może pomyślisz: „Po co nam te grafy?”. Ale grafy są także odzwierciedleniem życia codziennego. Potem przy bardziej skomplikowanych problemach mają z życiem codziennym coraz mniej wspólnego, ale na początek zobaczmy taki przykład: Weźmy sobie jakąś mapkę. Skrzyżowania oznaczymy jako wierzchołki, a następnie połączymy je wzdłuż dróg, które łączą te skrzyżowania. I tak oto powstał nam całkiem ładny graf i chyba już pojawia się w nas intuicja, że te grafy mogą jednak być użyteczne. Aby odzwierciedlenie rzeczywistości było jeszcze lepsze, możemy krawędziom dodać wagi – czyli powiedzmy ilość kilometrów, która dzieli dane dwa skrzyżowania lub liczba minut jaką potrzebujemy, żeby przejechać tą drogą. W mieście zdarzają się też ulice jednokierunkowe – ale i na to mamy sposób, ponieważ istnieją grafy skierowane, czyli zamiast krawędzi w postaci linii prostych, rysujemy strzałki. Często będziemy używać pojęcia ścieżki – jest to pewien ciąg wierzchołków sąsiadujących ze sobą lub możemy to rozumieć jako ciąg krawędzi łączących kolejne wierzchołki w ciągu wierzchołków ścieżki. Często mówiąc ścieżka mamy na myśli ścieżkę prostą, czyli taką, w której nie ma powtarzających się wierzchołków. Z jednego skrzyżowania do drugiego czasem możemy dostać się na więcej niż jeden sposób, np. zamiast jechać najbliższą drogą, pojedziemy naokoło (może właśnie tak będzie szybciej, więc dlaczego nie?) – to oznacza, że w grafie istnieje cykl. Cykl prosty to taka droga, w której koniec wraca do początku (pierwszy wierzchołek na ścieżce jest równocześnie wierzchołkiem ostatnim). Teraz znamy już podstawowe pojęcia związane z grafami. Możemy przejść dalej, do rodzajów grafów.
	Created by Monika Ciosek

Wprowadzenie