Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

1 

 

 

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



 

      jest niepustym zbiorem wierzchołków 
grafu   



 

       jest  niepustym  zbiorem  krawędzi 
grafu   



 

      jest funkcją incydencji grafu   

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

2 

 

 

Funkcja 

incydencji 

w 

grafach 

nieskierowanych: 

                

 

   

 

    

 

   

 

        

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

3 

 

 

Funkcja incydencji w grafach skierowanych: 

                         

 

Grafy 

skierowane 

będziemy 

nazywać 

digrafami. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

4 

 

 

Krawędź     nazywamy  krawędzią  zwykłą  jeżeli 
łączy  dwa  różne  wierzchołki,  w  przeciwnym 
przypadku nazywamy ją pętlą. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

5 

 

 

Krawędzie   

 

  i   

 

  nazywamy  krawędziami 

wielokrotnymi jeśli    

 

        

 

 . 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

6 

 

 

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

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

7 

 

 

Grafem  pełnym  nazywamy  graf  prosty, 
w którym  każde  dwa  wierzchołki  są  połączone 
krawędzią. 

Graf  pełny  o     wierzchołkach  oznaczamy 
symbolem  

 

. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

8 

 

 

Wierzchołkiem 

izolowanym 

nazywamy 

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

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

9 

 

 

Grafem 

skończonym 

nazywamy 

graf 

o skończonym zbiorze wierzchołków i krawędzi. 

W  dalszej  części  wykładu  będziemy  zajmować 
się jedynie grafami skończonymi. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

10 

 

 

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. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

11 

 

 

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

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

12 

 

 

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

 

   

 

       

 

   

 

   nazywamy  cyklem,  jeśli 

wszystkie wierzchołki  

 

   

 

       

 

 są różne. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

13 

 

 

Graf  nie  zawierający  cykli  nazywamy  grafem 
acyklicznym. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

14 

 

 

Każdy graf acykliczny jest grafem prostym. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

15 

 

 

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  . 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

16 

 

 

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

                     

      

 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

17 

 

 

Grafem  regularnym  stopnia     nazywamy  graf, 
w którym wszystkie wierzchołki są stopnia  . 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

18 

 

 

Każdy  graf   

 

  jest  grafem  regularnym  stopnia 

     . 

Graf  

 

 ma 

      

 

 krawędzi. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

19 

 

 

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  

 

. 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

20 

 

 

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  . 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

21 

 

 

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

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

22 

 

 

Graf     nazwiemy  podgrafem  grafu   ,  jeżeli 
                          oraz       

    

 

    . 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

23 

 

 

Spójny  podgraf,  który  nie  jest  zawarty 
w większym  spójnym  podgrafie  grafu   , 
nazywamy składową grafu  . 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

24 

 

 

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

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

25 

 

 

Cyklem  Eulera  w  grafie     nazywamy  każdą 
drogę prostą i zamkniętą, zawierającą wszystkie 
krawędzie grafu  . 

Każdy cykl Eulera jest również drogą Eulera. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

26 

 

 

Twierdzenie  (Eulera)  o  istnieniu  drogi  Eulera 
w grafie: 

Graf  ma  drogę  Eulera     jest  spójny  i  ma 
dokładnie 

dwa 

wierzchołki 

stopnia 

nieparzystego  lub  ma  każdy  wierzchołek 
stopnia parzystego. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

27 

 

 

Twierdzenie  (Eulera)  o  istnieniu  cyklu  Eulera 
w grafie: 

Graf  ma  cykl  Eulera     jest  spójny  i  ma  każdy 
wierzchołek stopnia parzystego. 

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

28 

 

 

Izomorfizm grafów: 

Grafy 

 

 

      

 

      

 

    

 

  

 

     i  

 

 

    

 

      

 

    

 

  

 

  )  są  izomorficzne,  jeśli 

istnieją bijekcje       

 

       

 

  i       

 

   

   

 

  takie, że: 

 

 

        

 

   

 

     

 

             

 

      

 

   

 

 

Matematyka Dyskretna – wykład 9 

dr Marcin Raniszewski 

29 

 

 

Izomorfizm 

grafów 

zachowuje 

wszystkie 

własności 

grafu 

(na 

przykład: 

liczbę 

wierzchołków,  liczbę  krawędzi,  liczbę  krawędzi 
wielokrotnych, 

liczbę 

pętli, 

stopnie 

wierzchołków).