Definíció: Egy G irányított gráf egy (V,E,K,B) négyes, ahol V egy véges csücshalmaz, E egy véges élhalmaz, K és B két illeszkedési reláció V és E közt úgy, hogy minden élhez pontosan egy csúcs K-illeszkedjen és pontosan egy csúcs B-illeszkedjen. K, illetve B neve `ki ', illetve `be ' reláció.
Megjegyzés: Azaz az irányítt gráfban is minden élnek két végpontja lesz (amelyek akár egybe is eshetnek, ahogy gráfoknál), de a két végponthoz való viszony nem szimmetrikus (ahogy gráfoknál volt), hanem az egyikhez `ki ', a másikhoz `be ' viszonyban lesz az él. Amennyiben gráfokra úgy gondoltunk mint egy város úthálózata, akkor irányított gráf esetén egy olyan város úthálózatára kell gondolnunk, ahol minden út egyirányúsított. Ennek megfelelően könnyű definiálni az irányított séta/vonal/út fogalmát. Egy xy irányított séta egy olyan sorozat, amely a pontok és élek alternáló sorozata, ahol minden élt megelőzi az a pont, amelyből kifut és minden élt követi az a csúcs, amelybe befut. Tehát egy irányított séta megfordítása általában nem irányított séta.
Feladat: Legyen G egy irányított gráf. Igaz-e ha x-ből elérhető y, akkor y-ból is elérhető x?
Feladat: Egy irányított gráfban x és y csúcsok legyenek `oda-vissza elérhető' relációban, ha létezik xy és yx irányított séta is. Bizonyítsuk be, hogy az oda-vissza elérhetőség ekvivalenciareláció.
Feladat: Tegyük fel, hogy s és t a G irányított gráf két csúcsa továbbá, s-ből nem érhető el t. Ekkor G csúcsai S és T halmazokra bontható úgy, hogy a s csúcs S eleme legyen, t csúcs T eleme legyen, továbbá S és T közti összes él T felöl haladjon S felé.
Definíció: Egy irányított gráf irányított értelemben/erősen összefüggő, ha bármely csúcspár között mindkét irányban halad irányított séta/út.
Feladat: Legyen G egy irányított gráf. Legyen u és v (nem feltétlen különböző) csúcs. G-hez adjunk hozzá egy u-ból v-be vezető irányított utat (illetve irányított kört, ha u=v) úgy, hogy a hozzáadott résznek minden u-tól, v-től különböző csúcsa új (azaz G-ben nem szereplő) csúcs legyen. Bizonyítsuk be, ha G erősen összefüggő, akkor a fenti módon kapott G' gráf is erősen összefüggő.
Definíció: Az előző feladatban egy G irányított gráfból egy G' irányított gráfot konstruáltunk. Azt mondjuk, hogy G'-t G-ből fülragasztás operációval nyertük.
Feladat: Legyen G egy erősen összefüggő irányított gráf. Bizonyítsuk be, hogy G megkapható az egypontú 0 élű gráfból ismételt fülragasztás operációkkal.
Definíció: Egy turnament olyan irányított gráf, ahol minden csúcspár között pontosan egy irányított él halad.
Feladat: Legyen T egy turnament. Ekkor T összes csúcsa felsorolható úgy, hogy az utolsó kivételével minden csúcsból vezessen él a következőhöz.
Feladat: Legyen T egy turnament, amelyben minden csúcsból elérhető mindegyik csúcs. Ekkor T összes csúcsa lerakható egy köralakú asztal köré úgy, hogy minden csúcsból vezessen él jobb szomszédjához.
Feladat: Legyen T egy turnament. Bizonyítsuk be, hogy található benne egy olyan csúcs, amelyből minden más csúcs legfeljebb két hosszú irányított úttal elérhető.
Definíció: Egy x csúcs abszolút győztes egy tournamentben, ha minden más y csúcs esetén az x és y közötti él x felöl y felé halad. Egy x csúcs pszeeudo győztes egy tournamentben, ha minden más y csúcs esetén az x és y közötti él x felöl y felé halad vagy van olyan z csúcs, hogy x-ből z felé halad az él és z-ből y felé halad az él.
Otthoni munkára javaslat: Bizonyítsuk be, hogy van olyan tournament, amelyben nincs abszolút győztes. Bizonyítsuk be, hogy ha egy tournamentben van abszolút győztes, akkor az egyértelmű. Bizonyítsuk be, hogy minden tournamentben van pszeudo győztes. Bizonyítsuk be, hogy nem biztos, hogy a pszeudo győztes egyértelmű.
Feladat: Bizonyítsuk be, hogy minden tournamentben van olyan irányított út, amely az összes ponton áthalad.
Feladat: Bizonyítsuk be, hogy egy tournament csúcsai akkor és csak akkor állíthatók körbe úgy, hogy mindenki megverte a bal oldali szomszédját, ha a csúcsainak nincs olyan kettéosztása, amelyre minden osztályok közötti él ugyanolyan irányú.