Irányított gráf
Egy irányított gráf egy G=(V,E,B,K) hármas. V a G gráf csúcshalmaza, V elemei a G
gráf csúcsai vagy pontjai. E a G gráf élhalmaza, E elemei a gráf
élei. B és K egy illeszkedési reláció V és E között (azaz B (és
K is) a V x E
Descartes-szorzat egy részhalmaza).
B-től és K-tól azt követeljük (ahhoz, hogy
irányított gráfról beszélhessünk)
meg minden élhez pontosan egy csúcs legyen, amely
vele B, illetve K relációban áljon.
A B be reláció, K a ki reláció. Ha vBe és uKe akkor
azt mondjuk, hogy e befut a v csúcsba és e kifut az u csúcsból.
e egy uv él (sorrend nagyon fontos!).
e egy hurokél az u csúcson, ha uBe és uKe.
e és f párhuzamos, ha valamely u, v csúcspárra
e és f is uv él.