Graf
Graf – struktura składająca się ze zbioru wierzchołków oraz zbioru krawędzi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawić wiele zagadnień.
Wyróżniamy grafy nieskierowane oraz grafy skierowane. W grafie nieskierowanym relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.
Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.
Wybrane pojęcia związane z teorią grafów
- Trasa – ciąg kolejnych krawędzi, za pomocą którego możemy przejść z jednego wierzchołka grafu do innego (lub wrócić do tego samego).
- Ścieżka – trasa, w której każda krawędź występuje co najwyżej raz (mogą natomiast powtarzać się wierzchołki).
- Droga (ścieżka prosta) – trasa, w której każdy wierzchołek występuje co najwyżej raz. Wyjątkiem jest wierzchołek końcowy, który może być wierzchołkiem początkowym – taka ścieżka to cykl.
- Pętla – krawędź prowadząca z wierzchołka do niego samego.
- Krawędź wielokrotna – kilka krawędzi łączących tę samą parę wierzchołków.
- Graf prosty – graf nie zawierający żadnych pętli ani krawędzi wielokrotnych.
- Graf spójny – graf, w którym można wyznaczyć ścieżkę między każdą parą wierzchołków.
- Graf pełny – graf prosty, w którym każda para wierzchołków jest bezpośrednio połączona krawędzią.
- Drzewo – graf spójny nie mający żadnych cykli (taki, w którym między każdą parą wierzchołków można wyznaczyć dokładnie jedną ścieżkę).
Reprezentacja w pamięci komputera
W pamięci komputera grafy zazwyczaj są przechowywane w postaci list lub macierzy sąsiedztwa. W przypadku list sąsiedztwa każdemu wierzchołkowi przyporządkowana jest lista wierzchołków z nim sąsiadujących. W przypadku macierzy sąsiedztwa w pamięci przechowywana jest macierz, w której każdy wiersz i każda kolumna odpowiada innemu wierzchołkowi. Liczba na przecięciu wiersza i kolumny informuje, ile krawędzi łączy daną parę wierzchołków (w przypadku grafu ważonego prostego można tam zamieścić wagę krawędzi). W przypadku grafu nieskierowanego macierz jest symetryczna.
Bibliografia
- R.J. Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301150662.
Liczba głosów: 0.
Dodano: 6 grudnia 2017 10:31, ostatnia edycja: 30 stycznia 2019 15:58.
Zobacz też
Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.
Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.
Metoda Otsu – algorytm służący do binaryzacji obrazu, czyli przekształcenia obrazu w odcieniach szarości do obrazu binarnego. Metoda ta realizuje progowanie globalne – dla całego obrazu wyznaczany jest jeden próg jasności, a następnie wszystkim pikselom jaśniejszym od tego progu przypisywana jest jedna wartość, a ciemniejszym druga.
Algorytm jest oparty na analizie histogramu. Przygotowanie histogramu polega na zliczeniu pikseli w każdym możliwym odcieniu (zazwyczaj liczba odcieni wynosi 256, gdyż tyle da się zakodować w jednym bajcie). Następnie należy sprawdzić każdy możliwy próg jasności i wybrać ten, dla którego wariancja międzyklasowa jest największa (lub suma ważona wariancji wewnątrzklasowych jest najmniejsza).
Jeśli obrazem wejściowym jest obraz kolorowy, można go łatwo sprowadzić do odcieni szarości. W przypadku kolorów zakodowanych w RGB najprostszym rozwiązaniem jest uśrednienie dla każdego piksela wartości wszystkich trzech kanałów.
Wyznaczanie maksymalnego przepływu – problem obliczeniowy polegający na wyznaczeniu maksymalnego przepływu w sieci przepływowej.
Sieć przepływowa jest skierowanym grafem prostym. Każdy łuk (krawędź skierowana w grafie) ma swoją nieujemną wagę, która oznacza maksymalny dopuszczalny przepływ w tym łuku. Na potrzeby tego artykułu nazwijmy rzeczy przepływające przez sieć danymi. Jeden z wierzchołków sieci jest źródłem, z którego wypływają przesyłane dane. Inny z wierzchołków to ujście, do którego te dane wpływają. Zakłada się ponadto, że dla każdego z pozostałych wierzchołków istnieje ścieżka ze źródła do ujścia przechodząca przez ten wierzchołek.
Przepływem w sieci nazywamy przyporządkowanie każdemu łukowi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez ten łuk. Wartości te muszą spełniać następujące warunki:
- Wartość przyporządkowana krawędzi musi być mniejsza lub równa jej wadze (warunek przepustowości).
- Do każdego wierzchołka (poza źródłem i ujściem) musi wpływać tyle samo danych, ile z niego wypływa (warunek zachowania przepływu).
Omawiany problem polega na dobraniu takiego przepływu, aby liczba danych wypływających ze źródła (i zarazem wpływających do ujścia) była jak największa.