Matematyka dyskretna 2/Ćwiczenia 1: Zagadnienia Mini-Maksowe w grafach

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zagadnienia Mini-Maksowe w grafach

1. Graf Petersena

Ćwiczenie 1

Czy graf Petersena przedstawiony na rysunku 1 ma skojarzenie doskonałe? Odpowiedź uzasadnij.

Rozwiązanie
 


Ćwiczenie 2

Kostka -wymiarowa to graf, którego wierzchołki są ciągami , gdzie , a krawędzie łączą te ciągi, które różnią się na jednej tylko pozycji. W kostce znajdź

  • maksymalne skojarzenie,
  • minimalne pokrycie krawędziowe,
  • minimalne pokrycie wierzchołkowe,
  • maksymalny zbiór niezależny,

i podaj ich liczności.

Wskazówka
Rozwiązanie
3. Drzewo

Ćwiczenie 3

Wskaż minimalne pokrycie krawędziowe drzewa z rysunku 3 oraz maksymalne skojarzenie zawarte w tym pokryciu.

Wskazówka
Rozwiązanie
 

Ćwiczenie 4

Pokaż, że w grafie prostym bez punktów izolowanych, maksymalne, w sensie inkluzji, skojarzenie jest najbardziej liczne wtedy i tylko wtedy, gdy jest zawarte w jakimś minimalnym pokryciu krawędziowym .

Wskazówka
Rozwiązanie

Ćwiczenie 5

Udowodnij, że w grafie prostym zachodzi:



Wskazówka
Rozwiązanie

Ćwiczenie 6

Udowodnij, że w grafie dwudzielnym bez wierzchołków izolowanych zachodzi .

Wskazówka
Rozwiązanie