Noszály, CsabaTóth, Ágnes2006-07-282006-07-2820052006-07-28http://hdl.handle.net/2437/270Az 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ó.4712054 bytes2869862 bytesapplication/octet-streamapplication/pdfhuno_restrictiongráfgráfalgoritmusokminimális feszítőfamaximális folyamgráfok bejárásalegrövidebb utak