o Valime graafist suvalise tipu v. Olgu 0 graaf ainsa tipuga v ja U=V{v}, st ülejäänud tippude hulk o Iga = 1, ... , - 1 korral leiame graafist vähima kaaluga serva , mis ühendab mingit graafi -1 tippu mingi tipuga Lisame alamgraafile -1 serva ja tema teise otspunkti . Eemaldame hulgast Primi algoritmi korrektsus: o Rakendatagu Primi algoritmi sidusale kaalutud graafile , milles on n tippu o Et on sidus, siis igal sammul leidub serv, mis ühendab alamgraafi -1 mõne veel ühendamata tipuga o Algoritmi rakendamise tulemus -1 on puu, sest pole tsükleid ja ta on sidus. -1 sisaldab graafi kõiki tippu, järelikult on toespuu o Tõestame, et toespuu = -1 kaal on minimaalne o Invariant: igal sammul k saadud graaf sisaldub mingis minimaalse kaaluga toespuus. Kui see kehtib ka -1 kohta, siis on -1 ise
Sidus graaf on Euleri graaf, kui tema kõikide tippude aste on paarisarvuline. Graafi 𝐺 = (𝑇, 𝐾) jääkgraaf on graaf 𝑄 = (𝑇, 𝐵), kus 𝐵 ⊂ 𝐾. Seega saadakse jääkgraaf osade kaarte ärajätmisega, kusjuures kõik tipud säilivad. Graafi -..- taandatud graaf on graaf 𝑄 = (𝐷, 𝐵), kus on ära jäetud osad graafi G tipud ja nende tippudega seotud kaared, seega 𝐵 ⊂ 𝐾 𝑗𝑎 𝐷 ⊂ 𝑇. Graaf on teisele alamgraaf, kui ta on sellele graafile samaaegselt nii jäägraaf kui ka taandatud graaf. Graaf on kahealuseline, kui tema tipud jagunevad kaheks mittelõikuvaks osahulgaks selliselt, et graafi iga kaar seob ühe osahulga mingit tippu teise osahulga mingi tipuga. Graaf on tasandiline, kui ta on paigutatav tasandile selliselt, et ta kaared ei lõiku. Orienteeritud graafi baas B on selline minimaalne tippude osahulk BcT, kus hulga B tippudest leidub tee selle graafi mistahes teise tipuni (graafi iga tipp on baasist saavutatav)
Orienteeritud graaf on Euleri graaf, kui ta omab Euleri kontuuri ehk iga tipu sisend- ja väljundaste on võrdsed. 16. Mis on jääkgraaf? Jääkgraaf on graaf, mis saadakse osade kaarte ärajätmisega, kusjuures kõik tipud säilivad. 17. Mis on taandatud graaf? Taandatud graaf on graaf, kus on ära jäetud osad tipud ja nendega seotud kaared. 18. Mis on alamgraaf? Alamgraaf on graaf, mis on mingi graafi taandatud graafi jääkgraaf ehk on sellele graafile samaaegselt nii taandatud graaf kui ka jääkgraaf. 19. Milline graaf on kahealuseline? Graaf on kahealuseline, kui tema kõik tipud jagunevad kaheks mittelõikuvaks osahulgaks selliselt, et graafi iga kaar seob ühe osahulga mingit tippu teise osahulga mingi tipuga. 20. Milline graaf on tasandiline? Graaf on tasandiline, kui ta on paigutatav tasandile selliselt, et ta kaared ei lõiku. 21. Mis on orienteeritud graafi baas? Kas baas on suurim või väikseim võimalik hulk
[2] Suunatud graaf, tipud, kaared o DEF: Suunatud graafiks nimetatakse paari G = (V, E), kus V on mittetühi hulk ning E hulk, mis koosneb hulga V elementide järjestatud paaridest. o Paare nimetame graafi kaarteks. Kaart tipust u tippu v tähistame (u, v) või uv. V = {1, 2, 3, 4, 5, 6} E = {(1,2), (1,4), (1,5), (2,6), (3,3), (3,6), (4,1), (4,6), (5,3), (6,2)} Kahe tipu vahel võib olla 0, 1 või 2 kaart. Alusgraaf o DEF: Igale suunatud graafile vastab alusgraaf, kus kaared on asendatud suunamata servadega. Suunatud graafi Boole’i maatriks o Suunatud graafi saab esitada nullidest ja ühtedest koosneva maatriksina, mis ei tarvitse enam olla sümmeetriline peadiagonaali suhtes. 49. Sisendaste ja väljundaste. Teoreem sisendastmete ja väljundastmete summast. [2] Sisendaste o Tipu v sisendaste d+(v) on tippu v sisenevate kaarte arv. Väljundaste o Tipu v väljundaste d-(v) on tipust v väljuvate kaarte arv.
annaabi.ee 
