Mavzu: Graflarda erkin uchlarini uchlarni tanlash, bo’yash. To’plamlarning to’plam ostilarini aniqlash, birlashtirish

Теоrema (to‘rt xil bo‘yoq haqidagi teorema). Ixtiyoriy G planar graf to‘rttadan ortiq bo‘lmagan ranglar bilan tog‘ri bo‘yalishi mumkin, ya’ni .
Graf xromatik sonini baholashning bir qancha evristik algoritmlari mavjud. Xasis algaritm deb nomlanuvchi algoritmni keltirib o‘tamiz. Ranglarni  bilan belgilaymiz va ni -rang deb ataymiz.
Xasis algoritm quyidagilardan iborat:
(a) uchlarni biror bir tartibda joylashtiriladi: ;
(b) uchni rangga bo‘yaladi;
(c) agar uchlar bo‘yalgan bo‘lsa, u holda uchni bu uch bilan qo‘shni bo‘lgan uchlarni bo‘yash uchun ishlatilmagan ranglar ichida eng kichik j-nomerli  rangga bo‘yaladi.
Xasis algoritmdan foydalanilgan holda olingan bo‘yashning optimalligi, uchlarni joylashtirishni tanlab olish tartibiga bog‘liq. Har doim uchlarni joylashtirishning shunday tartibi mavjudki, xasis algoritmni optimal  bo‘yashlar soniga olib keladi.
Shuni ta’kidlab o‘tish kerakki, xasis algoritm yordamida grafni bo‘yashda, d darajali uchni bo‘yashdagi erishilmagan ranglar soni d sonidan ortmaydi, demak nomerli rang ishlatilishi mumkin. Shuning uchun ham quyidagicha baho o‘rinli.

Теоrema. Agar G graf uchlarining maksimal darajasi d ga teng bo‘lsa, u holda xasis algoritm yordamida graf uchlarini dan ortiq bo‘lmagan rangga bo‘yash mumkin.

To’plam tushinchasi, to’plam ustida amallar

To'plam, to'plam osti, bo'sh to'plam, chekli va cheksiz to'plamlar, birlashma, kesishma, ayirma, to'ldiruvchi to'plam osti, universal to'plam , sonli to'plamlar, to'plamni o'zaro kesishmaydigan to'plam ostilarga ajratish.

"To'plam" tushunchasi-matematika kursining asosiy tushunchalaridan biridir. (Matematikada asosiy tushunchalar deganda ta'riflanmaydigan tushunchalar tushuniladi. Masalan, maktab kursidan ma'lumki, geometriyaning asosiy tushunchalari quyidagilar hisoblanadi: nuqta, to'g'ri chiziq, tekislik va masofa).To'plam tushunchasini faqatgina misol orqali tushuntirish mumkin. Misol, birinchi kurs talabalari to'plami, Buxoroda yashovchilar to'plami, jismning molekulalar to'plami, fermer xo’jaligidagi qo'ylar to'plami, tekislikdagi nuqtalar to'plami va hokazo. Odamlar bularga bolaligidan o'rganib qolgani uchun ularni osongina qabul qiladi. 1- sinf matematika kitobida bola turli xil tasvirdagi to'plamni ko'radi: turli xil hayvonlar to'plami, koptoklar, kitoblar va boshqa ob'ektlar to'plami. U bularni sanaydi va taqqoslaydi: Bir to'plamda ob'ektlar soni ko'p, ikkinchisida kam va bolada to'plam tushunchasi xaqida aniq tasavvur hosil bo'ladi ( to'plam termini ishlatilmasa ham).
Matematikada ob'ektlar to'plami (sonlar, nuqtalar, funktsiyalar va hokazo) haqida gapirilganda bu ob'ektlarning bir butunligi tushuniladi. To'plam nazariyasining asoschisi nemis matematigi Geogr Kantor (1845­1918) bu fikrni quyidagicha izohlaydi: "to'plam" deganda biz bir-biridan farq qiluvchi qandaydir aniq predmetlar, ya'ni ob'ektlarning ongimizda bir butun shaklda mujassamlashuvini tushunamiz.
Hayotda uchraydigan ba'zi so'zlar to'plam ma'nosida ishlatiladi. Masalan, "yig'ilish" , "poda", "sbor", "kollektsiya" va hokazolar shular jumlasidandir. To'plamni tuzuvchi turli tabiat ob'ektlari (odamlar, uylar, kitoblar, geometrik figuralar, sonlar va hokazorlar)ga uning elementlari deyiladi. Masalan, 3 soni natural son to'plamining elementi hisoblanadi, May oyi yildagi oylar to'plamining elementidir. To'plam bilan uning elementi o'rtasidagi munosabatni "tegishli" hamda "tegishli emas" so'zlari orqali ifodalash mumkin. Misol, 3 soni natural sonlar to'plamiga tegishli , -2 soni natural sonlar to'plamiga tegishli emas.
To'plamlar katta lotin alifbosi harflari A,B,C,D...bilan, to'plam elementlari esa kichik lotin harflari a,b,c... bilan belgilanadi. "Tegishli"
so'zi ^£ belgi bilan, "tegishli emas" so'zi esa ^£ belgi bilan almashtiriladi. Agar "a ob'ekt biror A to'plamning elementi" bo'lsa, uni quyidagicha belgilaymiz: a^£A. Bu yozuv quyidagicha o'qiladi: "a element A to'plamga tegishli".
Agar "a element Ato'plamga tegishli emas" bo'lsa, quyidagicha yoziladi.
a^£ A .
Misol, agar A- juft natural sonlar to'plami bo'lsa, quyidagi misollar to'g'ri bo'ladi:
16£A; 328£A; 17 ^£ A ; 11 ^£ A.
Elementlari soniga qarab to'plamlar chekli va cheksiz to'plamlarga bo'linadi. Elementlar soni chekli bo'lsa,- chekli to'plam, elementlari soni cheksiz bo'lsa, cheksiz to'plam deb aytiladi.

1. 
   kursda o'rganiladigan predmetlar to'plami, auditoriyadagi talabalar to'plami, soch tolalari to'plami- chekli to'plam; doira ustidagi nuqtalar to'plami, natural sonlar to'plami - cheksiz to'plamga misol bo'ladi.
   

To'plam bitta elementdan iborat bo'lishi ham mumkin. Masalan "nur" so'zidagi unli harflar to'plami. Bu to'plam 1 ta elementdan, ya'ni "u" harfidan iborat.

Agar , to'plamning birorta ham elementi bo'lmasa, bunday to'plam bo'sh to'plam deyiladi. Bo'sh to'plam 0 deb belgilanadi.Masalan, oydagi odamlar to'plami, uchburchakdagi diagonallar to'plami, x +1=0 tenglama haqiqiy ildizlari to'plami bo’sh to’plamdir.
To'plamning elementlari to'plamlar ham bo'lishi mumkin. Masalan, maktabdagi sinflar to'plami. Bu to'plam elementlari bo'lgan sinflar o'z navbatida o'quvchilar to'plamidir. Lekin o'quvchilar maktabdagi sinflar to'plamining elementlari bo'lmaydi.
II.To'plamlarning berilish usullari To'plam asosan ikki usulda beriladi:

Elementlarni bevosita keltirish yoki sanash yordamida beriladi. Agar a, b,c - A to'plamning turli ob'ektlar belgilari bo'lsa, A to'plam quyidagicha yoziladi: A={a,b,c} va quyidagicha o'qiladi "A to'plam a,b,c elementlardan iborat".

Bu usul chekli to'plamlarda qo'llaniladi, lekin bu shart bilan birga elementlar soni to'plamda ko'p bo'lmasligi kerak.

2. Elementlarning xarakteristik xossasiga qarab beriladi.

   
   

Masalan, A natural sonlar to'plami 6 dan kichik. Bu to'plam ikkinchi usulda berilgan : hamma A to'plam elementlarining xarakteristik xossasi ko'rsatilgan, ya'ni natural son bo'lish va 6 sonidan kichik bo'lishi asosida.

A to'plam elementlarini 1-usulda quyidagicha yozish mumkin:
A={ 1,2,3,4,5 }
To'plam elementining ayrim xarakteristik xossasi ko'rsatilgan bo'lsa ,uni quyidagicha ifodalaymiz: qavsda element belgisi yoziladi, keyin vertikal chiziq o'tkaziladi, so'ng to'plam elementlarining xossasi yoziladi. Masalan: 6 dan kichik bo'lgan A natural sonlar to'plami quyidagicha yoziladi: A={x / x ^£ N, x<6} bu erda N- natural sonlar
to'plami. To'plam cheksiz bo'lganda ikkinchi usuldan foydalaniladi, Masalan : markazi 0 nuqtada r radiusli aylanada yotuvchi M nuqtalarning A to'plami quyidagicha yozish mumkin:
A={M / | OM| =r}