Graf je apstraktan matematički model sistema objekata među kojima mogu postojati neke veze. Na primer gradovi povezani putevima. Tokom procesa apstrahovanja zaboravljamo vrstu objekata i beležimo samo informaciju o tome da li su dva objekta uvezi ili ne.

Na gornjoj slici možemo videti da objekat a nije u vezi ni sa jednim drugim objektom a da je objekat d u vezi sa drugih pet (i,e,u,g,h). Putanja linija i to da li se one seku, nema nikakvog značaja.

Graf je u stvari skup čvorova i grana, gde čvorovi predstavljaju objekte a grane veze između objekata.

Dimenzija grafa je broj čvorova u grafu.

Susedni čvorovi su oni koji su povezani nekom granom.

Stepen čvor je broj grana koje dopiru do nekog čvora.

Izolovan čvor je onaj koji je stepena 0, tj do njega ne dopire nijedna grana.

Viseći čvor je onaj koji je stepena 1, tj do njega dopire samo jedna.

Šetnja u grafu (običnom ili težinskom) je proizvoljan niz čvorova i grana. Šetnja počinje čvorom zatim sledi grana itd. Šetnja se završava čvorom. Prvi i poslednji čvor u grani su krajevi šetnje, a ako je početni čvor jednak krajnjem, tada je šetnja zatvorena.

Povezan graf je onaj u kome za bilo koja dva čvora postoji šetnja koja ih povezuje.

Komponenta povezanosti grafa G je najveći povezani podgraf grafa G.

Grafovi