Wikipedysta:Royas/graf
Z Wikipedii
Spis treści |
[edytuj] Definicja
[edytuj] Graf
Graf lub graf nieskierowany to uporządkowana para G := <V,E> gdzie:
Wierzchołki należące do krawędzi nazywane są jej końcami. Zazwyczaj V (i co za tym idzie E) są określane jako zbiory skończone.
[edytuj] Graf skierowany
Graf skierowany lub inaczej digraf to uporządkowana para G := <V,A> gdzie:
-
- V jest zbiorem wierzchołków,
- A jest zbiorem uporząkowanych par różnych wierzchołków ze zbioru V, zwanych krawędziami skierowanymi, lub łukami: A⊆{(u,v): u,v∈V ∧ v≠u}.
Przyjmuje się, że krawędź e:=(x,y) jest skierowana z x do y, czyli wychodzi z x, a wchodzi do y.
[edytuj] Graf mieszany
Graf mieszany to upożądkowany trójka G:=<V,E,A> gdzie zbiory V,E,A są zdefiniowane jak wyżej.
[edytuj] Modyfikacje definicji
W wielu zastosowanich tak zdefiniowane grafy nie są wystarczające i wprowadza się pewne modyfikacje.
Pętla to krawędz, której oba końce są tym samym wierzchołkiem. W grafie nieskierowanym pętlę możne reprezentować jako zbiór jednoelementowy {v}, lub jako dwuelementowy multizbiór {v,v}. W grafie skierowanym wystarczy zrezygnować ze słowa różne w definicji.
Czasami patrzebna jest możliwość połączenia dwóch wierzchołków przy pomocy więcej niż jednej krawędzi (w przypadku grafu skierowanego chodzi o łuki o takim samym zwrocie. Graf, który na to pozwala, nazywany jest multigrafem. Użyskuje się go przez np. zdefiniowanie E, lub A jako multizbioru.
Przez zdefiniowanie funcji z V, E, lub A w pewnien zbiór X, można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatowych informacji. Etykiety liczbowe są często nazywane wagami.
