GrafgrafGraf jest strukturą składającą się z obiektów (wierzchołkówwierzchołekwierzchołków) oraz z powiązań między nimi (krawędzikrawędźkrawędzi). Zazwyczaj przedstawiany jest w formie diagramu jako zbiór punktów połączonych odcinkami, gdzie punkty przedstawiają wierzchołki, a odcinki – krawędzie grafu.
RSxiPQWNTHTjy
Ilustracja interaktywna przedstawia graf o połączeniach: 7, 3. 3, 2. 3, 1. 1, 4. 1, 5. 1, 6. 1, 0. 1. Wierzchołek oznaczony jako "3", 2. Krawędź łącząca wierzchołki "3" i "1", 3. Sąsiad wierzchołka "1".
Ilustracja interaktywna przedstawia graf o połączeniach: 7, 3. 3, 2. 3, 1. 1, 4. 1, 5. 1, 6. 1, 0. 1. Wierzchołek oznaczony jako "3", 2. Krawędź łącząca wierzchołki "3" i "1", 3. Sąsiad wierzchołka "1".
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
Wierzchołki i krawędzie
Podczas implementacji potrzebna jest możliwość rozróżnienia wierzchołków. Osiągnąć to można, na przykład oznaczając poszczególne wierzchołki kolejnymi liczbami naturalnymi, zaczynając od 0. Przechowywać je będziemy za pomocą listy.
Warto zaznaczyć, że wierzchołki mogą być reprezentowane również za pomocą liter (taki przypadek zaprezentowano w Ćwiczeniu 1 na dole tej sekcji).
Linia 1. wierzcholki znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy.
wierzcholki = []
Podobnie w przypadku krawędzi:
Linia 1. krawedzie znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy.
krawedzie = []
Listy są parametrami klasy Graf. Klasa ta ma z kolei dwa pola – listę wierzchołków grafu oraz listę jego krawędzi. Domyślnymi parametrami konstruktora tej klasy będą puste listy:
Linia 1. class Graf dwukropek.
Linia 2. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek wierzcholki znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek krawedzie znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły dwukropek.
Linia 3. self kropka wierzcholki znak równości wierzcholki.
Linia 4. self kropka krawedzie znak równości krawedzie.
Ilustracja przedstawia sześciokąt. Nad sześciokątem jest duża litera G. W każdym wierzchołku jest inna litera w okręgu: s, r, q, p, u, t. Pomiędzy okręgami biegną przeciwległe proste przecinające się w środku sześciokąta.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
RP7mshv0CoMuW
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Propozycja rozwiązania:
Linia 1. graf znak równości GrafG otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias okrągły otwórz nawias kwadratowy apostrof t apostrof przecinek apostrof s apostrof przecinek apostrof r apostrof przecinek apostrof q apostrof przecinek apostrof p apostrof przecinek apostrof u apostrof zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy otwórz nawias kwadratowy apostrof t apostrof przecinek apostrof s apostrof zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy apostrof t apostrof przecinek apostrof q apostrof zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy apostrof t apostrof przecinek apostrof u apostrof zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy apostrof s apostrof przecinek apostrof p apostrof zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy apostrof s apostrof przecinek apostrof r apostrof zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy apostrof r apostrof przecinek apostrof u apostrof zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy apostrof r apostrof przecinek apostrof q apostrof zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy apostrof q apostrof przecinek apostrof p apostrof zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy apostrof p apostrof przecinek apostrof u apostrof zamknij nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły.
ciąg wierzchołków, w którym wszystkie wyrazy (z wyjątkiem pierwszego i ostatniego, które mogą być równe) są różne
graf
graf
struktura składająca się z niepustego zbioru wierzchołków oraz ze zbioru krawędzi; dla grafu zbiór wierzchołków oznaczamy (ang. verticies – wierzchołki), a zbiór krawędzi – (ang. edges – krawędzie); liczbę elementów zbioru oznaczamy literą , zaś liczbę elementów zbioru –
graf spójny
graf spójny
graf, w którym każda para wierzchołków połączona jest drogą
izomorfizm
izomorfizm
właściwość grafów polegająca na tym, że liczba krawędzi łączących dane dwa wierzchołki jednego grafu jest równa liczbie krawędzi łączących odpowiadające im wierzchołki drugiego grafu; jeśli graf jest izomorficzny z grafem , to gdy jakieś dwa wierzchołki są połączone krawędzią w jednym z grafów, odpowiadające im wierzchołki w drugim grafie również łączy krawędź; izomorfizm grafów zachowuje takie własności jak: liczba wierzchołków, liczba krawędzi, stopnie wierzchołków, czy spójność grafu
klasa generyczna
klasa generyczna
klasa w języku Java pozwalająca stworzyć ogólną, uniwersalną klasę, która będzie wykonywała działania z różnymi typami danych, umożliwiając ponowne użycie kodu bez konieczności redefiniowania klasy dla każdego typu
krawędź
krawędź
nieuporządkowana para (niekoniecznie różnych) elementów zbioru wierzchołków, tj. takich, które są ze sobą połączone; w reprezentacji graficznej jest to linia łącząca te wierzchołki; krawędź może łączyć ze sobą jeden wierzchołek (wtedy nazywana jest pętlą)
para nieuporządkowana
para nieuporządkowana
zbiór złożony jedynie z dwóch różnych elementów:
stopień wierzchołka
stopień wierzchołka
liczba krawędzi incydentnych z danym wierzchołkiem
wierzchołek
wierzchołek
inaczej: punkt, węzeł; element niepustego zbioru, który wraz ze zbiorem krawędzi tworzy graf