Розфарбовування графіка
Розфарбовування графа можна описати як процес призначення кольорів вершинам графа. У цьому випадку не слід використовувати один і той же колір для заповнення двох сусідніх вершин. Ми також можемо назвати розфарбування графа розфарбуванням вершин. При розфарбовуванні графа ми повинні стежити, щоб граф не містив жодного ребра, кінцеві вершини якого пофарбовані в один і той же колір. Цей тип графіка відомий як правильно пофарбований графік.
Приклад розфарбовування графіка
javascript найближчий
На цьому графіку ми показуємо правильно пофарбований графік, який описується наступним чином:
Наведений вище графік містить кілька точок, які описані таким чином:
- Один і той же колір не можна використовувати для фарбування двох сусідніх вершин.
- Отже, ми можемо назвати це правильно розфарбованим графіком.
Застосування розфарбовування графів
Існують різні застосування фарбування графів. Деякі з їх важливих застосувань описані нижче:
- призначення
- Розфарбовування карти
- Планування завдань
- Судоку
- Підготуйте розклад
- Вирішення конфліктів
Хроматичне число
Хроматичне число можна описати як мінімальну кількість кольорів, необхідних для правильного фарбування будь-якого графіка. Іншими словами, хроматичне число можна описати як мінімальну кількість кольорів, необхідних для фарбування будь-якого графа таким чином, щоб жодні дві суміжні вершини графа не отримували однаковий колір.
Приклад хроматичного числа:
Щоб зрозуміти хроматичне число, розглянемо графік, який описується наступним чином:
Наведений вище графік містить кілька точок, які описані таким чином:
- Для фарбування двох суміжних вершин не використовується той самий колір.
- Мінімальна кількість кольорів цього графа – 3, необхідна для правильного розфарбування вершин.
- Отже, на цьому графіку хроматичне число = 3
- Якщо ми хочемо правильно розфарбувати цей графік, у цьому випадку нам потрібні принаймні 3 кольори.
Типи графіків хроматичного числа:
Існують різні типи графіків хроматичного числа, які описуються наступним чином:
Графік циклу:
Граф буде відомий як граф циклу, якщо він містить 'n' ребер і 'n' вершин (n >= 3), які утворюють цикл довжиною 'n'. У графі циклу може бути лише 2 або 3 ступені всіх вершин.
Хроматичне число:
- Хроматичне число в графі циклу буде 2, якщо кількість вершин у цьому графі парна.
- Хроматичне число в графі циклу буде 3, якщо кількість вершин у цьому графі непарна.
Приклади циклічного графіка:
Існують різні приклади циклових графів. Деякі з них описані так:
приклад 1: На наступному графіку ми маємо визначити хроматичне число.
рішення: У наведеному вище цикловому графі є 3 різні кольори для трьох вершин, і жодна з сусідніх вершин не забарвлена тим самим кольором. У цьому графі кількість вершин непарна. Так
Хроматичне число = 3
приклад 2: На наступному графіку ми маємо визначити хроматичне число.
рішення: У наведеному вище графі циклу є 2 кольори для чотирьох вершин, і жодна з сусідніх вершин не забарвлена тим самим кольором. У цьому графі кількість вершин парна. Так
Хроматичне число = 2
приклад 3: На наступному графіку ми маємо визначити хроматичне число.
рішення: На наведеному вище графіку є 4 різні кольори для п’яти вершин, а дві сусідні вершини пофарбовані в один і той же колір (синій). Отже, цей граф не є цикловим графом і не містить хроматичного числа.
Приклад 4: На наступному графіку ми маємо визначити хроматичне число.
рішення: У наведеному вище графіку є 2 різні кольори для шести вершин, і жодна з сусідніх вершин не пофарбована в той самий колір. У цьому графі кількість вершин парна. Так
Хроматичне число = 2
Графік планувальника
Графік буде відомий як плановий графік, якщо він намальований на площині. Краї графіка планувальника не повинні перетинатися.
Хроматичне число:
- У графіку планувальника хроматичне число має бути менше або дорівнювати 4.
- Графік планувальника також може бути показаний усіма наведеними вище цикловими графіками, крім прикладу 3.
Приклади графіка Планера:
Існують різні приклади плоских графіків. Деякі з них описані так:
приклад 1: На наступному графіку ми маємо визначити хроматичне число.
рішення: У наведеному вище графі є три різні кольори для трьох вершин, і жодне з ребер цього графа не перетинає одне одного. Так
список держав
Хроматичне число = 3
Тут хроматичне число менше 4, тому цей граф є плоским.
приклад 2: На наступному графіку ми маємо визначити хроматичне число.
рішення: У наведеному вище графі є 2 різні кольори для чотирьох вершин, і жодне з ребер цього графа не перетинає одне одного. Так
Хроматичне число = 2
Тут хроматичне число менше 4, тому цей граф є плоским.
приклад 3: На наступному графіку ми маємо визначити хроматичне число.
рішення: У наведеному вище графі є 5 різних кольорів для п’яти вершин, і жодне з ребер цього графа не перетинає одне одного. Так
Хроматичне число = 5
Тут хроматичне число більше 4, тому цей граф не є плоским графом.
Приклад 4: На наступному графіку ми маємо визначити хроматичне число.
рішення: У наведеному вище графі є 2 різні кольори для шести вершин, і жодне з ребер цього графа не перетинає одне одного. Так
Хроматичне число = 2
скільки 25 зі 100
Тут хроматичне число менше 4, тому цей граф є плоским.
Повний графік
Граф буде відомий як повний граф, якщо лише одне ребро використовується для з’єднання кожних двох різних вершин. Кожна вершина в повному графі пов’язана з кожною іншою вершиною. У цьому графі кожна вершина буде пофарбована іншим кольором. Це означає, що в повному графі дві вершини не містять однаковий колір.
Хроматичне число
У повному графі хроматичне число буде дорівнювати кількості вершин у цьому графі.
Приклади повного графіка:
Існують різні приклади повних графіків. Деякі з них описані так:
приклад 1: На наступному графіку ми маємо визначити хроматичне число.
рішення: Є 4 різні кольори для 4 різних вершин, і жоден з кольорів не є однаковим у наведеному вище графіку. Згідно з визначенням, хроматичне число - це кількість вершин. Так,
Хроматичне число = 4
приклад 2: На наступному графіку ми маємо визначити хроматичне число.
рішення: Є 5 різних кольорів для 5 різних вершин, і жоден з кольорів не є однаковим у наведеному вище графіку. Згідно з визначенням, хроматичне число - це кількість вершин. Так,
Хроматичне число = 5
приклад 3: На наступному графіку ми маємо визначити хроматичне число.
рішення: Є 3 різні кольори для 4 різних вершин, і один колір повторюється у двох вершинах у наведеному вище графіку. Отже, цей граф не є повним графом і не містить хроматичного числа.
Дводольний граф
Граф буде відомий як дводольний граф, якщо він містить два набори вершин, A і B. Вершина A може з’єднуватися лише з вершинами B. Це означає, що ребра не можуть з’єднувати вершини з набором.
Хроматичне число
У будь-якому дводольному графі хроматичне число завжди дорівнює 2.
Приклади дводольного графа:
Існують різні приклади дводольних графів. Деякі з них описані так:
приклад 1: На наступному графіку ми маємо визначити хроматичне число.
рішення: У наведеному вище графі є 2 різні набори вершин. Таким чином, хроматичне число всіх дводольних графів завжди буде 2. Отже
Хроматичне число = 2
дерево:
Зв’язаний граф буде відомий як дерево, якщо в цьому графі немає ланцюгів. У дереві хроматичне число дорівнюватиме 2 незалежно від кількості вершин у дереві. Кожен дводольний граф також є деревом.
Хроматичне число
У будь-якому дереві хроматичне число дорівнює 2.
що таке ymail
Приклади дерева:
Існують різні приклади дерева. Деякі з них описані так:
приклад 1: У наступному дереві ми повинні визначити хроматичне число.
рішення: Є 2 різні кольори для чотирьох вершин. Дерево з будь-якою кількістю вершин повинно містити хроматичне число, як 2 у наведеному вище дереві. Так,
Хроматичне число = 2
приклад 2: У наступному дереві ми повинні визначити хроматичне число.
рішення: Є 2 різні кольори для п'яти вершин. Дерево з будь-якою кількістю вершин повинно містити хроматичне число, як 2 у наведеному вище дереві. Так,
Хроматичне число = 2
Реальний приклад хроматичного числа
Припустімо, що Маррі є менеджером у компанії Xyz. Компанія наймає нових співробітників, і вона повинна отримати графік навчання для цих нових співробітників. Їй потрібно запланувати три зустрічі, і вона намагається використовувати кілька часових проміжків якомога більше для зустрічей. Якщо є працівник, який повинен бути на двох різних нарадах, тоді керівник повинен використовувати різні графіки для цих нарад. Припустимо, ми хочемо отримати візуальне представлення цієї зустрічі.
Для візуального представлення Маррі використовує крапку для позначення зустрічі. Якщо є співробітник, який має дві зустрічі і вимагає приєднатися до обох зустрічей, то обидві зустрічі будуть з'єднані за допомогою краю. Різні часові інтервали представлені за допомогою кольорів. Тож менеджер заповнює крапки цими кольорами таким чином, щоб дві крапки не містили того самого кольору, що має спільний край. (Це означає, що працівник, якому потрібно бути присутнім на двох зустрічах, не повинен мати однаковий часовий інтервал). Візуальне представлення цього описано таким чином:
