"otstipuga" - 1 õppematerjal

Diskreetse matemaatika elemendid

graafil G, aga servaga on ühendatud parajasti need tipud, mille vahel graafis G serv puudub. Kaalutud graaf o DEF: Rakendustes on sageli vaja graafe, mille igale servale (või tipule) on vastavusse seatud üks reaalarv. Sellist graafi nimetatakse kaalutud graafiks ning vastavaid reaalarve kaaludeks. Intsidentsus o Kui tipp v kuulub servale e, siis ütleme, et tipp v ja serv e on intsidentsed. o Iga serv on intsidentne täpselt kahe tipuga, serva otstipuga. Kui serv e ühendab tippe u ja v, siis märgime seda ka tähisega e = {u,v} või e = uv. Naabertipud o DEF: Naabertipud on need tipud, mis on servaga ühendatud. Graafi naabrusmaatriks 31  o Olgu G = (V, E) graaf tippude hulgaga V = {v1, …, vn}. Graafi G naabrusmaatriks on n x n-maatriks A = (aij), kus o Naabrusmaatriks on sümmeetriline peadiagonaali suhtes ja peadiagonaalil on nullid.