Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

1 

 

 

Drzewem     nazywamy  każdy  graf  spójny 
i acykliczny. 

Z 

acykliczności 

wynika 

brak 

krawędzi 

wielokrotnych i pętli w każdym drzewie. 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

2 

 

 

Wierzchołki  stopnia  1  w  drzewie  nazywamy 
liśćmi. 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

3 

 

 

Jeśli graf   jest drzewem, to: 



 

 każde dwa wierzchołki grafu   połączone są 
dokładnie jedną drogą prostą 



 

 graf     przestaje  być  spójny  po  usunięciu 
dowolnej krawędzi 



 

 graf     przestaje  być  acykliczny  po  dodaniu 
jakiejkolwiek krawędzi 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

4 

 

 

Drzewo  mające     wierzchołków  ma  dokładnie 
      krawędzi. 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

5 

 

 

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). 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

6 

 

 

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

 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

7 

 

 

Drzewem spinającym (rozpinającym)   grafu   
nazywamy podgraf grafu  , który jest drzewem 
i  zawiera  każdy  wierzchołek  grafu   ,  czyli 
           . 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

8 

 

 

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

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

9 

 

 

Graf  

 

 ma  

   

 drzew spinających. 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

10 

 

 

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

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

11 

 

 

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. 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

12 

 

 

Graf  mający  cykl  Hamiltona  nazywamy  grafem 
hamiltonowskim. 

Graf  hamiltonowski  po  dodaniu  nowych 
krawędzi 

nie 

przestaje 

być 

grafem 

hamiltonowskim. 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

13 

 

 

Każdy graf  

 

 dla       jest hamiltonowski. 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

14 

 

 

Graf  prosty     o  co  najmniej  trzech 
wierzchołkach jest hamiltonowski, jeśli: 

           

      

 

      

 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

15 

 

 

Graf prosty   jest hamiltonowski jeśli: 

        

 
 

                             

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

16 

 

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   

 

.  Jeśli  ponadto 

każdy  wierzchołek  zbioru   

 

  jest  połączony 

z każdym  wierzchołkiem  zbioru   

 

  dokładnie 

jedną  krawędzią,  to  graf     nazywamy  pełnym 
grafem dwudzielnym. 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

17 

 

 

Symbolem   

   

  oznaczamy  pełny  graf 

dwudzielny, w którym   

 

      i   

 

     . 

Grafy  

   

 i  

   

 są izomorficzne. 

 

 

Matematyka Dyskretna – wykład 10 

dr Marcin Raniszewski 

18 

 

 

Załóżmy, że          . Wtedy: 



 

 graf  

   

 ma cykl Hamiltona         



 

 graf   

   

  ma  drogę  Hamiltona