« poprzedni punkt   następny punkt »
 

Ćwiczenia do wykładu 03
  1. Udowodnić, że relacja  r, określona na wierzchołkach pewnego grafu niezorientowanego G = (V,E) następująco,  v r v'  wttw v = v' lub istnieją wierzchołki v1, v2,...,vk takie, że v1=v i vk = v' oraz (vi,vi+1) ∈ E, jest relają zwrotną, symetryczną i przechodnią.

  2. Drzewo binarne nazywamy lokalnie pełnym, jeśli każdy jego wierzchołek wewnętrzny ma dwa następniki. Udowodnić, że drzewo binarne, lokalnie pełne,  o m wierzchołkach wewnętrznych ma dokładnie m+1 liści.

  3. Udowodnić, że każdy skończony graf, w którym każdy wierzchołek ma stopień co najmniej 2, zawiera cykl.

  4. Udowodnić, że każdy graf prosty o co najmniej dwóch wierzchołkach ma dwa wierzchołki tego samego rzędu.

  5. Na brzegu rzeki znajdują się trzej misjonarze i trzej kanibale. Dysponują tylko jedną łódką, która może  pomieścić co najwyżej dwie osoby. Jak zorganizować przeprawę przez rzekę tak, by na żadnym jej brzegu liczba kanibali nie przekraczała liczby misjonarzy (łódka nie może wracać pusta)?  Narysuj graf wszystkich możliwych sytuacji i wskaż drogę opisującą przeprawę przez rzekę zgodnie z wymaganiami.

  6. Udowodnij, że  graf niezorientowany  jest drzewem  wtedy i tylko wtedy, gdy dowone dwa różne wierzchołki są połączone dokładnie jedną drogą, której wszystkie wierzchołki są różne.

  7. Udowodnić, że każda droga zamknięta o długości co najmniej 3, której wierzchołki nie powtarzają się, tworzy cykl.
     
  8. Niech G* będzie grafem, którego zbiorem wierzchołków są krawędzie danego grafu niezorientowanego G, natomiast krawędzie łączą tylko te wierzchołki w grafie G*, które odpowiadają krawędziom incydentnym w grafie G.  Graf G* nazywamy grafem dualym grafu  G. Udowodnić, że
« poprzedni punkt   następny punkt »