"lihtgraafi" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

[36]. Prüferi kood. Märgendatud puude loendamine. Cayley teoreem. [37]. Märgendamata puude arv. [38]. Kooskõlad graafis. Berge'i teoreem. [39]. Kooskõlad kahealuselises graafis. Halli teoreem. [40]. Tasandiline graaf. Euleri valem: seos tasandilise graafi tippude, servade ja tahkude arvude vahel. Eulri valemi rakendusi. [41]. Graafi tasandilisuse kriteeriumid. Kuratowski teoreem. [42]. Graafi tippude värvimise ülesanne. Brooksi teoreem (tõestuseta). [43]. Tasandilise lihtgraafi värvimine 6 ja 5 värviga. Neljavärviprobleem ja kaartide värvimine. I. OSA [1]. Hulgad. Alam- ja ülemhulgad. Tehted hulkadega. Hulk on koosvaadeldavate objektide kogum. *Eristatakse kaht erinvat hulgateooriat: Naiivne hulgateooria- Naiivses hulgateoorias puudub kindel tugev aksiomaatika, ent ta on piisavalt efektiivne väga paljude lihtsamate vajaduste rahuldamiseks. Sageli õpetatakse matemaatikas esmalt naiivset hulgateooriat, kuna ta võimaldab inimesel paremini mõista