graf

graf

[gr.],

mat. obiekt G = (V, E), składający się z niepustego zbioru wierzchołków V oraz zbioru połączeń między nimi (krawędzi) E, będącego zbiorem 2-elementowych podzbiorów V.

Graf można przedstawić graficznie przyporządkowując wierzchołkom punkty i łącząc je liniami odpowiadającymi krawędziom; każdy graf skończony (o skończonej liczbie wierzchołków i krawędzi) można przedstawić w przestrzeni trójwymiarowej w taki sposób, że linie odpowiadające krawędziom nie przecinają się w punktach wewnętrznych. Do najważniejszych pojęć związanych z grafem należą: podgraf — niepusty podzbiór V₁ zbioru V i podzbiór E₁ zbioru E, taki że jeśli (x, y) ∈ E₁, to x, y ∈ V₁; droga — ciąg wierzchołków, z których każde 2 kolejne są połączone krawędzią; cykl — droga zaczynająca i kończąca się w tym samym wierzchołku; odległość d(x, y) między wierzchołkami x, y — długość najkrótszej drogi o początku x i końcu y (d(x, y) = ∞, jeśli nie ma żadnej takiej drogi). Graf nazywa się grafem zorientowanym, gdy każdej krawędzi jest przyporządkowany zwrot (inaczej: E jest zbiorem par uporządkowanych). Graf niezorientowany nazywa się grafem spójnym, jeśli dowolne 2 wierzchołki łączy pewna droga; graf zorientowany jest spójny, jeśli spójny jest graf otrzymany z niego przez zastąpienie każdej krawędzi zorientowanej przez krawędź niezorientowaną. Graf spójny niezorientowany i nie zawierający cykli nazywa się drzewem. Grafy można określać na różne sposoby — opisowo, graficznie, a także przez tzw. macierz sąsiedztwa wierzchołków: dla wierzchołków w₁, w₂, ... , w_n grafu skończonego jest to macierz kwadratowa, elementy której a_ij (i, j = 1, 2, ... , n) są równe liczbie krawędzi wychodzących z wierzchołka w_i do wierzchołka w_j. Własności grafów bada teoria grafów.

Bibliografia

N. DEO Teoria grafów i jej zastosowania w technice i informatyce, Warszawa 1980;

R.J. WILSON Wprowadzenie do teorii grafów, Warszawa 1985.

Grafów teoria. Plan mostów królewieckich (ilustracja zamieszczona w artykule L. Eulera) i odpowiadający mu graf; zadanie postawione przez L. Eulera: czy można tak zaplanować spacer po Królewcu, by przejść po każdym z mostów na rzece dokładnie raz i powrócić do miejsca, z którego się wyszło?