Przeczytaj

Struktura grafu

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

Ź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).

wierzcholki = []

Podobnie w przypadku krawędzi:

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:

class Graf:
    def __init__(self, wierzcholki=[], krawedzie=[]):
        self.wierzcholki = wierzcholki
        self.krawedzie = krawedzie

Wierzchołki grafu reprezentowane będą liczbami naturalnymi.

Utworzony w ten sposób obiekt graf klasy Graf ma trzy różne wierzchołki oznaczone numerami 0, 1 oraz 2, jednak nie ma żadnych krawędzi:

graf = Graf([0, 1, 2])

By wyświetlić wierzchołki obiektu graf klasy Graf, wykorzystamy polecenie print:

print(graf.wierzcholki)

Każda krawędź reprezentowana jest przez dwuelementową listę zawierającą numery wierzchołków, które łączy.

Dodajmy do utworzonego obiektu krawędzie łączące wierzchołki:

graf = Graf([0, 1, 2], [[0, 1], [0, 2]])

Graf opisany za pomocą poniższej klasy:

graf = Graf([7, 5, 4, 5, 1, 2], [[7, 5], [4, 6], [1, 2]])

wyglądałby następująco:

R1aqQvQ1QyMEI

Ilustracja przedstawia trzy grafy o połączeniach: pierwszy 7, 5, drugi 4, 6, trzeci 1, 2. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Polecenie 1

Jak nazywamy graf, którego nie wszystkie wierzchołki połączone są ze sobą krawędziami?

Przykład

W jaki sposób moglibyśmy za pomocą kodu zaprezentować graf zamieszczony na początku tej sekcji?

Zacznijmy od wierzchołków.

graf = Graf([7, 2, 3, 1, 4, 5, 6, 0])

Mamy do czynienia z grafem spójnym, więc jego wierzchołki połączone są krawędziami.

graf = Graf([7, 2, 3, 1, 4, 5, 6, 0], [[7, 3], [2, 3], [3, 1], [4, 1], [5, 1], [6, 1], [0, 1]])

Ćwiczenie 1

Dany jest graf G.

RdcdsO5lgdokK

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

Słownik

droga

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

struktura składająca się z niepustego zbioru wierzchołków oraz ze zbioru krawędzi; dla grafu $G$ zbiór wierzchołków oznaczamy $V(G)$ (ang. verticies – wierzchołki), a zbiór krawędzi – $E(G)$ (ang. edges – krawędzie); liczbę elementów zbioru $V(G)$ oznaczamy literą $n$ , zaś liczbę elementów zbioru $E(G)$ – $m$

graf spójny

graf, w którym każda para wierzchołków połączona jest drogą

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 $G$ jest izomorficzny z grafem $H$ , 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 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ź

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

zbiór złożony jedynie z dwóch różnych elementów: ${a, b}$

stopień wierzchołka

liczba krawędzi incydentnych z danym wierzchołkiem

wierzchołek

inaczej: punkt, węzeł; element niepustego zbioru, który wraz ze zbiorem krawędzi tworzy graf

Wprowadzenie

Prezentacja multimedialna

Struktura grafu

Wierzchołki i krawędzie

Przykład

Słownik