Diskreetne matemaatika I IAY0010 eksami konspekt
puu). Kui puule lisada kaar, tekib tsükkel ja pole enam puu.
Graafi värvimine on värvide omistamine graafi tippudele selliselt, et mistahes 2 ühendatud kaart
oleksid eri värvi (naabertipud eri värvi). Graafi kromaatiline arv on min arv, mis näitab, mitme
erineva värviga õnnestub graafi tipud värvida sellised, et naabertipud eri värvi. Kromaatiline arv 1 on
ainult tühjal graafil. Kahealuseline graaf -> kromaatiline arv 2 ja vastupidi. On olemas
naabrusmaatriks, intsidentsusmaatriks. Klassikalised ülesanded: Köningsbergi sillad (kas on võimalik
ületada sillad täpselt 1 kord, jõudes alguspunkti, ei kuna sellisel Euleri graafil pole kõik tippude
astmed paarisarvulised), Rändkaupmehe ülesanne (kaupmees tahab rännata läbi linnade ja koju
tagasi jõuda, leida optimaalseim teekond), Kaardi värvimisülesanne (värvida kaart võimalikult
väheste värvidega, riigid on graafi tipud ja kaared on ühisete piiridega riikide vahel, 1852 hüpotees 4
annaabi.ee 
