Graflarni bo'yash. Graf xromatik sinfi va xromatik soni. Bixromatik graflar

2. Xromatik Son (Chromatic Number): Xromatik son, grafning eng kam ranglar bilan to'g'rilash uchun kerak bo'lgan ranglar sonini ifodalaydi. Ushbu sonni topish o'z vaqti bilan murakkab masala bo'lishi mumkin va har bir grafning xromatik soni bir xil emas. Xromatik son, grafning xromatik sinfiga tengdir.

• 2. Xromatik Son (Chromatic Number): Xromatik son, grafning eng kam ranglar bilan to'g'rilash uchun kerak bo'lgan ranglar sonini ifodalaydi. Ushbu sonni topish o'z vaqti bilan murakkab masala bo'lishi mumkin va har bir grafning xromatik soni bir xil emas. Xromatik son, grafning xromatik sinfiga tengdir.

3. Bixromatik Graflar (Bipartite Graphs): Bixromatik graf, uchlar toifalari (qatlar) bo'yicha birlashgan grafdir. Ya'ni, grafning uchlarining har biri bitta toifaga tegishli bo'lib, toifalar ichida uchlar o'zaro bog'lanmagan. Bixromatik graf, ikki toifaga bo'lishib turadi: "A" va "B" misollarini olib ko'rsangiz, uchinchi uchlar har bir toifaga tegishli bo'ladi. Bixromatik grafning xromatik soni ikki bo'ladi (ya'ni 2).

• 3. Bixromatik Graflar (Bipartite Graphs): Bixromatik graf, uchlar toifalari (qatlar) bo'yicha birlashgan grafdir. Ya'ni, grafning uchlarining har biri bitta toifaga tegishli bo'lib, toifalar ichida uchlar o'zaro bog'lanmagan. Bixromatik graf, ikki toifaga bo'lishib turadi: "A" va "B" misollarini olib ko'rsangiz, uchinchi uchlar har bir toifaga tegishli bo'ladi. Bixromatik grafning xromatik soni ikki bo'ladi (ya'ni 2).

Graflarni bo'yash va xromatik sonni topish matematik va dasturiy informatika bo'yicha juda muhimdir. Grafning xromatik sonini aniqlash algoritmlari mavjud, lekin xromatik sonni eng past son bilan aniqlash odatda NP-to'g'ri (NP-complete) masalalariga kiradi. Biroq, bixromatik graflar uchun xromatik sonni aniqlash osonroq bo'lishi mumkin, chunki ular faqat ikki rangga ega.

• Graflarni bo'yash va xromatik sonni topish matematik va dasturiy informatika bo'yicha juda muhimdir. Grafning xromatik sonini aniqlash algoritmlari mavjud, lekin xromatik sonni eng past son bilan aniqlash odatda NP-to'g'ri (NP-complete) masalalariga kiradi. Biroq, bixromatik graflar uchun xromatik sonni aniqlash osonroq bo'lishi mumkin, chunki ular faqat ikki rangga ega.
• Graflar va ularning xromatik xususiyatlarini o'rganish va xromatik sonni topish graf teoriyasining muhim qismi va bir nechta amaliy masalalar uchun foydali bo'lib keladi.