Оцветяване на графика
Оцветяването на графа може да се опише като процес на присвояване на цветове на върховете на графика. При това един и същи цвят не трябва да се използва за запълване на двата съседни върха. Можем също да наречем оцветяване на графика като Vertex Coloring. При оцветяването на графа трябва да внимаваме графът да не съдържа никакви ребра, чиито крайни върхове са оцветени със същия цвят. Този тип графика е известна като правилно оцветена графика.
Пример за оцветяване на графика
пролетни бримки
В тази графика показваме правилно оцветената графика, която е описана по следния начин:
Горната графика съдържа някои точки, които са описани по следния начин:
- Един и същ цвят не може да се използва за оцветяване на двата съседни върха.
- Следователно можем да го наречем правилно оцветена графика.
Приложения за оцветяване на графики
Има различни приложения на оцветяване на графики. Някои от техните важни приложения са описани, както следва:
- Възлагане
- Оцветяване на карта
- Планиране на задачите
- Судоку
- Подгответе разписание
- Разрешаване на конфликти
Хроматично число
Хроматичното число може да се опише като минималния брой цветове, необходими за правилното оцветяване на всяка графика. С други думи, хроматичното число може да се опише като минимален брой цветове, които са необходими за оцветяване на всеки граф по такъв начин, че на два съседни върха на графика да не бъде присвоен един и същи цвят.
Пример за хроматично число:
За да разберем хроматичното число, ще разгледаме графика, която е описана по следния начин:
Горната графика съдържа някои точки, които са описани по следния начин:
- Същият цвят не се използва за оцветяване на двата съседни върха.
- Минималният брой цветове на тази графа е 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 различни цвята за три върха и нито един от ръбовете на тази графика не се пресича. Така
конвертиране на низ в char java
Хроматично число = 3
Тук хроматичното число е по-малко от 4, така че тази графика е плоска графика.
Пример 2: В следващата графика трябва да определим хроматичното число.
Решение: В горната графика има 2 различни цвята за четири върха и нито един от ръбовете на тази графика не се пресича. Така
Хроматично число = 2
Тук хроматичното число е по-малко от 4, така че тази графика е плоска графика.
Пример 3: В следващата графика трябва да определим хроматичното число.
Решение: В горната графика има 5 различни цвята за пет върха и нито един от ръбовете на тази графика не се пресича. Така
Хроматично число = 5
Тук хроматичното число е по-голямо от 4, така че тази графика не е плоска графика.
Пример 4: В следващата графика трябва да определим хроматичното число.
Решение: В горната графика има 2 различни цвята за шест върха и нито един от ръбовете на тази графика не се пресича. Така
Хроматично число = 2
Тук хроматичното число е по-малко от 4, така че тази графика е плоска графика.
Пълна графика
Графът ще бъде известен като пълен граф, ако само едно ребро се използва за свързване на всеки два различни върха. Всеки връх в пълен граф е свързан с всеки друг връх. В тази графика всеки връх ще бъде оцветен с различен цвят. Това означава, че в пълната графика два върха не съдържат един и същи цвят.
Хроматично число
В пълен граф хроматичното число ще бъде равно на броя на върховете в този график.
Примери за пълна графика:
генератор на случайни числа в c
Има различни примери за пълни графики. Някои от тях са описани по следния начин:
Пример 1: В следващата графика трябва да определим хроматичното число.
Решение: Има 4 различни цвята за 4 различни върха и нито един от цветовете не е еднакъв в горната графика. Според дефиницията хроматичното число е броят на върховете. Така,
Хроматично число = 4
Пример 2: В следващата графика трябва да определим хроматичното число.
Решение: Има 5 различни цвята за 5 различни върха и нито един от цветовете не е еднакъв в горната графика. Според дефиницията хроматичното число е броят на върховете. Така,
Хроматично число = 5
Пример 3: В следващата графика трябва да определим хроматичното число.
Решение: Има 3 различни цвята за 4 различни върха и един цвят се повтаря в два върха в горната графика. Така че тази графика не е пълна графика и не съдържа хроматично число.
Двустранна графика
Графът ще бъде известен като двустранен граф, ако съдържа два набора от върхове, A и B. Върхът на A може да се съединява само с върховете на B. Това означава, че ръбовете не могат да се съединяват с върховете с набор.
Хроматично число
Във всяка двустранна графика хроматичното число винаги е равно на 2.
Примери за двустранна графика:
Има различни примери за двустранни графи. Някои от тях са описани по следния начин:
Пример 1: В следващата графика трябва да определим хроматичното число.
Решение: Има 2 различни набора от върхове в горната графика. Така че хроматичното число на всички двуделни графи винаги ще бъде 2. И така
Хроматично число = 2
Дърво:
Свързана графа ще бъде известна като дърво, ако в нея няма вериги. В едно дърво хроматичното число ще бъде равно на 2, без значение колко върха има в дървото. Всеки двустранен граф също е дърво.
Хроматично число
Във всяко дърво хроматичното число е равно на 2.
java ламбда изрази
Примери за дърво:
Има различни примери за дърво. Някои от тях са описани по следния начин:
Пример 1: В следното дърво трябва да определим хроматичното число.
Решение: Има 2 различни цвята за четири върха. Дърво с произволен брой върхове трябва да съдържа хроматичното число като 2 в горното дърво. Така,
Хроматично число = 2
Пример 2: В следното дърво трябва да определим хроматичното число.
Решение: Има 2 различни цвята за пет върха. Дърво с произволен брой върхове трябва да съдържа хроматичното число като 2 в горното дърво. Така,
Хроматично число = 2
Пример за хроматично число от реалния живот
Да предположим, че Мари е мениджър в компанията Xyz. Компанията наема няколко нови служители и тя трябва да получи график за обучение за тези нови служители. Тя трябва да насрочи трите срещи и се опитва да използва малкото времеви интервали колкото е възможно повече за срещи. Ако има служител, който трябва да присъства на две различни срещи, тогава мениджърът трябва да използва различните часови графици за тези срещи. Да предположим, че искаме да получим визуално представяне на тази среща.
За визуално представяне Marry използва точката, за да посочи срещата. Ако има служител, който има две срещи и иска да се присъедини към двете срещи, тогава и двете срещи ще бъдат свързани с помощта на край. Различните времеви интервали са представени с помощта на цветове. Така че мениджърът запълва точките с тези цветове по такъв начин, че две точки да не съдържат един и същи цвят, който споделя край. (Това означава, че служител, който трябва да присъства на двете срещи, не трябва да има едно и също време). Визуалното представяне на това е описано по следния начин:
