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 */
- 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ę */
- 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 */
- 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 */
- 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.