Matematyka dyskretna 1/Ćwiczenia 12: Grafy

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Grafy I

1. Grafy oraz

Ćwiczenie 1

Niech oraz będą grafami przedstawionymi na rysunku 1. Przedstaw sumę , przecięcie , oraz różnicę .

Wskazówka
Rozwiązanie
 
4. Graf

Ćwiczenie 2

Graf jest przedstawiony na rysunku 4. Przedstaw graf ilorazowy dla relacji równoważności zdefiniowanej przez:

w.t.w. jest wielokrotnością

Wskazówka
Rozwiązanie

Ćwiczenie 3

Niech będzie grafem prostym z co najmniej dwoma wierzchołkami. Wykaż, że zawiera dwa wierzchołki tego samego stopnia.

Wskazówka
Rozwiązanie

Ćwiczenie 4

Wykaż, że w grupie sześciu osób zawsze znajdą się trzy, które albo znają się nawzajem, albo żadna z nich nie zna dwóch pozostałych.

Wskazówka
Rozwiązanie

Ćwiczenie 5

Dopełnienie grafu to graf . Przedstaw dopełnienie grafu pełnego oraz dwudzielnego grafu pełnego . Przedstaw graf, którego dopełnienie jest z nim izomorficzne.

Wskazówka
Rozwiązanie

Ćwiczenie 6

Niech będzie grafem prostym, w którym każdy wierzchołek ma co najmniej sąsiadów. Wykaż, że zawiera cykl o długości co najmniej .

Wskazówka
Rozwiązanie

Ćwiczenie 7

Niech będzie grafem prostym o wierzchołkach, niezawierającym trójkątów. Wykaż, że ma co najwyżej krawędzi i podaj przykład grafu, w którym to górne oszacowanie jest osiągnięte.

Wskazówka
Rozwiązanie
6. Graf Petersena

Ćwiczenie 8

Wskaż jakieś drzewo rozpinające w grafie Petersena z rysunku 6.

Wskazówka
Rozwiązanie

Prykładowe drzewo rozpinające w grafie Petersena zostało przedstawione na rysunku 7.

 

Ćwiczenie 9

Pokaż, że w dowolnym drzewie o co najmniej dwu wierzchołkach, istnieją co najmniej dwa wierzchołki o stopniu równym jeden.

Wskazówka
Rozwiązanie

Ćwiczenie 10

Centrum spójnego grafu to taki wierzchołek , dla którego maksymalna odległość pomiędzy i dowolnym innym wierzchołkiem grafu jest możliwie najmniejsza. Udowodnij, że każde drzewo ma albo dokładnie jedno centrum, albo dwa sąsiednie centra.

Wskazówka
Rozwiązanie