4. Dinamik ma‟lumotlar tuzilmasi haqida ma’lumot bering

48. Grafning siklomatik soni haqida tushuncha bering .
Grafning siklomatik soni tushunchasi, qandaydir rna 'noda, grafning bog'larnlilik darajasini aniqlovchi vositadir. Ravshanki, daraxt uchun A = 0 bo'ladi (1- teoremaga qarang).
Grafning o'rmon bo'lishi uchun uning siklomatik soni nolga teng bo'lishi zarur va yetarlidir (2- natijaga qarang). Grafning yagona siklga ega bo'lishi uchun uning siklomatik soni birga teng bo'lishi zarur va yetarlidir. Qirralari soni uchlari sonidan kichik bo'lmagan graf siklga egadir. Bu tasdiqlar ham 1- teoremaning natijalaridir.
3- m i sol. 3- shaklda tasvirlangan graf (6,9) -graf bo'lib, uning bog'lamlilik komponentlari soni birga teng. Bu grafning siklomatik sonini aniqlasak, A = 9 - 6 + 1 = 4 bo'ladi. Olib tashlangan qirralar 3- shaklda ingichka chiziqlar bilan ifodalangan.
Tarm oqlar
Graf. Uch. Qirra. Orgraf. Yoy. Tarmoq. To ‘plam. Blok-sxema. Gipergraf.
Bog 'lamli tarmoq. Sirtmoq. Yoyning о ‘tkazish qobiliyati. Uchning chiqish va
kirish yarim darajalari. Manba. О "pqon. Tarmoqdagi oqim. Yoy ho ‘ylah oqim.
Tarmoqdagi oqim miqdori. Maksimal oqim. To'yingan, to'vinmagan, to'g'ri va
teskari yoylar. Zanjir. Tarmoqning "to r jo y i”. Kesim. Manbani o'pqondan
ajratuvchi kesim. Kesimning о ‘tkazish qobiliyati. Minimal kesim.
10.8.1. Tarmoq tushunchasi. Graflar nazariyasida hozirgacha ba’zi
iboralar bo'yicha umumiy kelishuv qaror topmaganligini qayd qilgan edik.
Bu fikr graflar nazariyasining tarmoq va tarmoqqa oid tushunchalari bilan
ish ko‘rganda yaqqol namoyan bo‘ladi. Ba’zan, “tarmoq” iborasi o‘rniga
“to‘r” iborasini ham qo‘llaydilar. Masalan, S.V. Yablonskiyning 1986-
yilda bosilib chiqqan “Введение в дискретную математику” (Diskret
matematikaga kirish) nomli o‘quv qo‘llanmasida ([ 1 ]da) graf tushunchasi
umumlashtirilib, tarmoqning quyidagi ta’rifi berilgan va “tarmoq”
tushunchasi xususida fikrlar ham bayon qilingan:
“Berilgan M = {at,a2,...} to‘plam va har bir Et elementi A/dan
olingan R = {E0;El , E2,...} majmuani (to‘plamni) tarmoq deb ataymiz
va M ( E 0-,El, E 2,...) bilan belgilaymiz, bu yerda Ei = (av (i), av •
M to'plamning ob’yektlari tarmoqning uchlari deb, E0 majmuadagi
obyektlar esa - tarmoqning qutblari deb ataladi”.
Yuqorida eslatilgan kitobda ta’kidlanishicha: “Adabiyotda tarmoq
tushunchasiga yaqin tushunchalar ham uchraydi, masalan, “blok-sxem a”
tushunchasi, “gipergraf’ tushunchasi. Blok-sxema tushunchasi tarmoq
tushunchasidan oldin paydo bo‘lgan, gipergraf tushunchasi esa -
keyinroq”.