Ta’rif 1. G| graf G grafning qismi deyiladi, agar G| ning uchlari to`plami
G ga tegishli bo`lsa, ya’ni V|V bo`lsa, hamda G| ning barcha qirralari G ning
ham qirralar bo`lsa, ya’ni E|
V={a, v, c, d}, V|={a|, b|, c|, d|}, V| V.
G* graf G grafning to`ldiruvchisi deyiladi, agarda uning barcha uchlari G
grafga tegishli bo`lib, birorta ham qirrasi G ga tegishli bo`Ladi.
Ta’rif 2. Agar G=(X,U) grafning bo‘lagi G|=(X|,U|) uchun | bo‘lsa, u
holda graf sugraf deb ataladi.
Sugraflarni hosil qilish uchun faqat qirralarga murojaat qilamiz. Quyidagi
graflar sugraflardir.
Ta’rif 2. Agar graflarning uchlari to`plami orasida qo`shnilik munosabatini
saqlovchi biyeksiya mavjud bo`lsa, bu ikkita graf izomorf deyiladi. graf
grafga izomorf bo`lsa, kabi belgilanadi.
Ta’rif 3. Agar graf o`zining to`ldiruvchisiga izomorf bo`lsa, graf o`zini
o`zi to`ldiruvchi deyiladi.
Ta’rif 4. Qo`shni yoylar ketma-ketligi yo`l, qo`shni qirralar ketma-ketligi
Do'stlaringiz bilan baham: |