2.
Grafdan uchni olib tashlash amali qanday bajariladi?
3.
Toldiruvchi graf, qism graf haqidagi fikringizni bayon qiling?
4.
Grafda yangi uchni qo’shish, yangi qirrani(yoyni) qo’shish amali qanday
bajariladi?
5.
Birlashma amalida hosil bo’lgan grafning uchlari qanday bo’ladi?
6.
Berilgan graflarning birlashmasi(uyushmasi)
am ali va birikmasi
(tutashmasi) amali orasida qanday o’xshashlik va farqlar bor?
7.
Berilgan graflarning birlashmasi(uyushmasi) amali qanday bajariladi?
8.
Berilgan graflarning ko’paytmasi amali qanday bajariladi?
6.3. L. Eyler va Uilyam Gamilton graflari
Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikki uchi bog’langan graf
bog’lamli graf deyiladi
2
.
1-teorema. Agar grafdagi har bir uchning lokal darajasi ikkidan kichik bo’lmasa,
u holda bu graf siklga ega bo’ladi.
Grafning har bir qirrasidan faqat bir marta o’tadigan
zanjir Eyler zanjiri deb
ataladi.Yopiq Eyler zanjiriga(ya’ni Eyler sikliga) ega graf Eyler grafi deb ataladi.
Agar grafda yopiq bo’lmagan Eyler zanjiri topilsa, u holda bunday graf yarim
Eyler grafi deyiladi.
2- teorema. Bog’lamli graf Eyler grafi bo’lishi uchun
undagi barcha uchlarning
darajasi juft bo’lishi zarur va yetarlidir.
1-natija. Bog’lamli graf yarim Eyler grafi bo’lishi uchun undagi ikkitadan ko’p
bo’lmagan uchning darajalari toq bo’lishi zarur va yetarlidir.
Har bir yoydan faqat bir marta o’tadigan yo’l oriyentirlangan Eyler yo’li deyiladi.
10-shaklda grafni Eyler grafi bo’lishini tekshiramiz.
Dastlabki uch sifatida grafdagi 2 olingan bo’lsin. Bu uchdan a yonalishda (2,3)
qirra bo’ylab harakatlanish mumkin. Keyin b yo’nalishda (3,5) bo’ylab, c
yo’nalishda (5,1) bo’ylab, d yo’nalishda (1,3) bo’ylab, e yo’nalishda (3,4) bo’ylab,
2
Flyori algoritmini
’
-bu E.Lyuka tomonidan e’lon qilingan. (Lucas, E. Recteations
Mathematiqques. Paris: Gautheir-Villas,1891).
k yo’nalishda (4,5) bo’ylab, oxirida l yo’nalishda (5,2) bo’ylab 2
belgili uchga
o’tamiz. Harakatni shu yo’nalishda toxtatamiz.
Dostları ilə paylaş: 
