"mistahed" - 1 õppematerjal

Diskreetne matemaatika eksami kordamise materjal

 Taandatud graafil saab ära jätta tipud ning nende kaared.  Alamgraaf on graaf, millele on rakendatud nii jääkgraaf kui ka taandatud graaf.  Graaf on kahealuseline, kui tema tipud jagunevad kaheks mittelõikuvalt osahulgaks.  Tasandiline graa on paigutatav tasandile nii, et kaared ei lõiku.  Baas on selline minimaalne tippude hulk, kus selle hulga tippudest leidub tee graafi mistahed teise tipuni.  Sõltumatute tippude hulk on graafi osahulk, kus 2 suvalist tippu pole omavahel ühendatud.  Imoforsed graafid omavad samapalju tippe ja kaari ning erinevad üksteisest vaid nimetuse või paigutse poolest.  Pöördgraaf sisaldab kaari seal, kus graafil neid pole.  Puu on sidu tsükliteta orienteerimata graaf.  Puul on n tippu ja n-1 kaart.  Kromaatiline arv on minimaalne arv millega saab kõik graafi tipud ära