Graf nieskierowany
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Graf nieskierowany – jeden z rodzajów grafów rozpatrywanych w teorii grafów. Graf nieskierowany można sobie wyobrazić jako sieć połączonych krawędziami wierzchołków. Droga potrzebna do pokonania krawędzi nie zależy w grafie nieskierowanym od kierunku ruchu. Jeżeli z pierwszego wierzchołka można się dostać do drugiego to, tą samą drogą można dotrzeć z powrotem.
W matematyce graf nieskierowany definiuje się w oparciu o pojęcie zbioru. Graf nieskierowany G to uporządkowana para G := (V, E) która podlega następującym warunkom:
- V to zbiór wierzchołków,
- E jest zbiorem nieuporządkowanych par wierzchołków, nazywanych krawędziami
- Wierzchołki należące do krawędzi nazywane są jej końcami.
Moc zbioru V nazywamy rzędem grafu G i oznaczamy przez |V|, a moc zbioru E nazywamy jego rozmiarem i oznaczamy przez ||G||. Zwykle zakłada się, że zbiory V oraz E są skończone. Większość twierdzeń teorii grafów poprawnych dla skończonej ilości krawędzi i wierzchołków okazuje się nieprawdziwa dla grafów nieskończonych.
Przykład grafu wraz z jego ilustracją:
- V := { 1, 2, 3, 4, 5, 6 }
- E := { {1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6} }
