2. Элементы теории множеств

0

2	1	0	0	1	0	0	1	0
3	0	1	1	0	0	0	0	1
4	1	0	0	0	0	1	1	0
5	0	1	0	0	1	0	0	1
6	0	0	1	0	1	0	0	1
7	0	0	0	1	0	1	1	0

Grafiklardagi Gamilton sikllari

• Agar Gamilton sikli bo'lsa, grafik Gamiltonian deb ataladi
• Tsikl Gamiltonian deb ataladi , agar u har bir cho'qqini faqat bir marta o'z ichiga olsa va grafikning barcha qirralarini aylanib o'tishga kiritish shart emas.

Gamilton grafigi
Gamilton bo'lmagan grafik

Gamilton tsikli tushunchasi birinchi marta Uilyam Hamilton tomonidan ko'rib chiqilgan dunyo bo'ylab sayohat qilish muammosi bilan bog'liq holda paydo bo'ldi: grafikning barcha uchlarini - turli mamlakatlar poytaxtlarini - bir marta aylanib, boshlang'ich nuqtaga qaytish.

• Gamilton tsikli tushunchasi birinchi marta Uilyam Hamilton tomonidan ko'rib chiqilgan dunyo bo'ylab sayohat qilish muammosi bilan bog'liq holda paydo bo'ldi: grafikning barcha uchlarini - turli mamlakatlar poytaxtlarini - bir marta aylanib, boshlang'ich nuqtaga qaytish.
• 20 ta shtat uchun vazifa dodekaedrning barcha uchlarini kesib o'tishni anglatadi.
• 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-1

Tarixiy ma'lumotnoma
1
2
3
4
5
6
7
8
9
10
o'n bir
12
13
14
15
16
17
18
19
20
Gamilton sikllarini aniqlash usullari: Roberts va Floresning sanab o'tish usuli. 1

• G= grafigi uchun M= ||m ij || o'tish matritsasi k  n o‘lchami :

k = maksimal daraja _ v i , v i V, n=|V|
m ij − i -chi uchi v q , agar grafikda v i uchidan yoy bo'lsa tepaga v q . M matritsaning j- ustunining elementlarini tashkil etuvchi cho'qqilarni o'zboshimchalik bilan tartiblash mumkin.

• v 1 ustunidagi birinchi cho'qqi (masalan, a cho'qqisi) tuzilgan Gamilton zanjiriga qo'shiladi . Keyin a ustunidagi birinchi mumkin bo'lgan cho'qqi (masalan, b ) zanjirga qo'shiladi , keyin c - b ustunida va hokazo.
• S ga tegishli bo'lmagan cho'qqi tushuniladi , uning qo'shilishi tsiklning muddatidan oldin yopilishiga olib kelmaydi.