cheksiz graf
deyiladi.
Yo'l
(path) – bu bironta tugundan boshqa bir tugungacha bo'lgan yonma-yon
joylashgan tugunlar ketma-ketligidir.
Grafning asosiy alomatlari
Grafning uchlari va qirralari to`plamini mos ravishda va kabi belgilanadi.
ushbu to’plamda uchlar berilgan bo’ladi. to’plamida esa qirallarning qushni uchlar
juftligi bilan aniqlanadi.
Masalan: Bu holda grafning grafik ko’rinishi quyidagicha bo’ladi .
Grafga misol
Qirra ikkita uch bilan aniqlanadi.
Umumiy uchga ega bo`lgan ikkita qirra qo`shni hisoblanadi. Agar grafning
ikkita uchi qirra bilan tutashtirilgan bo`lsa, bu uchlar
qo`shni uchlar
deyiladi.
Grafning bir uchdan chiqqan ikki qirrasi
qo`shni qirralar
deyiladi. Agar grafda boshi
va oxiri bitta tugunda tutashadigan qirra mavjud bo'lsa, unga
ilmoqli
qirra deyiladi.
Qirra tushunchasi
Agar
grafda
takroriy
(karrali)
qirralar
mavjud
bo`lsa,
bunday
grafga
multigraf
deyiladi. Agar grafda karrali qirralar bilan birga uchni o`z-o`zi bilan
tutashtiruvchi ilmoqlar mavjud bo`lsa, bunday grafga
psevdograf
deyiladi.
A) multigraf; B) psevdograf
Yo`naltirilmagan grafika
Yo'naltirilmagan grafik - bu grafikning tepalarini bog'laydigan qirralarda
yo'nalish bo'lmagan grafik. 2.a-rasmda
1
2
3
,
,
V
V V V
=
tepaliklar to'plami bilan
yo'naltirilmagan grafik tasvirlangan. Yuqoridagi grafikdagi qirralarning to'plami
(
) (
) (
)
1
2
2
3
1
3
,
,
,
,
,
V
V V
V V
V V
=
shaklida yozilishi mumkin. Shuni ham ta'kidlash
mumkinki, qirralarning
(
) (
) (
)
2
1
3
2
3
1
,
,
,
,
,
V
V V
V V
V V
=
deb yozilishiga hech narsa
to'sqinlik qilmaydi, chunki qirralarning yo'nalishi yo'q. Shuning uchun
yo'naltirilmagan grafikdagi qirralar tartibli juftliklar emas. Bu yo'naltirilmagan
grafikning asosiy xarakteristikasi. Yo'naltirilmagan grafikalar tepaliklar bilan
tasvirlangan ob'ektlar orasidagi nosimmetrik munosabatlarni ifodalash uchun
ishlatilishi mumkin. Masalan, shaharlar majmuasini bog'laydigan ikki tomonlama yo'l
5
tarmog'ini yo'naltirilmagan grafik yordamida ko'rsatish mumkin. Shaharlar grafikdagi
tepaliklar bilan ifodalanishi mumkin va qirralari shaharlarni bog'laydigan ikki
tomonlama yo'llarni ifodalaydi.
|
