Graf

Graf to – w uproszczeniu – 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 (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.

Moc zbioru – własność zbioru, która opisuje jego liczebność. Nieformalnie, moc zbioru jest tym większa im większy jest zbiór. Pojęcie mocy zbioru opiera się o pojęcie równoliczności dwóch zbiorów - zbiory A i B są równoliczne, gdy każdy element zbioru A można połączyć w parę z dokładnie jednym elementem zbioru B, innymi słowy istnieje bijekcja (funkcja różnowartościowa i "na") między zbiorami A i B. Zbiory równoliczne mają tę samą moc. Moce zbiorów są konkretnymi obiektami matematycznymi, nazywanymi liczbami kardynalnymi.
Teoria grafów dział w matematyce i informatyce 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 zwykle są numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektami. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie jest grafem skierowanym. Krawędź może posiadać także wagę, to znaczy przypisaną liczbę, która określa na przykład odległość między wierzchołkami (jeśli na przykład 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).

Teoria złożoności obliczeniowej to dział teorii obliczeń. Głównym jej 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 twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać: problem spełnialności, problem najkrótszej ścieżki, problem faktoryzacji oraz wiele innych o których wiadomo że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności, będąca drugą ważną gałęzią teorii obliczeń.
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.

Definicje

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

Graf nieskierowany

Graf, graf prosty lub graf nieskierowany to uporządkowana para G := (V,E) gdzie:

V jest niepustym zbiorem. Elementy tego zbioru nazywamy wierzchołkami,

E jest rodziną dwuelementowych podzbiorów zbioru wierzchołków V, zwanych krawędziami: $E\subseteq \{ \{u,v\} : u,v \in V,u \neq v\}$ .

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. Jednak powyższa definicja tego nie wymaga i w praktyce rozważa się też czasami grafy o nieskończonej liczbie wierzchołków (wtedy liczba krawędzi może być skończona, lub nieskończona).

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.
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.

Graf skierowany

Osobny artykuł: Graf skierowany.

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ądkowanych par różnych wierzchołków ze zbioru V, zwanych krawędziami skierowanymi, lub łukami: $A \subseteq V \times V$ .

Przyjmuje się, że krawędź e:=(x,y) jest skierowana z x do y, czyli wychodzi z x, a wchodzi do y.

Graf mieszany

Graf mieszany to uporządkowana trójka G:=(V,E,A) gdzie zbiory V,E,A są zdefiniowane jak wyżej, czyli może zawierać jednocześnie krawędzie skierowane i nieskierowane.

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.
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.

Warianty definicji

W wielu zastosowaniach tak zdefiniowane grafy nie są wystarczające i 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 {v} albo użyć dwuelementowego multizbioru {v,v}. W grafie skierowanym pętla jest naturalnie reprezentowana przez parę (v,v).

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 E, lub A jako multizbioru.

P2P (od ang. peer-to-peer – równy z równym) – model komunikacji w sieci komputerowej, który gwarantuje obydwu stronom równorzędne prawa (w przeciwieństwie do modelu klient-serwer).
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.

Przez zdefiniowanie funkcji z V, E, lub A w pewien zbiór X, można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatkowych informacji. Etykiety liczbowe są często nazywane wagami. Dla grafów z wagami zbiór tworzący graf jest rozszerzony o funkcję $\! \delta: E \to K$ taką, że dla każdej krawędzi $\! e \in E$ , $\! \delta (e)$ jest wagą danej krawędzi

Komputer (z ang. computer od łac. computare – obliczać, dawne nazwy używane w Polsce: mózg elektronowy, elektroniczna maszyna cyfrowa, maszyna matematyczna) – urządzenie elektroniczne służące do przetwarzania wszelkich informacji, które da się zapisać w formie ciągu cyfr albo sygnału ciągłego.
Laboratorium – to miejsce, gdzie przeprowadza się tę część badań naukowych, która wymaga wykonywania wielu powtarzalnych eksperymentów w ściśle kontrolowanych warunkach.

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 $\! R$ taka, że dla dowolnych wierzchołków $\! v$ i $\! u$ $\!vRu$ zachodzi wtedy i tylko wtedy, gdy istnieje krawędź łącząca $\! v$ i $\! u$ . Dla grafów nieskierowanych relacja ta jest symetryczna (zob. też "macierz sąsiedztwa" poniżej).

Graf nieskierowany można też definiować jako trójkę $\! G=(V,E,\gamma)$ , gdzie

$\! V$ jest zbiorem wierzchołków

$\! E$ zbiorem krawędzi

$\! \gamma$ funkcją ze zbioru krawędzi w rodzinę jednoelementowych lub dwuelementowych podzbiorów zbioru wierzchołków – $\! \gamma : E \to (\{\{v,u\}:v,u \in V\}\cup \{\{w\}:w \in V\})$ . Wówczas jeżeli $\! e$ jest krawędzią grafu to:

kończy się ona wierzchołkami $\! u,v\in V$ , gdy $\! \gamma(e)=\{u,v\}$

jest ona pętlą wierzchołka $\! v$ , gdy $\! \gamma(e)=\{v\}$

Graf skierowany określa się też jako trójkę $\! G=(V,E,\gamma)$ , gdzie zbiory $\! V$ i $\! E$ są zdefiniowane analogicznie do grafów nieskierowanych a $\! \gamma$ 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 – $\! \gamma : E \to V\times V$ . Wówczas, jeżeli $\! e$ jest krawędzią grafu $\! G$ to istnieją takie wierzchołki $\! u,v\in V$ , że $\! \gamma(e)=(u,v)$ . W takim przypadku krawędź $\! e$ biegnie z $\! u$ do $\! v$ .

Graf geometryczny

Dla każdego grafu istnieje nieskończenie wiele przedstawiających go rysunków, czasami jednak rozważane są w przypadku grafów własności stricte geometryczne (współrzędne geometryczne wierzchołków, tylko proste krawędzie, "zmieszczenie się" w pewnej przestrzeni itp.). Grafy rozpatrywane jako figury w przestrzeni (w której są one "zanurzone" i która nadaje im cechy charakterystyczne dla danej przestrzeni) nazywa się grafami geometrycznymi.

Trasowanie (ang. routing, pol. ruting, routowanie) – 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, może to być np. komputer stacjonarny lub dedykowane urządzenie (również nazywane routerem).
prof. 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.

Pojęcia służące do opisu grafów

Alfabetyczna lista definicji

Wszystkie drogi w tym grafie są proste, nie ma cykli.

Acentryczność wierzchołka grafu

To maksymalna odległości wierzchołka do innych wierzchołków grafu, lub inaczej długość najdłuższej ścieżki prostej zaczynającej się w danym wierzchołku.

Cykl

Zamknięta droga prosta $e_a,e_b,\ldots ,e_z$ , taka, że krawędź $e_z$ kończy się w początkowym wierzchołku drogi

Droga

Wyznaczona przez krawędzie trasa polegająca na podróżowaniu od wierzchołka do wierzchołka po łączących je krawędziach. Jeżeli przez $e_i$ oznaczy się i-tą krawędź grafu, to droga może być jednoznacznie zapisana jako $e_a,e_b,\ldots,e_z$

Droga prosta

Droga nie zawierająca dwóch tych samych krawędzi

Długość drogi/ścieżki

To liczba krawędzi/wierzchołków tworzących daną drogę/ścieżkę

Droga acykliczna

Droga nie zawierająca cyklu

Gęstość grafu

Stosunek liczby krawędzi do największej możliwej liczby krawędzi: $\frac{2|E|}{|V|\,(|V|-1)}$ . Używa się również określeń: graf gęsty, jeżeli ma on dużo krawędzi w stosunku do liczby wierzchołków i podobnie graf rzadki, jeżeli ma on mało krawędzi w stosunku do liczby wierzchołków. Przy czym znaczenie słów mało i dużo może zależeć od kontekstu.

Klika

Podzbiór wierzchołków danego grafu wraz z krawędziami je łączącymi takich, że każde dwa wierzchołki tego podzbioru są sąsiadami (czyli podgraf pełny).

Kolorowanie grafu

To nadanie każdemu wierzchołkowi koloru, tak by żadne sąsiadujące ze sobą wierzchołki nie były pokolorowane tym samym kolorem.

Krawędzie sąsiednie

Krawędzie kończące się w jednym wierzchołku. W przypadku grafów skierowanych zazwyczaj wymagana jest "zgodność kierunków" krawędzi, tj. dwie krawędzie są sąsiednie, jeżeli odpowiednio kończą się i zaczynają w tym samym wierzchołku.

Krawędź/wierzchołek krytyczny

Krawędź/wierzchołek, po usunięciu której/którego ze zbioru pokrywającego zmniejsza się indeks pokrycia krawędziowego/wierzchołkowego.

Liczba chromatyczna

Najmniejsza liczba kolorów potrzebna do prawidłowego pokolorowania grafu.

Nadgraf grafu H

Taki graf, że H jest jego podgrafem.

Pętla

Krawędź zaczynająca i kończąca się w tym samym wierzchołku

Podgraf grafu H

Graf G uzyskany poprzez usunięcie części wierzchołków z H, wraz z kończącymi się w nich krawędziami

Graf r-regularny:

Graf, w którym każdy wierzchołek grafu jest stopnia r.

Sąsiad:

Dwa wierzchołki są sąsiadami, jeśli istnieje krawędź pomiędzy nimi.

Spójna składowa grafu G

Spójna składowa grafu to możliwie największy spójny podgraf grafu G. Graf spójny ma jedną spójną składową.

Stopień wierzchołka v

Liczba kończących się w nim krawędzi. Oznaczenie: deg(v). W przypadku grafów skierowanych mówi się o stopniach wejściowym i wyjściowym – degIn(v), degOut(v)

Ściana

Obszar zamknięty wyznaczony przez krawędzie grafu (tzw. krawędzie tworzące ścianę). Z pojęciem ściany ściśle powiązane jest twierdzenie Eulera. Uwaga! Za ścianę uważa się też nieskończony obszar znajdujący się "na zewnątrz" grafu (a więc każdy graf ma co najmniej jedną ścianę)!

Ściany sąsiadujące

Ściany są sąsiadujące, jeżeli mają co najmniej jedną wspólną krawędź tworzącą.

Ścieżka

Intuicyjnie jest bardzo podobna do drogi, z tym, że jest wyznaczona przez wierzchołki, tj. można ją opisać poprzez ciąg wierzchołków $v_a,v_b,\ldots ,v_z$

Ścieżka prosta

Ścieżka wyznaczona tak, by żaden wierzchołek na trasie nie powtarzał się

Ścieżka zamknięta

Ścieżka $v_a,v_b,\ldots ,v_z,v_a$ , czyli kończąca się w początkowym wierzchołku

Usunięcie wierzchołka

Przez usunięcie wierzchołka rozumie się wymazanie go, oraz wszystkich kończących się w nim krawędzi z danego grafu

Waga krawędzi

Często od grafu reprezentującego np. sieć połączeń komunikacyjnych oczekuje się nie tylko informacji o istniejącym połączeniu (krawędzi lub ścieżki), ale też o np. długości połączenia. Wprowadza się wtedy wagi, wartość przypisaną każdej krawędzi. Graf taki można wykorzystać np. do wyznaczenie optymalnej, w sensie przejechanych kilometrów trasy, lub, ogólniej rozwiązanie problemu komiwojażera, wyznaczenia optymalnego rozłożenia kabli w sieci, koordynowania wysyłania plików metodą peer to peer itp.

Wierzchołek izolowany

Wierzchołek o stopniu 0, czyli nie będący końcem żadnej krawędzi.

Wierzchołek pokrywający krawędź

Wierzchołek v pokrywa krawędź e, jeżeli e kończy się w v. W analogiczny sposób definiuje się krawędź pokrywającą dany wierzchołek – krawędź e kryje wierzchołek v, gdy się w nim kończy.

Minimalny pokrywający podzbiór krawędzi/wierzchołków

To możliwie najmniejszy podzbiór krawędzi/wierzchołków grafu, taki, że pokrywają one wszystkie wierzchołki/krawędzie danego grafu. Liczność minimalnego zbioru pokrywającego krawędzi/wierzchołków nazywa się indeksem pokrycia wierzchołkowego/krawędziowego. Wszystkie podzbiory o tej liczności i własności nazywa się pokryciem minimalnym.

Wierzchołek rozspajający

Wierzchołek, po usunięciu którego zwiększa się liczba spójnych składowych grafu. Nazywany przegubem tworzy "wąskie gardło" grafu – tj. istnieją w grafie dwa wierzchołki takie, że każda łącząca je droga musi przejść przez wierzchołek rozspajający.

Most

Krawędziowy "odpowiednik" wierzchołka rozspajającego – krawędź, po usunięciu której wzrasta liczba spójnych składowych grafu.

Oznaczenia formalne

Często dla danego grafu G stosuje się skrócone oznaczenia oparte na alfabecie greckim oraz łacińskim:

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.
Alfabet łaciński (łacinka), tzw. 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.

$n\ =\ |V(G)|$ liczba wierzchołków G $m\ =\ |E(G)|$ liczba krawędzi G $\! \delta (G)$ najmniejszy stopień wierzchołka w G $\! \Delta (G)$ największy stopień wierzchołka w G $\! \chi (G)$ liczba chromatyczna G $\! \chi' (G)$ indeks chromatyczny G $\! \omega (G)$ liczba spójnych składowych G

Przykład dla konkretnego grafu

Graf nieskierowany

To przykład grafu nieskierowanego G wraz z jego ilustracją: $\! V(G) = \{ v_1, v_2, v_3, v_4, v_5, v_6 \}$ $\! E(G) = \{ \{v_1, v_2\}, \{v_1, v_5\}, \{v_5, v_4\}, \{v_4, v_6\}$ ,
$\!\{v_4, v_3\}, \{v_3, v_2\}, \{v_2, v_5\} \}$

Jego własności:

W językach programowania, pozwalających na bezpośredni dostęp do pamięci (jak np. Asembler, C, C++, Cyclone), pamięć jest reprezentowana jako jednowymiarowa tablica bajtów - wszystkie zmienne (statyczne i dynamiczne) są umieszczane w tej "tablicy".
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 wierzchołkach oznacza się następująco: Kn.

Przykładową ścieżką prostą może być $\! v_6,v_4,v_5,v_1$ a cyklem $\! v_5,v_4,v_3,v_2,v_5$

Stopnie wierzchołków:

$\! deg(v_1)\ =\ 2$ $\! deg(v_2)\ =\ 3$ $\! deg(v_3)\ =\ 2$ $\! deg(v_4)\ =\ 3$ $\! deg(v_5)\ =\ 3$ $\! deg(v_6)\ =\ 1$

Krawędź $\! \{v_1,v_5\}$ jest sąsiednia z $\! \{v_5,v_2\}$ , ale nie jest z $\! \{v_2,v_3\}$

Graf G ma trzy ściany – zewnętrzną oraz dwie wyznaczone odpowiednio przez ścieżki np. $\! v_2,v_3,v_4,v_5$ i $\! v_1,v_5,v_2$

Graf G jest spójny, czyli ma jedną spójną składową. Natomiast podgraf grafu G, składający się z wierzchołków $\! v_1,v_2,v_5,v_6$ i incydentnych z nimi krawędziami, ma dwie spójne składowe – cykl $\! v_1,v_2,v_5,v_1$ i wierzchołek izolowany $v_6$ .

Izomorfizm i homeomorfizm grafów

Osobny artykuł: Izomorfizm grafów.

Graficzna reprezentacja grafów (w postaci kropek i łączących je krzywych) jest tylko sposobem przedstawienia relacji zachodzącej między wierzchołkami. Dla każdego grafu istnieje nieskończenie wiele przedstawiających go jednoznacznie wykresów, rysunków. Co więcej, właściwości grafów (takie jak większość podanych w następnej sekcji) są niezależne od sposobu numerowania wierzchołków, kolejności ich rysowania itp. Grafy różniące się tylko sposobem ich przedstawienia, lub indeksami nadanymi wierzchołkom, nazywamy izomorficznymi.

Ś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.
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).

Osobny artykuł: Homeomorfizm grafów.

Dwa grafy są homeomorficzne, jeśli z jednego grafu można otrzymać drugi zastępując wybrane krawędzie łańcuchami prostymi lub łańcuchy proste pojedynczymi krawędziami. Mówiąc obrazowo, chodzi o dorysowywanie na krawędziach dowolnej liczby wierzchołków, bądź wymazywanie ich.

Cykl to droga (inaczej: ścieżka prosta) zamknięta, czyli taka, której koniec (ostatni wierzchołek) jest identyczny z początkiem (pierwszym wierzchołkiem).
Izomorfizm grafów – Grafy G i F nazywamy izomorficznymi, jeżeli istnieje bijekcja zbioru wierzchołków grafu G na zbiór wierzchołków grafu F, która zachowuje strukturę grafu (krawędzie). Intuicyjnie oznacza to, że grafy G i F są tym samym grafem, jedynie poddanym jakiejś permutacji wierzchołków.

Klasy grafów

Grafy można podzielić ze względu na różne własności, zazwyczaj zachowane w obrębie izomorfizmów danego grafu. Najczęściej dotyczą one tylko grafów prostych (nie zawierających pętli i krawędzi wielokrotnych), część z tych własności można rozszerzyć na multigrafy. Najczęściej spotykane klasy grafów to:

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.
Droga – wydzielony pas terenu składający się z jezdni, pobocza, chodnika, drogi dla pieszych lub drogi dla rowerów, łącznie z torowiskiem pojazdów szynowych znajdującym się w obrębie tego pasa. Przeznaczona do ruchu pojazdów, ruchu pieszych, jazdy wierzchem lub pędzenia zwierząt. (Kodeks Drogowy Art.2 ust.1)

graf prosty (właściwy)

Graf nie zawierający pętli ani krawędzi wielokrotnych. Graf nieprosty nazywany jest multigrafem. Z reguły zdanie G jest grafem oznacza w domyśle, że G jest grafem prostym

graf pełny

Graf, którego każdy wierzchołek jest połączony bezpośrednio krawędzią z każdym innym. Graf pełny o n wierzchołkach oznacza się $\! K_n$ .

graf regularny stopnia k

Graf, którego każdy wierzchołek jest stopnia k

graf kubiczny

Specjalne określenie dla grafów regularnych stopnia 3

graf acykliczny

Graf nie zawierający żadnej drogi zamkniętej

graf spójny

Graf, w którym dla każdego wierzchołka istnieje droga do każdego innego wierzchołka

graf k-spójny

Graf posiadający k spójnych składowych

drzewo

Spójny graf acykliczny

las

Graf, którego wszystkie spójne składowe są drzewami

graf dwudzielny

Graf, którego wierzchołki mogą być podzielone na dwa zbiory, tak by w obrębie jednego zbioru żaden wierzchołek nie był połączony z innym

graf dwudzielny pełny

Graf dwudzielny taki, że każdy wierzchołek z jednego zbioru jest połączony krawędzią z każdym wierzchołkam ze zbioru drugiego. Pełny graf dwudzielny o $\! n_1\ + n_2$ wierzchołkach oznacza się $\! K_{n_1,n_2}$

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ą

pełny graf k-dzielny

Jeżeli zbiór wierzchołków dzieli się na k nie połączonych między sobą podzbiorów wierzchołków, to jeżeli dla każdego wierzchołka $\! v_i$ z $\! j$ -tego przedziału $\! v_i$ jest połączony z każdym wierzchołkiem z każdego z przedziałów poza j, to jest to pełny graf k-dzielny

graf eulerowski

Graf posiadający drogę prostą przechodzą przez każdą krawędź.

graf hamiltonowski

Graf posiadający ścieżkę prostą przechodzą przez każdy wierzchołek.

graf planarny

Graf, dla którego istnieje graf izomorficzny, który można przedstawić na płaszczyźnie tak, by żadne krawędzie się nie przecinały (oczywiście, nie w sensie "spotkania się" w jednym wierzchołku). Kazimierz Kuratowski udowodnił, że grafy pełne $K_5$ i $K_{3,3}$ są nieplanarne, oraz że każdy inny graf nieplanarny musi posiadać podgraf homeomorficzny z którymś z tych grafów.

graf płaski

To izomorficzne przedstawienie grafu takie, że żadne dwie krawędzie się nie przecinają

graf platoński

Graf, którego przedstawienie tworzy siatkę wielościanu foremnego

graf komórkowy

Graf płaski, którego wszystkie ściany są utworzone przez drogi zamknięte tej samej długości

graf krytyczny

Graf, którego każdy wierzchołek/krawędź jest krytyczny/krytyczna

graf symetryczny

Graf skierowany taki, że jeżeli istnieje krawędź $\! (u,v)$ to istnieje też krawędź $\! (v,u)$ . Graf asymetryczny ma własność: jeżeli istnieje krawędź $\! (u,v)$ to nie istnieje krawędź $\! (v,u)$

graf podstawowy grafu skierowanego

To niemal ten sam, ale nieskierowany, bo bez zwrotów na krawędziach

turniej

To graf pełny, w którym zorientowano krawędzie, lub inaczej, graf skierowany którego graf podstawowy jest grafem pełnym

Wydawnictwa Naukowo-Techniczne (WNT) – polskie wydawnictwo założone w roku 1949 z siedzibą w Warszawie. Do roku 1961 funkcjonowało pod nazwą Państwowe Wydawnictwa Techniczne.
Populacja biologiczna — zespół organizmów jednego gatunku żyjących równocześnie w określonym środowisku i wzajemnie na siebie wpływających, zdolnych do wydawania płodnego potomstwa. Nie jest to jednak suma osobników jednego gatunku, a zupełnie nowa całość.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)