Matematyka dyskretna – dr Marcin Raniszewski 

 

Matematyka Dyskretna – ćw. 11 

Teoria grafów 

Wprowadzenie, macierze sąsiedztwa, drogi i cykle Eulera 

 

Grafem 

  nazywamy uporządkowaną trójkę                       , gdzie: 



 

     jest niepustym zbiorem wierzchołków grafu   



 

     jest niepustym zbiorem krawędzi grafu   



 

     jest funkcją incydencji grafu  , przy czym: 

o  w grafie nieskierowanym: 

                

 

   

 

    

 

   

 

        

o  w grafie skierowanym (digrafie): 

                         

Krawędź 

   nazywamy  krawędzią  zwykłą  jeżeli  łączy  dwa  różne  wierzchołki,  w  przeciwnym  przypadku 

nazywamy ją pętlą. 

Krawędzie 

 

 

 i 

 

 

 nazywamy krawędziami wielokrotnymi jeśli 

   

 

        

 

 . 

Graf 

  nazywamy prostym jeśli nie posiada pętli i krawędzi wielokrotnych. 

Wierzchołkiem izolowanym nazywamy wierzchołek, który nie jest końcem żadnej krawędzi. 

Dalej będziemy rozważać tylko grafy skończone: 

Drogą  grafu 

   nazywamy  dowolny  ciąg  krawędzi    

 

   

 

       

 

  spełniający  zależność:     

 

      

 

   

   

 . 

Mówimy, że droga ta ma długość 

 . Jeśli  

   

   

 

, to droga ta jest zamknięta. 

Drogę  nazywamy drogą prostą, jeśli wszystkie krawędzie ją tworzące są różne. 

Zamkniętą drogę prostą o ciągu wierzchołków 

  

 

   

 

       

 

   

 

  nazywamy cyklem, jeśli wszystkie wierzchołki 

 

 

   

 

       

 

 są różne. 

Stopniem wierzchołka 

  (       ) grafu   nazywamy liczbę krawędzi z   jako jednym z wierzchołków, przy 

czym pętle zliczamy podwójnie. Liczbą 

 

 

    oznaczamy liczbę wierzchołków grafu   stopnia  . 

Suma stopni wierzchołków grafu jest dwa razy większa od liczby jego krawędzi. 

Zad.  1.  Niech  dany  będzie  graf 

 :           

 

   

 

   

 

   

 

   

 

   

 

             

 

   

 

     

 

   

 

   

  

 

   

 

     

 

   

 

     

 

   

 

     

 

   

 

     

 

   

 

     

 

   

 

     

 

   

 

     

 

   

 

     

 

   

 

     

 

   

 

  . 

Narysuj ten graf. Wskaż w nim: 

(a)  pętle, 
(b) trzy drogi zamknięte o długości 2, 
(c)  trzy drogi zamknięte o długościach 4, 5 i 8, 
(d) trzy drogi proste o długościach 3, 4 i 6, 
(e)  trzy drogi proste zamknięte o długościach 2, 5 i 9, 
(f)  trzy cykle 

Podaj stopnie wierzchołków oraz wyznacz liczby 

    . 

Matematyka dyskretna – dr Marcin Raniszewski 

 

Zad. 2. Niech dany będzie graf 

 , w którym:  

 

       ,  

 

       ,  

 

       ,  

 

       , 

 

 

       . Ile krawędzi ma ten graf? 

Jeśli krawędź łączy dwa wierzchołki, to nazywamy je wierzchołkami sąsiednimi. 

Macierzą  sąsiedztwa digrafu 

   o    wierzchołkach  

 

   

 

       

 

  nazwiemy  macierz 

   wymiaru      ,  której 

każdy wyraz 

 

  

 jest liczbą krawędzi od wierzchołka 

 

 

 do wierzchołka 

 

 

. 

Dla  dowolnego  digrafu 

   o     wierzchołkach   

 

   

 

       

 

  liczba  dróg  o  długości 

   z  wierzchołka   

 

  do 

wierzchołka 

 

 

 jest równa elementowi 

 

  

 macierzy 

 

 

, gdzie 

  jest macierzą sąsiedztwa digrafu  . 

Zad. 3. Podaj ile jest dróg o długości 3 z wierzchołka 

  do   oraz z   do   poniższego digrafu: 

 

Graf 

  nazywamy spójnym, jeśli każda para różnych wierzchołków jest połączona drogą w tym grafie. 

Graf 

  nazwiemy podgrafem grafu  , jeżeli                          oraz      

    

      . 

Spójny podgraf, który nie jest zawarty w większym spójnym podgrafie grafu 

 , nazywamy składową grafu  . 

Drogą Eulera w grafie 

  nazywamy każdą drogę prostą, zawierającą wszystkie krawędzie grafu  . 

Cyklem Eulera w grafie 

  nazywamy każdą drogę prostą i zamkniętą, zawierającą wszystkie krawędzie grafu 

 . 

Twierdzenia Eulera: 



 

Graf  ma  drogę  Eulera 

   jest  spójny  i  ma  dokładnie  dwa  wierzchołki  stopnia  nieparzystego  lub  ma 

każdy wierzchołek stopnia parzystego 



 

Graf ma cykl Eulera 

  jest spójny i ma każdy wierzchołek stopnia parzystego 

Zad. 4. Podaj: 

(a)  przykład grafu spójnego, który nie ma cyklu Eulera, 
(b) przykład grafu o wierzchołkach parzystego stopnia, który ma cykl Eulera, 
(c)  przykład grafu o wierzchołkach parzystego stopnia, który nie ma cyklu Eulera. 

Matematyka dyskretna – dr Marcin Raniszewski 

 

Zad.  5.  Czy  jest  możliwe,  aby  owad  poruszający  się  wzdłuż  krawędzi  sześcianu  przeszedł 
każdą krawędź dokładnie raz? Odpowiedź poprzyj odpowiednim rysunkiem grafu. 

Zad.  6.  Które  z  grafów  mają  cykle  Eulera,  a  które  nie  mają  i  dlaczego?  Podaj  przykładowy 
cykl Eulera dla grafów, które je posiadają. 

 

 

 

Zad. 7. Które z grafów mają drogi Eulera, a które nie mają i dlaczego? Podaj taką drogę dla 
grafów, które ją posiadają. 

 

 

Matematyka dyskretna – dr Marcin Raniszewski 

 

Zad. 8. Zbuduj graf mający zbiór wierzchołków  

                    , w którym wierzchołki 

 

 

  i 

 

 

  są  połączone  krawędzią,  jeśli  ciągi 

 

 

  i 

 

 

  różnią  się  na  dokładnie  dwóch 

współrzędnych. 

(a)  Ile składowych ma ten graf? 
(b) Ile wierzchołków danego stopnia ma ten graf? 
(c)  Czy ten graf ma cykl Eulera? Czy ten graf ma drogę Eulera? 

Zad.  9.  Czy  można  tak  przejść  dany  dom  aby  przez  każde  drzwi  przejść  dokładnie  raz? 
Odpowiedź uzasadnij. Jak zmieni się odpowiedź, jeśli drzwi między dwoma dużymi pokojami 
będą zamknięte?