GRAF PŁASKI – graf, którego krawędzie (łuki) nie mają punktów wspólnych innych prócz wierzchołków, połączenie tylko przez krawędzie (nie łuki)
GRAF SPÓJNY - f nazywamy spójnym, jeśli dla każdej pary wierzchołków istnieje ścieżka, która je łączy.
GRAF PEŁNY MAKSYMALNIE SPÓJNY – to taki, w którym każda para wierzchołków jest połączona z krawędzią.
DRZEWO - skończony, spójny graf bez cykli (obwodów) zawierający co najmniej 2 wierzchołki.
DROGA lub ŚCIEŻKA – ciąg łuków, w którym koniec każdego poprzedniego łuku jest początkiem następnego, odpowiednikiem w grafie nieskierowanym jest ŁAŃCUCH.
DŁUGOŚĆ DROGI – liczba łuków w ciągu.
OBWÓD – (cykl w grafie nieskierowanym) – skończona droga, dla której początek pierwszego łuku i koniec ostatniego są tym samym wierzchołkiem odpowiednikiem w grafie nieskierowanym jest CYKL.
ODDALENIE TOPOLOGICZNE – d(x,y) dwóch wierzchołków grafu nazywamy długość najkrótszego (tj. składającego się z najmniejszej liczby krawędzi) łączącej je łańcuchami.
TOPOLOGIA ALGEBRAICZNA – dział matematyki zajmujący się własnościami topologicznymi figur – są to takie własności, które nie ulegają zmianie przy najbardziej radykalnych transformacjach tych figur, np. rozciąganiu, skracaniu, rozerwaniu. Topologia pomija metryczne własności figur, a pewne własności pozostają niezmienne : ta sama liczba wierzchołków, te same wierzchołki połączone ze sobą.
SIEĆ TRANSPORTOWA JAKO GRAF
· Sieć przedstawiana jest wtedy jako zbiór punktów, węzłów będących wierzchołkami grafu oraz łączących je lini, odcinków dróg – będących krawędziami lub łukami w grafie.
· Grafy wyróżniają się wśród figur geometrycznych własnościami topologicznymi nie ulegają zmianie przy najbardziej radykalnych transformacjach tych figur.
1. Liczba wierzchołków
2. Liczba krawędzie
3. Porządek (kolejność) połączeń między wierzchołkami
GRAFOWE MIARY SPÓJNOŚĆI SIECI
Stopień wzajemnego powiązania wierzchołków grafu (a więc węzłów sieci) określa jego spójność. Im bardziej rozbudowana jest sieć połączeń miedzy elementami danego zbioru wierzchołków, tym bardziej jest spójny.
Miary spójności są szczególnie przydatne w szkicach rozwoju sieci transportowej w czasie. Stopien spójności, czyli powiązań węzłów sieci może stanowić miernik świadczący o złożoności powiązań społeczno – gospodarczych regionu.
W MINIMALNIE SPOJNYM istnieje tylko jeden ciąg krawędzi (łańcuch) miedzy każda para wierzchołków – liczba krawędzi jest mniejsza wtedy o od liczby wierzchołków (v).
W GRAFIE MAKSYMALNIE SPOJNYM tj. pełnym, liczba krawędzi (e max) stanowi połowę iloczynu. Liczby wierzchołków i liczby o mniejszej od niej. Uogólniając można wiec zapisać ze liczba krawędzi (e) w grafach spójnych o określonej liczbie wierzchołków (v) zawiera się w przedziale
v-1≤e≤vv-1/2
MIARY DOSTEPNOSCI WIERZCHOŁKÓW GRAFU (WĘZŁÓW SIECI)
· Dostepnosc węzłów w sieci transportowej odpowiada per analogiem dostępności wierzchołków w grafie
· Pierwsza grupa miar wskazujących na dostępność wierzcholków w grafie to miary centralności, do których zaliczamy :
1. Liczbe asocjacji
2.
3.
1. Liczbę asocjacji wierzchołka x/e(x)/ nazywamy największą spośród jego oddaleń do wszystkich pozostałych wierzchołków grafu
e(x)=max d(x,y)
gdzie x,y należy do zbioru X
· Wierzchołek o skończonej, najmniejszej liczbie asocjacji określamy mianem punktu centralnego grafu
p = min e (x)
Graf może mieć wiele punktów centralnych. A zatem węzły transportowe z najniższą liczbą ……… zajmują centralną pozycję w sieci – są najbardziej dostępne.
Maciejka2761