16-mavzu graflarning berilish usullari. Qo`shnilik va intsedentlik matritsalari. Graflarning izomorfligi. Grafning maxsus turdagi ko‘phad yordamida berilishi

Download 151,04 Kb.

bet	3/3
Sana	31.12.2021
Hajmi	151,04 Kb.
	#208942

1 2 3

Bog'liq
16-mavzu graflarning berilish usullari. Qo`shnilik va intsedentl

Teorema .

Insidentlik matritsalari. Uchlari va qirralari ( ) bo‘lgan belgilangan graf berilgan bo‘lsin. Bu grafning uchlariga satrlari, qirralariga esa ustunlari mos keluvchi va elementlari

ko‘rinishda aniqlangan ( , ) matritsagrafning insidentlik matritsasi deb ataladi.

ko‘rinishda aniqlangan ( , ) matritsaga grafning insidentlik matritsasi deb ataladi.

Misol. 13- shaklda tasvirlangan grafning insidentlik matritsasi quyidagicha bo‘ladi:

.

Teorema.Graflar (orgraflar) faqat va faqat insidentlik matritsalari bir-birlaridan satrlarining o‘rinlarini va ustunlarining o‘rinlarini mos almashtirishlar yordamida hosil bo‘lsagina izomorf bo‘lishadi.

Download 151,04 Kb.

Do'stlaringiz bilan baham:

1 2 3