Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan
graf bog‘langan graf deb ataladi.
Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo`lsa,
u holda bu ikkita uch bog‘langan deyiladi. Bunday uchlar to‘plami
grafda
ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami
bo‘yicha ekvivalentlik munosabatini inobatga
olgan holda berilgan grafni
bog‘lamlilik komponentlari deb ataluvchi bog‘lamli
qismlarning birlashmasi deb
qarash mumkin.
Tekis G
(
V
,
U
)
graf uchun m
r
1
n
k
tenglik o`rinlidir, bunda m
V ,
n
U , r – yoqlar soni, k – bog‘lamlilik komponentalar soni.
n
uzunlikdagi
marshrut
deb
n
ta qirraning bo`sh bo`lmagan ketma-ketligiga
aytiladi. Qo`shni
yoylar ketma-ketligi
yo`l
, qo`shni
qirralar ketma-ketligi
