1. Zaproponuj algorytm kolorowania dowolnego drzewa minimalną liczbą kolorów. Oszacuj jego koszt.
    
2. Zaproponuj algorytm kolorowania dowolnego grafu, polegający na wyborze pierwszego dopuszczalnego koloru dla każdego wierzchołka. Jaki jest jego koszt?
    
3. Przypuśćmy, że złodziej znajduje w sejfie n obiektów różnego rozmiaru i wartości, ale ma do dyspozycji tylko plecak o rozmiarze r, który może wypełnić zdobyczą. Załóżmy, że obiektów każdego z n typów jest w sejfie dowolnie dużo. Problem polega na dokonaniu wyboru takiej kombinacji obiektów, aby zmieściły się one w plecaku i by całkowita wartość wszystkich obiektów w plecaku była największa z możliwych. Zaproponuj rozwiązanie tej wersji problemu plecakowego metodą programowania dynamicznego.
    
4. Problem pakowania. Załóżmy, że mamy dany zbiór n obiektów o rozmiarze  s_i, przy czym 0 < s_i < 1. Obiekty te chcemy zapakować do skrzyń, z których każda może pomieścić dowolny zbiór obiektów o łącznym rozmiarze nieprzekraczającym 1.  Udowodnij, że problem wyznaczenia minimalnej liczba skrzyń potrzebnych do zapakowania wszystkich obiektów jest  NP-trudny.
    
5. Przedstawić metodę konstrukcji drogi przechodzącej przez wszystkie wierzchołki danego grafu niezorientowanego, na podstawie danego minimalnego drzewa rozpinającego tego grafu. Udowodnić, że tak zbudowana droga komiwojażera  jest co najwyżej dwa razy dłuższa, niż minimalna droga komiwojażera w tym grafie.

 

« poprzedni punkt