Az első gráfelméleti probléma - a Königsbergi hidak problémája - és annak megoldása a XVIII. századra nyúlik vissza. Azóta a gráfok sok más problémánál bizonyultak kiváló modellezési eszköznek, a hasonló játékos jellegű feladatok mellett egyre több gyakorlati alkalmazásuk jelent meg: használják többek között adatbázisrendszerekben, fordítóprogramokban, CAD rendszerekben, képfeldolgozás és a mesterséges intelligencia területén. Ezekben az alkalmazásokban gyakran felmerülő problémák a legrövidebb utak és a minimális feszítőfák meghatározása, valamint hálózatokbanmaximális folyamok keresése. A diplomamunkámban az ezeket a problémákat megoldó algoritmusok közül tárgyalok néhányat. A fejezet további részében a gráfokkal kapcsolatos legfontosabb fogalmakat definiálom, majd a gráfok leggyakoribb ábrázolási módjait mutatom be. A fejezet végén az algoritmusok elemzésénél használatos főbb jelölésekről lesz szó.