"multigraafist" - 1 õppematerjal

Diskreetse matemaatika elemendid

30 Multigraaf o DEF: Et toodud definitsioonis loetakse servadeks ainult tippude hulga kaheelemendilisi alamhulki, siis ei tohi graafis esineda silmuseid, st servi mis ühendavad mingit tippu iseendaga, ega kordseid servi, olukordi, kus mingit kahte tippu ühendab rohkem kui üks serv. Siiski tuleb vahel ka neid arvestada, sellisel juhul räägitakse graafi asemel multigraafist. Täisgraaf o DEF: Täisgraafiks nimetatakse graafi, milles iga tipupaari vahel on serv. Nullgraaf o DEF: Nullgraafiks nimetatakse graafi, milles pole ühtegi serva. Täiendgraaf o DEF: Graafi G täiendgraafiks nimetatakse graafi G’, millel on sama tippude hulk nagu 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