Ma’ruza matni To’plam tushunchasi

Graf matritsasi: Matritsa ustunlari va qatorlari graf uchlarini nomerlariga mos keladi, uning elementi c_n x₁ va x_jbirlashtiruvchi qirralar sonidir. 2.6.graf uchun matritsa quyidagi ko’rinishga egadir.
0 2 1 0 0
2 0 4 0 0
Graf uchlarini turlicha nomerlash mumkindir. 2.6-rasmdagi grafni quyidagicha nomerlaymiz: masalan

Graflar uchun uchlar soni va qirralar soni muhimdir hamda uchlar va qirralar “insindent” ekanligi ham. Demak, 2.7-rasmda G₁ va G₂ izomorf graflar jufti ko’rsatilgandir.

2.7-rasm
Ko’pincha masalalarda uchlar orasidagi munosabat muhim rol o’ynamaydi. Bunga misol tariqasida tartib munosabat bo’lishi mumkin. Masalan, dan katta bu holda dan katta bo’lishi mumkin emas. Demak, uchlar orasidagi munosabat ma'lum’mo’ljalga egadir. Bunday graflarni mo’ljalga ega graflar yoki orientirli graflar deymiz.
Ta’rif. Orientirli D graf deb, bir juft D=(X, A) ga aytamiz. Bu yerda X uchlarning ixtiyoriy to’plami va A –uchlarning tartiblangan juftligini to’plamidir, uchlarning tartiblangan juftligini “yoylar” deymiz. juftlikda birinchi x yoy uchi, ikkinchi uch x_j yoyning oxiridir. 2.8-rasmda yoylar strelka bilan bezatilgandir.

2.8-rasm
Ta’rif. Graf ning qisman grafi deb ataladi, agarda u berilgan grafning barcha uchlariga ega bo’lib, ammo barcha qirralariga ega bo’lmasa, balki qisman qirralariga ega bo’lsa, ya’ni
Ta’rif. ning graf ostisi deb shunday grafga aytiladiki, bunda ular qism bo’ladi,
2.9-rasmda qisman grafga, grafostiga va grafga misol keltirilgan.