algorytm.org

Grafy i ciąg dalszy

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Grafy i ciąg dalszy
Ocena użytkowników:***** / 12
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 28 lipca 2005 23:06

Oto dodatkowe informacje na temat grafów, potrzebne w bardziej skomplikowanych algorytmach.
Kilka definicji:
Stopień wierzchołka - to liczba krawędzi do niego przyległych
Graf regularny - to graf, w którym każdy wierzchołek ma taki sam stopień
Graf planarny - to graf, który można przedstawić na płaszczyźnie tak, by żadne dwie krawędzie się nie przecinały
f-graf - to graf z ograniczonym stopniem wierzchołka, tzn. jego stopień nie może być większy niż f
Graf prosty - to graf bez pętli własnych i krawędzi równoległych
Niezmiennik grafu - to liczba lub ciąg liczb, który zależy tylko od struktury grafu a nie od sposobu jego poetykietowania (np. liczba wierzchołków, liczba krawędzi)
Liczba chromatyczna grafu - to najmniejsza liczba kolorów potrzebnych do pokolorowania wierzchołków grafu tak, by żadne dwa przyległe wierzchołki nie były tego samego koloru
Przykładu do powyższych definicji:
stopień wierzchołka 1=2, wierzchołka 2=3, graf planarny, f-graf dla f=3
stopień wierzchołka 1=2, wierzchołka 2=3, graf planarny, f-graf dla f=3
graf 2-regularny, planarny
graf 2-regularny, planarny
graf planarny, f-graf dla f=4
graf planarny, f-graf dla f=4
graf planarny, liczba chromatyczna wynosi 3
graf planarny, liczba chromatyczna wynosi 3

Teraz przejdźmy do bardzo ważnego problemu: generowania grafów losowych.
Istnieje kilka modeli grafów losowych, omówimy najważnejsze:
  • model G(n,p) - n (liczba wierzchołków) jest dana, p jest tzw. prawdopodobieństwem krawędziowym (0<=p<=1). Liczba p jest określona dla każdej krawędzi, określa ono prawdzopodobieństwo, że dana krawędź znajdzie się w grafie
  • model G(n,k) - n jest dana, ze zbioru wszystkich możliwych krawędzi są losowane kolejne krawędzie, lecz tu, w odróżnieniu do poprzedniego modelu, z jednakowym prawdopodobieństwem
  • model G(n,f) - n jest dana, f oznacza maksymalny stopień wierzchołka, którego nie można przekroczyć.
Przy losowaniu grafów stosuje się często tzw. metodę przesiewania (lub sito, wykorzystane przez Eratostenesa przy wyznaczaniu liczb pierwszych). Dzieli się ona na kilka części:
  1. wybór odpowiedniego generatora (zgodnie z powyższymi modelami)
  2. każdy wygenerowany graf jest weryfikowany, czy spełnia założenia wybranego modelu (np. czy jego największy stopień nie jest większy niż f), grafy które ich nie spełniają są odrzucane, reszta jest zapisywana np. w pliku
  3. po zakończeniu generowania w pliku znajdują się grafy spełniające założenia danego modelu. Należy jeszcze sprawdzić, czy grafy te są różne, tzn. czy nie ma wśród nich grafów izomorficznych
Testowanie izomorfizmu jest problemem trudnym. Nie ma żadnego szybkiego algorytmu sprawdzającego, czy dwa grafy są izomorficzne. Powodem tego jest wiele kryteriów izomorfizmu grafów, jeżeli dane grafy nie spełniają jekiegoś kryterium, należy przejść do kolejnego (co zwiększa koszt obliczeń).
Kryterium izomorfizmu grafów:
  1. jednakowa liczba wierzchołków
  2. jednakowa liczba krawędzi
  3. jednakowy ciąg stopni wierzchołków
  4. jendakowe ciągi stopni wierzchołków dla sąsiadów
  5. jednakowa liczba trójkątów (cykli o długości 3)
  6. tworzenie macierzy odległości
Pierwsze dwa kroki można wykonać wprawdzie w czasie Θ(n), lecz w punkcie 5 czas zaczyna gwałtownie wzrastać.
Poprawiony: 29 sierpnia 2012 21:55
Komentarze
photo
0 # a8o2ge 2010-03-16 10:19
Poszukuję więcej informacji na temat G(n,f) znacie jakąś fachową literaturę lub stronę w necie? Wujek Google słabo dziś coś szuka
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz