Matematyka dyskretna – dr Marcin Raniszewski 

 

Matematyka Dyskretna – ćw. 12 

Teoria grafów 

Drzewa, drzewa spinające, drogi i cykle Hamiltona, grafy dwudzielne 

 

Drzewem 

  nazywamy każdy graf spójny i acykliczny. Z acykliczności wynika brak krawędzi wielokrotnych 

i pętli w każdym drzewie. 

Liśćmi w drzewie nazywamy wierzchołki stopnia 1. 

Drzewo binarne to drzewo, w którym występują wierzchołki co najwyżej 3 stopnia. 

Ukorzenione  drzewo  binarne  to  drzewo  binarne,  w  którym  został  wyróżniony  jeden  wierzchołek  stopnia  2 
(zwany korzeniem). 

Drzewo  regularne  to  ukorzenione  drzewo  binarne,  w  którym  wszystkie  wierzchołki  (oprócz  korzenia)  mają 
stopień 3 lub 1. 

Zad.  1.  Narysuj  wszystkie  drzewa  mające  siedem  wierzchołków  z  dokładnością  do 
izomorfizmu. Które z nich są drzewami binarnymi? Które z nich są drzewami regularnymi? 

Drzewem  spinającym 

   grafu     nazywamy  taki  podgraf  grafu   ,  który  jest  drzewem  zawierającym  każdy 

wierzchołek grafu 

 , czyli            . 

Każdy graf spójny ma drzewo spinające. 

Graf 

 

 

 ma 

 

   

 drzew spinających. 

Zad. 2. Podaj liczbę drzew spinających dla grafów przedstawionych na rysunkach: 

 

Zad. 3. Ile drzew spinających ma graf 

 

 

? Narysuj je wszystkie. 

Matematyka dyskretna – dr Marcin Raniszewski 

 

Drzewo mające 

  wierzchołków ma dokładnie       krawędzi. 

Zad.  4.  Pewne  drzewo  ma  dwa  wierzchołki  stopnia  4,  jeden  wierzchołek  stopnia  3  i  jeden 
wierzchołek stopnia 2. Jeśli pozostałe wierzchołki to liście, to ile wierzchołków  jest  w tym 
grafie? 

Drogę nazywamy drogą Hamiltona, jeśli przechodzi przez każdy wierzchołek grafu dokładnie jeden raz. 

Drogę zamkniętą, która przechodzi przez każdy wierzchołek grafu dokładnie jeden raz, z wyjątkiem ostatniego 
wierzchołka, którym ponownie jest pierwszy wierzchołek, nazywamy cyklem Hamiltona. 

Graf mający cykl Hamiltona nazywamy grafem hamiltonowskim. 

Graf 

  nazywamy grafem dwudzielnym, jeśli zbiór      jest sumą dwóch niepustych zbiorów rozłącznych  

 

 

i 

 

 

 takich, że każda krawędź w grafie 

  łączy wierzchołek ze zbioru  

 

 z wierzchołkiem ze zbioru 

 

 

. Graf 

  

nazywamy  pełnym grafem dwudzielnym, jeśli ponadto każdy wierzchołek zbioru 

 

 

 jest połączony z każdym 

wierzchołkiem zbioru 

 

 

 dokładnie jedną krawędzią. 

Symbolem 

 

   

 oznaczamy pełny graf dwudzielny, w którym  

 

 

      i   

 

     . 

Załóżmy, że 

         . Wtedy: 



 

graf 

 

   

 ma cykl Hamiltona 

        



 

graf 

 

   

 ma drogę Hamiltona 

              

Zad. 5. Narysuj: 

(a)  graf dwudzielny o sześciu wierzchołkach, który nie jest grafem pełnym dwudzielnym, 

(b) graf 

 

   

, 

(c)  graf o sześciu wierzchołkach, który nie jest dwudzielny. 

Zad. 6. Narysuj: 

(a)  graf dwudzielny o sześciu wierzchołkach, który nie ma drogi Hamiltona, 
(b) graf  dwudzielny  o  siedmiu  wierzchołkach,  który  ma  drogę  Hamiltona,  ale  nie  ma 

cyklu Hamiltona, 

(c)  graf dwudzielny o sześciu wierzchołkach, który ma cykl Hamiltona. 

W podpunktach (b) i (c) wyznacz odpowiednio jedną drogę i jeden cykl Hamiltona.