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

G ( x )  S =  .

Elementlarning eng ko'p sonini o'z ichiga olgan ichki barqarorlik to'plami eng katta ichki barqaror to'plam deb ataladi va bu to'plamning elementlari soni G grafigining ichki barqarorlik soni deb ataladi . Eng katta ichki barqaror to'plam aloqa nazariyasida muhim rol o'ynaydi.

Tashqi barqarorlik to'plami . T  to'plami Grafikning X G ( X ) tashqi barqaror deyiladi, agar T ga tegishli bo'lmagan har qanday cho'qqi T dan cho'qqilarga yoylar orqali bog'langan bo'lsa, ya'ni har qanday x  T uchun quyidagilar bajariladi: G ( x )  T .  .

Eng kam sonli elementlarni o'z ichiga olgan tashqi barqarorlik to'plami eng kam tashqi barqarorlik to'plami deb ataladi va bu to'plamning elementlari soni G ( X ) grafigining tashqi barqarorlik raqami deb ataladi.

Eyler va Gamilton grafiklari

Maqsad - grafiklarda optimallashtirish masalalarini echish uchun Eyler va Gamilton sikllarini qurish masalalarini o'rganish.
Tarkib:

• Eyler sikli va grafigi haqida tushuncha
• Eylerni aniqlash mezonlari va algoritmlari

hisobga oladi

• Eyler grafiklarini qo'llash
• Gamilton sikllari va grafiklari
• Gamilton sikllarini aniqlash usullari
• Gamilton grafiklarining qo'llanilishi
• Eylerning qiyosiy tahlili va

Gamilton grafiklari

Grafik Eyler siklini o'z ichiga olsa, Eyler deyiladi

• Grafik Eyler siklini o'z ichiga olsa, Eyler deyiladi
• Eyler sikli - har bir grafik chetini faqat bir marta o'z ichiga olgan yopiq marshrut (cho'qqilarni takrorlash mumkin)
• Misol
• a bcdefche a

Eyler sikli va grafik ta'rifi

Muammoni boshqa formulada hal qilish mumkin: agar grafikga yana bir chekka qo'shilsa, u holda har bir chekkani faqat bir marta o'z ichiga olgan marshrut yaratish mumkin, u cho'qqilarning biridan boshlanib, boshqasida tugaydi.

• Muammoni boshqa formulada hal qilish mumkin: agar grafikga yana bir chekka qo'shilsa, u holda har bir chekkani faqat bir marta o'z ichiga olgan marshrut yaratish mumkin, u cho'qqilarning biridan boshlanib, boshqasida tugaydi.
• A BCDCBDA B
• BDCDABC B _
• Bunday marshrut Eyler zanjiri hisoblanadi
• yarim Eyler grafigi