Zaawansowane algorytmy i struktury danych/Ćwiczenia 8

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Pokaż, że każdy graf może zostać zanurzony w grafie rozpiętym na co najwyżej wierzchołkach tak, aby dla każdego skojarzenia w istniało dokładnie jedno doskonałe skojarzenie takie, że . Czy jeżeli jest zewnętrznie planarny, to może być planarny?

Rozwiązanie


Zadanie 2

Dla grafu dwudzielnego , gdzie zdefiniujmy symboliczną macierz sąsiedztwa rozmiaru jako:

gdzie to różne zmienne przypisane krawędzią. Pokaż, że wtedy i tylko wtedy gdy ma doskonałe skojarzenie.

Rozwiązanie


Zadanie 3

Dla grafu zdefiniujmy symboliczną macierz sąsiedztwa rozmiaru jako:

gdzie to różne zmienne przypisane krawędzią. Pokaż, że wtedy i tylko wtedy gdy ma doskonałe skojarzenie.

Rozwiązanie

Zadanie 4

Załóżmy, że graf ma doskonałe skojarzenie. Powiemy, że krawędź jest niedozwolona jeżeli nie należy do żadnego doskonałego skojarzenia w . Pokaż jak w czasie znaleźć wszystkie niedozwolone krawędzie w grafie .

Rozwiązanie