7
Grafni to'ldiruvchisi bu aynan bir tugunlar va aynan bir qirralardan tashkil
topgan va mavjud grafni to'liq bo'lishini ta'minlovchi grafga aytiladi.
a)
to’liq graf
b)
graf va uning to’ldiruvchisi
To'liq, yo'naltirilmagan grafda qirralar soni quyidagi formula (1) orqali
aniqlanadi:
(1)qaerda n – yoylar(tugunlar) soni.
D grafning to'yinganligi (density) grafning qirralrining tugunlar nisbatiga
to’liqlik munosabat koefitsientini belgilaydi va quyidagi formula (2) orqali
aniqlanadi:
(2)qaerda n – grafning tugunlar soni, m – grafning qirralar soni.
Grafning to'yinganligi koefitsientiga qarab ikki hil graf ko’rinishi aniqlash mumkin:
to'yingan graf va siyrak graf
