4-ma’ruza. Grafning maxsus turdagi ko‘phad yordamida berilishi. Kalit so‘zlar

4-MA’RUZA. GRAFNING MAXSUS TURDAGI KO‘PHAD YORDAMIDA BERILISHI.

Kalit so‘zlar: Graf, orgraf, uch, qirra, yoy, sirtmoq, karrali qirralar, uchning local darajasi, multigraf, ko‘phad, grafning uchlari qo‘shniligi matritsasi, orientirlanmagan multigrafning uchlari qo‘shniligi matritsasi, orientirlangan grafning uchlari qo‘shniligi matritsasi, sirtmoqsiz orgraf uchlari qo‘shniligi matritsasi, grafning qirralari qo‘shniligi matritsasi, insidentlik matritsasi.
Grafning maxsus turdagi ko‘phad yordamida berilishi.
Grafni maxsus turdagi ko‘phad yordamida ham berish mumkinligini ta’kidlaymiz. Uchlari to‘plami bo‘lgan graf berilgan bo‘lsin. grafning yakkalangan uchlari yo‘q deb faraz qilamiz,. Bu grafni ta o‘zgaruvchilarga bog‘liq

ko‘rinishdagi ko‘phad yordamida tasvirlash mumkin, bu yerda ko‘paytma shartni qanoatlantiruvchi barcha juftlar bo‘yicha amalga oshiriladi, o‘zgaruvchi uchga mos keladi, – va uchlarni tutashtiruvchi qirralar soni, – uchdagi sirtmoqlar soni.
ko‘phad grafga izomorflik aniqligida mos kelishini isbotlash mumkin.
6- misol. 9- shaklda tasvirlangan grafga mos ko‘phadni aniqlaymiz. Berilgan orientirlanmagan grafda yettita uch va sakkizta qirra bor. Uning har bir uchiga bitta ( ) o‘zgaruvchini mos q1ilib qo‘yamiz. grafda karrali qirralari yo‘q, uning uchta qirrasi sirtmoq-lardan iborat bo‘lib, ulardan ikkitasi 3 uchga, biri esa 5 uchga insidentdir. Shuning uchun , , ; , qolgan barcha bo‘ladi. Berilgan grafga mos ko‘phad

ko‘rinishga ega bo‘ladi. ■
7- misol. ko‘phadga mos keluvchi grafning geometrik tasvirini topamiz. Bu ko‘phadning tarkibiga ko‘ra unga mos keluvchi orientirlanmagan grafda 4ta uch va 6ta qirra bo‘lib, bu qirralardan ikkitasi karrali ( ) va bittasi sirtmoq ( ) ekanligini ta’kidlaymiz. Berilgan grafning geometrik tasvirlanishlaridan biri 1- shaklda keltirilgan. ■