Gráf

Egy gráf egy G=(V,E,I) hármas. V egy véges halmaz, a G gráf csúcshalmaza, V elemei a G gráf csúcsai vagy pontjai. E egy véges halmaz, a G gráf élhalmaza, E elemei a gráf élei. I egy illeszkedési reláció V és E között (azaz I a V x E Descartes-szorzat egy részhalmaza). I-től azt követeljük (ahhoz, hogy gráfról beszélhessünk) meg minden élnek két végpontja legyen, amely egybe is eshet, azaz egy e él {v : vIe} végponthalmaza egy- vagy kételemű csúcshalmaz. Az egyszerű gráfoknál kialakult nyelvezetet most is használhatjuk. Egy különbségre felhívjuk a figyelmet. x,y csúcsk és e,f élek esetén e=xy és f=xy ismeretében egyszerű gráfok esetén tudjuk, hogy e=f. Gráfoknál ezt nem állíthatjuk.

Egy hurokél-nélküli gráf olyan gráf, amelyben nincs hurokél.

Egy egyszerű gráf olyan gráf, amelyben nincs hurok él és nincsenek párhuzamos élek. Ez persze formálisan nem igaz: egy egyszerű gráf esetén az élhalmaz pontpárokat tartalmaz, hurokélnelküli gráfban az élek csak az illeszkedési reláción keresztül kapcsolódnak a csúcsokhoz. Ennek ellenére a két fogalom azonosságának magától értétődőnek kell lenni. Egy egyszerű gráf V és E halmazát kiegészíthetjük egy illeszkedési relációval: egy e={x,y} él pontosan az x és y csúcsokkal illeszkedjen. Ezzel egy hurokél és párhuzamos élek nélküli gr'afhoz jutunk. Megfodítva egy hurok él és párhuzamos élek nélküli gráf esetén V mellett megadhatjuk az Ee={v: v I e} végponthalmazokat (e az összes élen keresztül fut). Ezzel egy egyszerű gráfhoz jutunk.