9988996107

Zadanie 32

Dany jest plik, w liniach którego są różne pary liczb całkowitych z przedziału 1 do n. Napisać procedurę, która tworzy graf o n wierzchołkach reprezentowany jako listy incydencji taki, że pary z pliku to krawędzie tego grafu. W wersji niezorientowanej listy powinny być dwukierunkowe z wartownikiem i obie reprezentacje tej samej krawędzi powinny mieć wskaźniki do siebie na wzajem.

Zadanie 33

Napisać procedurę w języku Pascal, która dla danego grafu zorientowanego G — (V, E) reprezentowanego jako listy incydencji, oblicza graf transponowany G^T = (V, E^T), gdzie E^T = {(v, u) : {u,v) G E}.

Zadanie 34

Napisać procedurę w języku Pascal, która dla danego grafu zorientowanego G = (V, E) reprezentowanego jako listy incydencji, który jest drzewem oblicza jego wysokość G.

Zadanie 35

Napisać procedurę, która sprawdza czy dany graf niezorientowany jest spójny.

Zadanie 36

Napisać procedurę, która sprawdza czy dany graf niezorientowany jest acykliczny.

Zadanie 37

W tablicy A znajduje się permutacja liczb od 1 do n. Napisać procedurę w języku Pascal, która sprawdza czy permutacja z tablicy A reprezentuje cykl Hamiltona w grafie Gon wierzchołkach reprezentowanym przez listy incydencji.

Cykl w grafie G jest cyklem Hamiltona jeśli przechodzi przez każdy wierzchołek dokładnie jeden raz.

Zadanie 38

Napisać procedurę w języku Pascal, która sprawdza czy dany graf skierowany reprezentowany przez listy incydencji jest acykliczny.

Zadanie 39

Napisać procedurę w języku Pascal, która sprawdza czy na liście o głowie h znajdują się wierzchołki cyklu Eulera grafu skierowanego Gon wierzchołkach.

20