Algorytmy grafowe

0

Jakby komuś się nudziło to tutaj kilka zadanek z Matematyki Dyskretnej (jutro mam egzamin z tego). Za wszystkie odpowiedzi dziękuję (ale tylko te na temat ;) ).

W zadaniach poniżej, o ile nie jest przyjęta inna reprezenacja danych, przyjmujemy, że dane wejściowe o grafie G = , V = {1..n} zawiera tablica G[1..n, 1..n] o wartościach 0, 1 taka, że G[u, v] = 1 in E
/* Jakby ktoś nie wiedział, to jest to taka macierz sąsiedztwa */

  1. Graf G = , V = {1..n} jest niezorientowany. Zaproponować algorytm, sprawdzajacy, czy G zawiera wierzchołki rzędu nieparzystego i ewentualnie podać ich liczbę /* to prościutkie na rozgrzewkę */
  2. Graf G = , V = {1..n} jest niezorientowany. Co można powiedzieć o grafie G, jeżeli posiada on dokładnie dwa różne drzewa rozpinające o korzeniu v0 in E? /* Nad tym jeszcze nie myślałem */
  3. Graf G = , V = {1..n} jest niezorientowany. Zaproponować algorytm, podający maksymalną liczbę wierzchołków w grafie G, posiadajacych ten sam rząd. /* To też dosyć proste */
  4. W zorientowanym grafie G = , V = {1..n}, rząd r(v) wierzchołka definioujemy jako parę liczb: r(v) = gdzie
  • z(v) - liczba krawędzi wychodzących z wierzchołka v
  • d(v) - liczba krawędzi dochodzących do wierzchołka v
    Zaproponować algorytm sprawdzający, czy w danym grafie G można znaleźć dwa różne wierzchołki u, v takie, że r(u) = r(v)

W zadaniach poniżej, o ile nie jest przyjęta inna reprezenacja danyc, przyjmujemy, że dane wejściowe o grafie G = z funkcją wag a: E -> R, zawiera tablica A[1..n, 1..n] o wartościach ze zbioru liczb rzeczywistych R taka, że A[u, v] = a()
5. W zorientowanym grafie G = , V = {1..n}, z funkcją wag a: E -> R, zbirór wartości wag {a(e): e in E} jest podzbiorem zbioru {1, 2, 4, 5, 16,...} kolejnych potęg naturalnych liczby 2. Pokazać, że dla dowolnych wierzchołków u, v nie istnieją dwie różne drogi z u do v o minimalnej sumie wag.
6. Dany jest zorientowany graf G = , V = {1..n}, z funkcją wag a: E -> R. Zaproponować algorytm sprawdzający, czy dla dowolnych wierzchołków u, v każde dwie różne drogi z u do v mają rózną długość.
7. Dany jest zorientowany graf G = , V = {1..n}, z funkcją wag a: E -> R. Zaproponować algorytm sprawdzający, czy graf G ma cykle o ujemnej sumie wag.
Dany jest zorientowany graf G = , V = {1..n}, z funkcją wag a: E -> R. Wiedząc, że graf G nie posiada cykli, zaproponować algorytm znajdujący dla dowolnych wierzchołków u, v in V drogę o maksymalnej sumie wag.
8. Dany jest zorientowany graf G = , V = {1..n}, z funkcją wag a: E -> R. Zaproponować algorytm znajdujący dla dowolnych wierzchołków u, v in V drogę z u do v nie zawierającą cykli o maksymalnej sumie wag.
9. Dany jest niezorientowany graf G = , nie zawierający cykli, o dodatnich wagach. Zaproponować algorytm, o możliwie najmniejszej złożoności, znajdujący w grafie G maksymalne odległości między dowolnymi parami wierzchołków. Uzasadnić poprawność algorytmu.
10. Dany jest niezorientowany graf G = , o dodatnich wagach. Zaproponować algorytm o możliwie najmniejszej złożoności, znajdujący takie wierzchołki u, v in V, dla których długość minimalnej drogi łączącej u i v jest możliwie najmniejsza (minimalna). Uzasadnić poprawność algorytmu.

0

to przeciez bardzo latwe ;] [;

Wynik należy do R =] :P
bo urojonych chyba tu nie ma ;P :D [diabel] [diabel] :d ;p [cygaro] [browar] [angel]

0

Eh... Zaczynam w was wątpić (no może tylko okres wakacji was usprawiedliwia). A MD i tak do przodu mam :P

0

Tak na pierwszy rzut oka to w pytaniu nr 10 chodzi o algorytm Djikstry znajdowania najkrótszych scieżek z jednym źródłym, przy zaimplementowaniu kolajki prorytetoej na zasadach kopca ma on bardzo dobrą złożoność. Wydaje mi się że kilka powyższych zagadanień da się rozwiać modyfikując ten algorytm.

0

Chyba jendak nie wystarczjąco się wczytałem. Poszukiwane wierzchołki to wierzchołki połączone najkrótszą krawędzią grafu, czyli mozna się obyć bez Dijkstry :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1