Matematyka dyskretna 1/Ćwiczenia 12: Grafy: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m Zastępowanie tekstu – „<math> ” na „<math>”
m Zastępowanie tekstu – „ </math>” na „</math>”
Linia 39: Linia 39:


<center>
<center>
<math>v_i \triangleq v_j\quad</math> w.t.w. <math>\quad \left\vert i-j \right\vert\ </math> jest wielokrotnością <math>\ 4.
<math>v_i \triangleq v_j\quad</math> w.t.w. <math>\quad \left\vert i-j \right\vert\ </math> jest wielokrotnością <math>\ 4.
</math>
</math>
</center>
</center>

Wersja z 10:47, 5 wrz 2023

Grafy I

1. Grafy 𝐆1 oraz 𝐆2

Ćwiczenie 1

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

Wskazówka
Rozwiązanie
 
4. Graf 𝐆

Ćwiczenie 2

Graf 𝐆=(V,E) jest przedstawiony na rysunku 4. Przedstaw graf ilorazowy 𝐆/ dla relacji równoważności  V×V zdefiniowanej przez:

vivj w.t.w. |ij|  jest wielokrotnością  4.

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 𝐆=(V,E) to graf 𝐆=(V,𝒫2(V)E) . Przedstaw dopełnienie grafu pełnego 𝒦n oraz dwudzielnego grafu pełnego 𝒦m,n . 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 r2 sąsiadów. Wykaż, że 𝐆 zawiera cykl o długości co najmniej r+1 .

Wskazówka
Rozwiązanie

Ćwiczenie 7

Niech 𝐆 będzie grafem prostym o 2k wierzchołkach, niezawierającym trójkątów. Wykaż, że 𝐆 ma co najwyżej k2 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 v , dla którego maksymalna odległość pomiędzy v 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