Grejaus kodai – tai taip sugeneruotos poaibes, kai bet kokios dvi gretimos poaibes skiriasi 1 elementuPilnas grafas – tai toks grafas, kurio virsunes sujungtos su visomis kitomis to grafo virsunemis.Tuscias grafas – tai grafas turintis n virsuniu ir neturintis briaunu.Dvipusis grafas tai toks grafas kurio virsunes galima isskaidyti i du poaibius A ir B taip, kad kiekvienos grafo briaunos galai priklausytu skiritingiems poaibiams.Multi grafas – tai toks grafas turintis bent viena virsuniu pora sujungta keliom briaunom.Grafas G yra plokstusis, jei ji galima pavaizduoti plokstumoje taip, kad jo briaunos kirstusi tiktai virsunese.Medis – tai jungusis grafas neturintis ciklu.1. Jei grafas yra medis, tai bet kurias dvi jo virsunes jungia vienas ir tik vienas kelias.2. Visos medzio briaunos yra tiltai.3. N virsuniu medis turi N-1 briauna.4. Jungusis N virsuniu ir N-1 briaunos grafas yra medis.Grafo jungianciuju medziu vadinamas toks medis kuris jungia visas pradinio grafo virsunes ir jo briaunos yra grafo briaunos.Jei G yra jungusis svorinis grafas, tai tarp visu grafo G jungianciuju medziu yra vienas arba keli, kurio bendrasis svoris yra maziausias. Toks grafas vadinamas grafo G minimaliuoju jungianciuoju medziu.Kruskalo algoritmas:1. Rasti pigiausia grafo briauna ir nudazyti ja.2. Rasti pigiausia dar nenudazyta, ir kuria nudazius nebutu issaukiamas ciklas.3. Kartoti 2 tol, kol raudonuju briaunu galai panaudos visas grafo virsunes.Primo metodas:1. Randame virsune ir ja nudazome x.2. Randame trumpiausia briauna tarp nudazytos x ir nenudazytos y virsunes. (x,y) i medi ir y nudazome.3. Kartoti 2 tol, kol yra nenudazytu virsuniuOilerio ciklas – tai toks ciklas kada visos briaunos yra apeinamos po viena karta.Teorema. Jei G(v,u) yra multigrafas, tada butina ir pakankama salyga, kad grafas G turetu oilerio cikla yra:1. Grafas turi buti jungusis.2. visu jo virsuniu laipsniai turi buti lyginiai (siuo atveju jis tures Oilerio cikla) arba jis turi dvi nelyginio laipsnio virsunes (siuo atveju jis tures Oilerio grandi prasidedancia vienoje nelyginio laipsnio virsuneje ir besibaigiancia kitoje).
Oilerio ciklo radimo algoritmas