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 == Pokaż, że jeżeli graf rozpięty na parzystej liczbie wierzchołków ma więcej niż krawędzi, to zawiera doskonałe skojarzenie.

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 5

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

->