 | Pobierz cały dokument Lista 10 lista10 id 759712 Nieznany .pdf Rozmiar 187,5 KB |
zad.1
Na początek kilka definicji:
W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków,
oznaczanych przez V) wzajemnie połączonych za pomocą krawędzi (oznaczonych przez E).
Grafy dzielimy na grafy skierowane i nieskierowane:
Rys.1. Graf nieskierowany
Rys.2. Graf skierowany
Jeśli krawędź łączy dwa wierzchołki to jest z nimi incydentna.
Pętla własna to krawędź łączące wierzchołek z samym sobą.
Stopień wierzchołka w grafie nieskierowanym to liczba incydentnych z nim krawędzi.
Istnieje kilka algorytmów do przechowania grafu w pamięci.
a)
Omówmy najpierw macierz sąsiedztwa.
Budujemy tablicę o rozmiarach V*V, gdzie V-liczba wierzchołków. Następnie wypełniamy ją
zerami- jeśli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki są
połączone. Oto macierz sąsiedztwa dla grafu z rysunku 1:
1
2
3
4
5
1
0
1
1
0
1
2
1
0
1
1
1
3
1
1
0
1
0
4
0
1
1
0
1
| Pobierz cały dokument Lista 10 lista10 id 759712 Nieznany .pdf Rozmiar 187,5 KB |