Graf (matematyka)

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Graf – podstawowy obiekt rozważań teorii grafów, struktura matematyczna służąca do przedstawiania i badania relacji między obiektami. W uproszczeniu graf to zbiór wierzchołków, które mogą być połączone krawędziami w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków.

Macierz sąsiedztwa (multi)grafu G {displaystyle G} – macierz kwadratowa, w której aij oznacza liczbę krawędzi pomiędzy wierzchołkami i {displaystyle i} i j {displaystyle j} . W przypadku grafów prostych macierz sąsiedztwa jest macierzą zerojedynkową z zerami na głównej przekątnej. Dla grafów nieskierowanych macierz sąsiedztwa jest z definicji symetryczna.Teoria grafów to dział matematyki i informatyki zajmujący się badaniem własności grafów. Informatyka rozwija także algorytmy wyznaczające pewne właściwości grafów. Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór nie związanych z grafami.

Wierzchołki grafu mogą być numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektami. Wierzchołki należące do krawędzi nazywane są jej końcami. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie nazywany jest grafem skierowanym lub orgrafem. Krawędź grafu może posiadać wagę, to znaczy przypisaną liczbę, która określa na przykład odległość między wierzchołkami (jeśli np. graf jest reprezentacją połączeń między miastami). W grafie skierowanym wagi mogą być zależne od kierunku przechodzenia przez krawędź (np. jeśli graf reprezentuje trud poruszania się po jakimś terenie, to droga pod górkę będzie miała przypisaną większą wagę niż z górki).

Algebra Boole’a – algebra ogólna stosowana w matematyce, informatyce teoretycznej oraz elektronice cyfrowej. Jej nazwa pochodzi od nazwiska matematyka, filozofa i logika George’a Boole’a. Teoria algebr Boole’a jest działem matematyki na pograniczu teorii częściowego porządku, algebry, logiki matematycznej i topologii.Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.

Za pierwszego teoretyka i badacza grafów uważa się szwajcarskiego matematyka i fizyka Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich. Pierwsze użycie określenia „graf” przypisywane jest Jamesowi Josephowi Sylvesterowi – matematykowi angielskiego pochodzenia.

Zastosowanie grafów[ | edytuj kod]

Zastosowanie grafów
Drzewo binarne
Niedeterministyczny automat skończony
Graficzne przedstawienie cząsteczki propanu

Za najstarszy przykład zastosowania grafów w rozwiązaniu zadanego problemu uznaje się zagadnienie mostów królewieckich, opis którego opublikował w 1736 roku Leonhard Euler:

Wielka Brytania, Zjednoczone Królestwo (ang. United Kingdom), Zjednoczone Królestwo Wielkiej Brytanii i Irlandii Północnej (ang. United Kingdom of Great Britain and Northern Ireland) – unitarne państwo wyspiarskie położone w Europie Zachodniej. W skład Wielkiej Brytanii wchodzą: Anglia, Walia i Szkocja położone na wyspie Wielka Brytania oraz Irlandia Północna leżąca w północnej części wyspy Irlandia. Na wyspie tej znajduje się jedyna granica lądowa Zjednoczonego Królestwa z innym państwem – Irlandią. Poza nią, Wielka Brytania otoczona jest przez Ocean Atlantycki na zachodzie i północy, Morze Północne na wschodzie, kanał La Manche na południu i Morze Irlandzkie na zachodzie.Stopień wierzchołka w grafie to liczba krawędzi sąsiadujących z wierzchołkiem. Jest on równy sumie liczb wszystkich łuków wchodzących, wychodzących, krawędzi i pętli; każdą pętlę liczy się jednak jak dwie krawędzie. W grafach skierowanych można też wyróżnić stopień wchodzący i stopień wychodzący. Są to odpowiednio liczby łuków wchodzących do i wychodzących z wierzchołka.

Konigsberg bridges.png7 bridges.svgKönigsberg graph.png

Grafy mogą służyć do praktycznych zastosowań (także z pomocą komputerów) w wielu różnorodnych problemach, np.: sieć dróg z wierzchołkami reprezentującymi skrzyżowania i krawędziami przedstawiającymi ulice, sieć pomieszczeń i korytarzy w budynkach, dzięki czemu możliwe jest komputerowe wynajdywanie najlepszej drogi ze swojego obecnego położenia do pożądanego celu. Algorytmy grafowe stanowią istotną część programów obsługujących urządzenia GPS. System sztucznej inteligencji w niektórych grach komputerowych musi odszukać dla sterowanych przez program postaci najlepszą drogę, która pozwoli zaatakować przeciwnika. Zagadnienie to może być rozwiązane w oparciu o własności grafów. Przedstawienie w formie grafów sieci komputerowych pozwala na stworzenie oprogramowania usprawniającego trasowanie w Internecie. W dużych organizacjach realizację zlecanych przez klientów zadań można przedstawić w postaci grafów, dzięki czemu możliwe jest zwiększenie wydajności: wierzchołki mogą reprezentować pracowników, a krawędzie grafu – przepływ zadań. Za pomocą związanych z grafami pojęć można opisywać też m.in. rysunki obwodów, schematy blokowe, ponieważ przedstawiają one połączenia lub relacje, zachodzące między różnymi fragmentami wykresu.

Mając graf planarny G można zdefiniować dla niego pojęcie grafu dualnego G*. Termin dualny (ang. dual) jest użyty ponieważ dualność jest symetryczna, jeśli graf X jest dualnym grafem grafu Y, to graf Y jest dualnym grafem grafu X; w efekcie grafy takie są podawane jako pary.Przestrzeń metryczna – zbiór z zadaną na nim metryką, tj. funkcją, która określa odległość między każdą parą elementów tego zbioru.

Drzewa grafowe przydatne są w praktycznej reprezentacji różnego rodzaju hierarchii. Mistrzostwa sportowe czy drzewo genealogiczne mogą być w przejrzysty sposób opisane przez drzewa binarne. Do tworzenia kodów Huffmana można wykorzystać drzewa binarne z wagami. Idea działania danego niedeterministycznego automatu skończonego może być w przejrzysty sposób pokazana przez odpowiedni graf.

Kolorowanie grafu polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru.Wykres – graficzna forma przedstawienia zmienności zjawiska, procesu, wielkości, zależności lub jakichkolwiek danych. Zwykle przedstawiany w dwóch wymiarach, ale może być wielowymiarowy.

Wzrasta również znaczenie i wykorzystanie teorii grafów w dziedzinach takich, jak chemia, lingwistyka, geografia, architektura i inne.

Definicje[ | edytuj kod]

Graf nieskierowany
Graf skierowany
Graf z wagami
Multigraf

Różni autorzy stosują bardzo odmienne sposoby definiowania i oznaczania elementów grafu.

Graf[ | edytuj kod]

Jedną z definicji grafu jest: graf, graf prosty lub graf nieskierowany składa się z dwóch zbiorów: oraz przy czym jest niepustym zbiorem, którego elementy nazywane są wierzchołkami, a jest rodziną dwuelementowych podzbiorów zbioru wierzchołków zwanych krawędziami – Definicja ta nie wymaga, by i były skończone. W praktyce rozważa się także grafy o nieskończonej liczbie wierzchołków – wtedy liczba krawędzi może być zarówno skończona, jak i nieskończona.

Graf planarny – graf, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim.P2P (ang.) Peer-to-Peer – model komunikacji w sieci komputerowej, zapewniający wszystkim hostom te same uprawnienia, w odróżnieniu od architektury klient-serwer.

Graf skierowany[ | edytuj kod]

 Osobny artykuł: Graf skierowany.

Graf skierowany lub inaczej digraf składa się z dwóch zbiorów – niepustego zbioru wierzchołków oraz rodziny par uporządkowanych elementów zbioru zwanych krawędziami lub łukami grafu skierowanego. Kolejność wierzchołków w parze wyznacza kierunek krawędzi – w przypadku pary łuk biegnie z wierzchołka do wierzchołka . Podobnie, jak w przypadku grafu nieskierowanego, definicja ta ma sens zarówno wtedy, gdy zbiory lub są skończone, jak i nieskończone.

Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.Komputer (z ang. computer od łac. computare – liczyć, sumować; dawne nazwy używane w Polsce: mózg elektronowy, elektroniczna maszyna cyfrowa, maszyna matematyczna) – maszyna elektroniczna przeznaczona do przetwarzania informacji, które da się zapisać w formie ciągu cyfr albo sygnału ciągłego.

Graf mieszany[ | edytuj kod]

Graf mieszany to uporządkowana trójka grafu gdzie zbiory są zdefiniowane jak wyżej, czyli zawiera jednocześnie krawędzie skierowane i nieskierowane.

Kazimierz Kuratowski (ur. 2 lutego 1896 w Warszawie, zm. 18 czerwca 1980 w Warszawie), polski matematyk, jeden z czołowych przedstawicieli warszawskiej szkoły matematycznej.Las - graf, którego każdy spójny podgraf jest drzewem. Równoważnie można zdefiniować las po prostu jako acykliczny graf nieskierowany (czyli nie zawierający żadnych cykli). Wtedy jego spójne składowe są drzewami.

Grafy z wagami[ | edytuj kod]

Przez zdefiniowanie funkcji z lub w pewien zbiór można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatkowych informacji. Etykiety liczbowe są często nazywane wagami, a graf grafem z wagami (grafem z ważeniem, grafem ważonym).

Alfabet łaciński, łacinka, alfabet rzymski – alfabet, system znaków służących do zapisu większości języków europejskich oraz wielu innych. Jest najbardziej rozpowszechnionym alfabetem na świecie – posługuje się nim ok. 35% ludzkości. Wywodzi się z systemu służącego do zapisu łaciny.Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.

W grafie ważonym krawędziowo zbiór tworzący graf jest rozszerzony o funkcję taką, że dla każdej krawędzi jest wagą danej krawędzi.

Turniej to graf skierowany w którym każde dwa wierzchołki są połączone dokładnie jedną skierowaną krawędzią. Jest to skierowany odpowiednik grafu pełnego.Trasowanie (ang. routing, pol. ruting, rutowanie) – w informatyce wyznaczanie trasy i wysłanie nią pakietu danych w sieci komputerowej. Urządzenie węzłowe, w którym kształtowany jest ruch sieciowy, nazywane jest routerem – jego rolę może pełnić np. komputer stacjonarny czy oddzielne dedykowane urządzenie.

Grafem ważonym wierzchołkowo nazywa się graf w którym jest funkcją przypisującą każdemu wierzchołkowi pewną liczbę naturalną nazywaną wagą wierzchołka. Graf taki oznacza się przez (lub po prostu a to, że jest ważony wynika z kontekstu), natomiast wagę wierzchołka oznacza się przez .

Graf pełny jest grafem prostym, w którym dla każdej pary węzłów istnieje krawędź je łącząca. Graf pełny o n {displaystyle n} wierzchołkach oznacza się następująco: K n {displaystyle K_{n}} .Ściana grafu płaskiego to część płaszczyzny, wyznaczona przez krawędzie tego grafu. Każdy graf płaski posiada jedną nieograniczoną ścianę (zwaną ścianą zewnętrzną) oraz skończoną liczbę ścian zamkniętych tj. ograniczonych krawędziami grafu.

Warianty definicji[ | edytuj kod]

W wielu zastosowaniach podstawowe definicje grafów nie są wystarczające, dlatego wprowadza się pewne modyfikacje. Na przykład aby wprowadzić pętlę, czyli krawędź, której oba końce są tym samym wierzchołkiem, w definicji grafu nieskierowanego należy dopuścić zbiory jednoelementowe albo użyć dwuelementowego multizbioru W grafie skierowanym pętla jest naturalnie reprezentowana przez parę .

Tablica w informatyce to kontener danych dostępnych, w którym poszczególne komórki dostępne są za pomocą kluczy, które najczęściej przyjmują wartości numeryczne. Rozmiar tablicy jest albo ustalony z góry (tablice statyczne), albo może się zmieniać w trakcie wykonywania programu (tablice dynamiczne).Cykl prosty to droga zamknięta, czyli taka, której koniec (ostatni wierzchołek) jest identyczny z początkiem (pierwszym wierzchołkiem).

Czasami potrzebna 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. Uzyskuje się go np. przez zdefiniowanie lub jako multizbioru.

Izomorfizm grafów – Grafy G jest izomorficzny z grafem F, jeśli istnieje takie, różnowartościowe i na, przyporządkowanie (bijekcja) wierzchołków grafu H wierzchołkom grafu G , że jeśli jakieś dwa wierzchołki są połączone krawędzią w jednym z grafów, to odpowiadające im wierzchołki w drugim grafie również łączy krawędź.Global Positioning System (GPS) - właściwie GPS-NAVSTAR (ang. Global Positioning System – NAVigation Signal Timing And Ranging) – jeden z systemów nawigacji satelitarnej, stworzony przez Departament Obrony Stanów Zjednoczonych, obejmujący swoim zasięgiem całą kulę ziemską. System składa się z trzech segmentów: segmentu kosmicznego - 31 satelitów orbitujących wokół Ziemi na średniej orbicie okołoziemskiej; segmentu naziemnego - stacji kontrolnych i monitorujących na ziemi oraz segmentu użytkownika - odbiorników sygnału. Zadaniem systemu jest dostarczenie użytkownikowi informacji o jego położeniu oraz ułatwienie nawigacji po terenie.
Przykłady odmiennych sposobów definiowania grafu

Graf może być też określony jako niepusty zbiór wierzchołków i dana na nim relacja binarna taka, że dla dowolnych wierzchołków i zachodzi wtedy i tylko wtedy, gdy istnieje krawędź łącząca i . Dla grafów nieskierowanych relacja ta jest symetryczna.

Talia grafu (ang. girth) – długość najkrótszego cyklu zawartego w grafie. Przyjmuje się, że obwód grafów acyklicznych jest równy nieskończoności. Struktura matematyczna (także model, system semantyczny, model semantyczny, dziedzina, struktura pierwszego rzędu) - w matematyce zbiór obiektów matematycznych połączonych w pewien system.

Graf nieskierowany można też definiować jako trójkę gdzie jest niepustym zbiorem, którego elementy nazywają się wierzchołkami, jest rodziną dwuelementowych podzbiorów zbioru wierzchołków zwanych krawędziami: a jest funkcją ze zbioru w zbiór wszystkich podzbiorów jedno- lub dwuelementowych zbioru Wówczas jeżeli jest krawędzią grafu, to kończy się ona wierzchołkami gdy i jest pętlą wierzchołka gdy

Dariusz Piotr Dereniowski (ur. 1979) – polski informatyk i matematyk, nauczyciel akademicki, doktor habilitowany nauk technicznych.Matroid to obiekt stanowiący uogólnienie przestrzeni liniowej wraz z istniejącym w niej pojęciem niezależności liniowej. Matroidy bada się głównie w takich działach matematyki, jak algebra, geometria czy matematyka dyskretna. Pojęcie to zostało wprowadzone w 1935 roku przez angielskiego matematyka Hasslera Whitneya.

Graf skierowany określa się też jako trójkę gdzie zbiory i są zdefiniowane analogicznie do grafów nieskierowanych a jest funkcją ze zbioru krawędzi w zbiór uporządkowanych par (kwadrat kartezjański, czyli iloczyn kartezjański zbioru ze sobą) wierzchołków – Jeśli jest krawędzią grafu oraz to nazywane jest początkiem krawędzi a – końcem krawędzi i mówi się, że biegnie od do .

Odległość między dwoma wierzchołkami definiuje się w teorii grafów jako liczbę krawędzi w najkrótszej ścieżce, łączącej rozpatrywane wierzchołki. W przypadku, gdy nie istnieje taka ścieżka, tj. gdy wierzchołki z danej pary należą do odrębnych spójnych składowych jednego grafu niespójnego, odległość z definicji równa się nieskończoności. W ten sposób zdefiniowana odległość może zostać znaleziona poprzez zastosowanie algorytmu przeszukiwania wszerz (BFS) bądź algorytmu Dijkstry.Domknięcie przechodnie relacji dwuargumentowej R na zbiorze X jest to najmniejsza (w sensie inkluzji) relacja przechodnia R na zbiorze X, która zawiera R.


Podstrony: 1 [2] [3] [4] [5] [6]




Warto wiedzieć że... beta

Multizbiór (ang. multiset, pol. wielozbiór) uogólnienie pojęcia zbioru, w którym w odróżnieniu od klasycznych zbiorów jeden element może występować wiele razy. Nie jest dana jednak żadna ich kolejność i tym multizbiór różni się od krotki.
Relacja symetryczna – relacja, która jeśli zachodzi dla pary ( x , y ) {displaystyle (x,y)} , to zachodzi też dla pary ( y , x ) {displaystyle (y,x)} .
Lista - struktura danych służąca do reprezentacji zbiorów dynamicznych, w której elementy ułożone są w liniowym porządku. Rozróżniane są dwa podstawowe rodzaje list: lista jednokierunkowa w której z każdego elementu możliwe jest przejście do jego następnika oraz lista dwukierunkowa w której z każdego elementu możliwe jest przejście do jego poprzednika i następnika.
Graf k-dzielny - to naturalne rozszerzenie klasy grafów dwudzielnych - jest to graf, którego zbiór wierzchołków można podzielić na k parami rozłącznych podzbiorów takich, że żadne dwa węzły należące do tego samego zbioru nie są połączone krawędzią.
Zagadnienie mostów królewieckich − problem, nad którym rzekomo głowili się mieszkańcy Królewca, a który rozwiązał w XVIII wieku Leonhard Euler.
Problem komiwojażera (TSP - ang. travelling salesman problem) jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
Teoria modeli (nazywana też czasem semantyką logiczną) to dział logiki matematycznej zajmujący się badaniem własności modeli teorii aksjomatycznych i zależności między nimi. Dziedzina ta jest w znacznym stopniu powiązana z algebrą i teorią mnogości, ale ma też mocno rozbudowany własny aparat pojęciowy i w swojej współczesnej postaci jest w pełni samodzielną dziedziną wiedzy.

Reklama