28211 zadanie z struktury system inf / algorytmy grafowe

zadanie z: optymalizacja na sieciach dane: tabele wag krawedzi siec podesle zwyciezcy tresc: 1. traktujac wartosci podane w tablicy jak długosci krawedzi w sieci a) skierowanej; b) nieskierowanej okreslic najkrótsze drogi miedzy kazda para wierzchołków. uwaga! nalezy wyznaczyc drogi (tzn. ciagi kolejnych wierzchołków) oraz ich długosci. 2. traktujac wartosci podane w tablicy jak długosci krawedzi w sieci skierowanej okreslic najdłuzsze drogi miedzy kazda para wierzchołków. Uwaga, jak wyzej. 3. traktujac wartosci podane w tablicy jak długosci krawedzi w sieci nieskierowanej wyznaczyc minimalne drzewo rozpinajace (MST, ang. Minimal Spinning Tree) dla sieci. 4. przez przepustowosc drogi rozumiemy minimalna wage krawedzi tej drogi. w grafie skierowanym zdefiniowanym powyzej wyznaczyc maksymalne przepustowosci dróg miedzy wszystkimi parami wierzchołków. nalezy w kazdym przypadku wskazac droge (ciag wierzchołków) oraz jej przepustowosc. 5. przyjmujac, ze wartosci w tablicy reprezentuja przepustowosci krawedzi okreslic maksymalny przepływ (maxflow) w sieci od wierzchołka 1 do wierzchołka 10. rozpatrzyc dwa przypadki: a) siec jest skierowana (przepływ mozliwy jest tylko od wierzchołka o mniejszym numerze do wierzchołka o wiekszym numerze), b) siec jest nieskierowana (przyjac jednakowa przepustowosc dla obu kierunków kaz- dej krawedzi). 6. wyznaczyc krawedz (jesli istnieje) o tej własnosci, ze zwiekszenie o jednostke jej przepustowosci powoduje zwiekszenie wartosci maksymalnego przepływu. Znalezc wszystkie krawedzie o tej własnosci. 7. wyznaczyc krawedzie o tej własnosci, ze zmniejszenie o jednostke przepustowosci którejkolwiek z nich nie powoduje zmniejszenia wartosci maksymalnego przepływu. do jakiej wartosci mozna zmniejszac przepustowosci tych krawedzi? czy mozna równoczesnie zmniejszac przepustowosc wszystkich tych krawedzi bez zmniejszenia maksymalnego przepływu? 8. wyznaczyc krawedzie (jesli istnieja) o tej własnosci, ze ich usuniecie nie powoduje zmniejszenia wartosci maksymalnego przepływu. czy mozna usunac je równoczesnie? W zadaniach 6 – 8 przyjmujemy, ze siec jest skierowana. prosze o podanie przyblizonej ceny, czasu realizacji oraz danych kontaktowych