1.definicja "dag"
2. definicja cięciwy powrotnej (i chyba inne z tego slajdu też się pojawiły)
3. definicja listy sąsiedztwa
4. definicja macierzy sąsiedztwa
5. narysować przykład grafu o 4 wierzchołkach, dla którego algorytmy bfs i dfs zadziałają tak samo
6. ile razy zmieniony przypisany zostanie atrybut "color" w algorytmie bfs dla n wierzchołków i m krawędzi.
7. masz podane d(u) i f(u) dla kilku wierzchołków. narysuj graf.

wybrane polecenia, j.w.
(w sumie nie wiem jak, ale 3 znalazły się w moich rękach, szkoda że nie mam aparatu):

4. Wygenerować N=50 grafów skierowanych o n wierzchołkach i m=0.7*n*n krawędziach za pomocą funkcji graphgen. Przyjąć 1 za wierzchołek źródłowy. Przeszukać te grafy algorytmem bfs_ms. Zbadać w funkcji n od 1 do 100: a) złożoność oczekiwaną przeszukiwania osiągniętego podgrafu (operacja dominująca - operacje na kolejce); b) wartość oczekiwana liczby przetworzonych wierzchołków. Sporządzić 2 wykresy. Wyjaśnić ich przebieg w oparciu o teorię. Czy złożoność zależy od charaktery danych? Wnioski.

8. Wygenerować N=50 grafów skierowanych o n wierzchołkach i m=floor(0.7*n*n) krawędziach za pomocą funkcji graphgen. Przyjąć 1 za wierzchołek źródłowy. Przeszukać te grafy algorytmem dfs_ms. Zmodyfikować algorytm dfs)ms tak, by wykonywał jednokrotny start z wierzchołka źródłowego. Zbadać w funkcji n od 1 do 100: a) złożoność oczekiwaną (operacja dominująca - przypisanie); b) wartość oczekiwana największej wartości atrybutu f wierzchołków osiągniętą w tym algorytmie. Sporządzić 2 wykresy. Wyjaśnić ich przebieg w oparciu o teorię. Czy złożoność zależy od charaktery danych? Wnioski.

12. Wygenerować N=50 grafów skierowanych o n wierzchołkach i m=floor(0.7*n*n) krawędziach za pomocą funkcji graphgen. Przyjąć 1 za wierzchołek źródłowy. Przeszukać te grafy algorytmem dfs_ms. Zbadać w funkcji n od 1 do 100: a) złożoność oczekiwaną (operacja dominująca - przypisanie); b) wartość oczekiwana liczby cięciw w przód. Sporządzić 2 wykresy. Wyjaśnić ich przebieg w oparciu o teorię. Czy złożoność zależy od charaktery danych? Wnioski.

spostrzeżenia/refleksje własne:

wejściówka jak zwykle, czyli jakaś definicja i coś na znajomość algorytmów. polecenia na laborkę mocno zagmatwane, ale po kilkukrotnym przeczytaniu oraz przejrzeniu kodu imo wstawienie liczników jest proste. z istotnych rzeczy:
- na labce korzysta się z funkcji graphgen, której działanie jest opisane w komentarzu w jej kodzie, i generalnie nie ma z nią problemów: dostaje na wejście liczbę wierzchołków, liczbę krawędzi, typ grafu i zarodek dla liczb pseudolosowych, wypluwa tablicę sąsiedztwa oraz macierz sąsiedztwa;
- wysoce przesadzona jest ilość danych do określania wartości oczekiwanych; zdecydowanie polecam sprawdzenie działania algorytmu dla np. N=5 i n od 1 do 20, a wywołanie dla wymaganych N=50 i n od 1 do 100 zostawić sobie na koniec. mnie matlab mulił się ponad 5 minut nim wypluł wykresy, niektórym jeszcze dłużej;
- w wykładach nie ma zwykle prostych wzorów na wartości oczekiwane, więc tym razem tworzenie wniosków jest dość twórcze, bo trzeba przedstawić jakieś argumenty, czemu złożoność wyszła taka, a nie inna; w tym zakresie labka dość wymagająca;

Co do hintów, to warto zakomentować w kodzie niepotrzebne rzeczy takie jak wydruki na ekran w przeszukiwaniu i zabawy z listą w generowaniu grafów (potrzebny jest chyba tylko macierzak) - znacznie skraca to czas mielenia.

Ja miałem def. grafu skierowanego i pytanie w stylu 10 wierzchołków, 100 krawędzi - ile średnio pól będzie mieć lista sąsiedztwa (odp. chyba 10)

Cytat:

6. ile razy zmieniony przypisany zostanie atrybut "color" w algorytmie bfs dla n wierzchołków i m krawędzi.

IGI napisał:

A co maja do tego krawedzie?

To raczej tylko dla zmyły. W końcu zadny wierzcholek zmienia kolor 2 razy wiec ogolna zmiana =liczba wierzchołków * 2

różnica między algorytmami *_tss a *_ms jest taka, że pierwsze operują na tablicach sąsiedztwa, a drugie na macierzach sąsiedztwa. tablice sąsiedztwa zapisywane są w macierzy adj, a macierz sąsiedztwa w t_adj. funkcja graphgen zwraca obie macierze. ponieważ dla danego typu algorytmu potrzebujesz tylko jednej, to wywalasz z graphgen niepotrzebną, przy okazji przyspieszając działanie programu.

8. Wygenerować N=50 grafów skierowanych o n wierzchołkach i m=floor(0.7*n*n) krawędziach za pomocą funkcji graphgen. Przyjąć 1 za wierzchołek źródłowy. Przeszukać te grafy algorytmem dfs_ms. Zmodyfikować algorytm dfs)ms tak, by wykonywał jednokrotny start z wierzchołka źródłowego. Zbadać w funkcji n od 1 do 100: a) złożoność oczekiwaną (operacja dominująca - przypisanie); b) wartość oczekiwana największej wartości atrybutu f wierzchołków osiągniętą w tym algorytmie. Sporządzić 2 wykresy. Wyjaśnić ich przebieg w oparciu o teorię. Czy złożoność zależy od charaktery danych? Wnioski.

nie obiecuję że poprawny, ale imo trzeba wywalić ostatnią pętlę i zamiast niej wstawić pojedyncze wywołanie dfsvisit dla pierwszego wierzchołka. po zmianach algorytm wygląda następująco:

Kod:

function dfs_ms(t_adj) global color predecessor d f time for u=1:size(t_adj,2)    color(u)=0; predecessor(u)=0; end time=0; dfsvisit_ms(1,t_adj);

sprawdziłem, wydaje się działać poprawnie.

Cytat:

Przyłączam się do pytanie które pojawiło sie wcześniej: jak z tą liczbą cięciw w przód ? Cóż takiego należy zliczać ? Smile

Jest graf na którym chodzi DFS. Algorytm jak się przesuwa po wierzchołkach to tworzy drzewo przeszukiwania wgłąb - droga po której idzie algorytm. I teraz, jeśli jakaś krawędź (a,b) istnieje i nie należy do tego drzewa to może być którąś cięciwą.

a) Jeśli: przedział [ d(a) , f(a) ] zawiera się w [ d(b) , f(b) ] to jest cięciwą powrotną (w tył). To jest tożsame z występowaniem cyklu w grafie. Ilość cykli = ilość cięciw powrotnych.
b) Jeśli: przedział [ d(b) , f(b) ] zawiera się w [ d(a) , f(a) ] to jest cięciwą.
c) Jeśli: przedział [ d(a) , f(a) ] jest rozłączny z [ d(b) , f(b) ] to jest cięciwą zwykłą.

Cytat:

A moje własne to: jak zliczać tą wartość f(u) ?

Każde kolorowanie w DFS to jedna jednostka czasu. Przy każdym wierzchołku wpisujesz d=czas odwiedzin oraz f=czas przetworzenia.
W praktyce: dochodzisz do białego wierzchołka to kolorujesz go na szaro, zwiększasz czas i wpisujesz d=czas. Jeśli nie możesz iść dalej to szary zmieniasz na czarny, zwiększasz czas i wpisujesz f=czas.

[EDIT]
Przepraszam niewtajemniczonych za bałagan na forum - poniżej, na potrzeby dzisiejszej laborki
,wrzuciłem kod skryptu cieciwy.m realizującego funkcję o tym samym tytule. Prawdopodobnie nie jest to najlepsze rozwiązanie tego problemu (nijak nie zoptymalizowane), ale chyba działa. Upewnię się, jak już coś zjem/zdam sesję. Nie chce kasować, bo to brzydko wycofywać się z tego, co się zamieściło na elce. Nawet jeśli chodzi o sygnaturki

[koniec edita]

Kod:

napredce, pliki start.m oraz cieciwy.m %cieciwy.m function t = cieciwy(adj,d,f,predecessor) for u = 1:size(adj,2)     for v = 1:size(adj(u).sasiedzi,2)         if(predecessor(adj(u).sasiedzi(v)) ~= u)             if((d(u) > d(adj(u).sasiedzi(v))) & (f(u) < f(adj(u).sasiedzi(v))))                 %display(['Cieciwa powrotna jest ',int2str(u),',',int2str(adj(u).sasiedzi(v))]);                 t = 1;                 return             end            end        end    end    t = 0; % koniec cieciw.m %start.m %start.m clear all; global color predecessor d f time; n = 5; W = zeros(1,10); m = round(0.8 * n * n); %losowanie DAG, poki co dla n = 5 wierzch, co by szybciej while(1)     [adj,t_adj] = graphgen(n,m,1,-2);     dfs_tss(adj);     predecessor;     d;     f;     %kod cieciwy zmieszczam niedaleko     a = cieciwy(adj,d,f,predecessor);     if(a == 0)         break;     end end %wypisanie tablicy adj, potwornie protsacko, ale czas nagli for i= 1:size(adj,2)     adj(i).sasiedzi end    W = dfsw_tss(adj); %wypisanie W W %a tutaj miejsce na losowanie dla n = 30 (i 10)

Cytat:

2) masz graf nieskierowany 10 wierzchołków i 40 krawędzi i robisz listę sąsiedztwa. Jaka będzie średnia ilość pól w tablicy (odpowiedź to 8 bo 2 razy 40 bo nieskierowane powtarza krawędzie przez 10)

yacekm napisał:

co??? nie rozumiem. jak liczyc tego typu rzeczy?

Jak jest graf nieskierowany który ma 10 wierzchołków, to jego lista sąsiedztwa składa się z 10 elementów-list(dla każdego wierzchołka). Wiadomo, że cały graf ma 40 krawędzi. Dla listy nieskierowanej, tworząc listę sąsiedztwa każdą krawędź zaznacza się dwukrotnie: w liście wierzchołka A wpisując że prowadzi do B i na odwrót. Więc w całej liście będzie 2*40=80wpisów, czyli dla jednego wierzchołka jest ich średnio 8.

od pana dr sochonia
1)zbadaj zlozonos obliczniowa oczekiwana algorytmu dfs_tss w funkcji liczby krawędzi m grafu nieskierowanego, przyjmujac liczebe wierzcholkow n=12. Rozwaz wartosci m od 1 do mmax. jako operacje dominujace przyjmj porownanie oraz podstawienie wartosci atrybutu color(przedstaw na wspolnym wykresie zlozonosc sumaryczna i zlozonosci skladow) wnioski
2)zbadaj zlozonos obliczneiowa oczekiwana algorytmu bfs_tss w funkcji liczby wierzcholkow n grafu skierowanego dla wspolczynnika gestosci grafu pi=0,2
rozwaz wartosc n od 2 do 25. jako operacje dominujace przyjmij porownanie oraz podstawienir wartosci atrybutu color (przedstaw na wspolnym wykresie zlozonosc sumaryczna i zlozonosci skladowe)
na tym samym wykresie przedstaw zlozonosc obliczeniowa otrzyman dla grafu pelnego. Wnioski

Dana była macierz - na jej podstawie narysowac graf i okresli jego skierowanie,cyklicznosc, spojnosc i gestosc.

Na szczęście do nas (3T3) przyszła odpowiednia osoba, czyli Sochoń :)

Wejściówka - standard z macierzą sąsiedztwa, to samo o czym pisał wyżej dwie_szopy.

---