Graf (matematyka)

Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


Graf – podstawowy obiekt rozważań teorii grafów[1][2], struktura matematyczna służąca do przedstawiania i badania relacji między obiektami[3][4]. 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[5].

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[6]. Wierzchołki należące do krawędzi nazywane są jej końcami[7]. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie nazywany jest grafem skierowanym[8] lub orgrafem[9]. 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)[10]. 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)[11].

Za pierwszego teoretyka i badacza grafów uważa się[12] 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[13].

Inne języki
العربية: رسم بياني
asturianu: Grafo
azərbaycanca: Qraf (riyaziyyat)
беларуская: Граф (матэматыка)
eesti: Graaf
Ελληνικά: Γράφος
español: Grafo
Esperanto: Grafeo
euskara: Grafo
galego: Grafo
한국어: 그래프
հայերեն: Գրաֆներ
Bahasa Indonesia: Graf (matematika)
italiano: Grafo
latviešu: Grafs
magyar: Gráf
मराठी: जाल, (गणित)
norsk nynorsk: Grafisk framstilling
Piemontèis: Graf
português: Grafo
română: Graf
Simple English: Graph (mathematics)
slovenčina: Graf (matematika)
slovenščina: Graf (matematika)
српски / srpski: Граф
srpskohrvatski / српскохрватски: Graf
suomi: Graafi
українська: Граф (математика)
中文: 图 (数学)