graf
 
Encyklopedia PWN
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 V1 zbioru V i podzbiór E1 zbioru E, taki że jeśli (x, y) ∈ E1, to x, yV1; 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 w1, w2, ... , wn grafu skończonego jest to macierz kwadratowa, elementy której aij (i, j = 1, 2, ... , n) są równe liczbie krawędzi wychodzących z wierzchołka wi do wierzchołka wj. 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.
Ilustracje
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?wyk. LogoScript/Archiwum Ilustracji WN PWN SA © Wydawnictwo Naukowe PWN
Przeglądaj encyklopedię
Przeglądaj tabele i zestawienia
Przeglądaj ilustracje i multimedia