Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Визначення хроматичного числа. Хроматичний поліном

 

Для обчислення хроматичного числа вводять функцію p(G,l).

Означення 2.5.6. Для заданого графа G і натурального числа l через p(G,l) (хроматичний поліном) позначається кількість всіх правильних розфарбувань графа G з допомогою l фарб.

Слід відмітити що наступна формула справедлива для достатньо малих S0.

Теорема 2.5.2. Справедлива формула:

, де

S – кількість ребер суграфів графа G;

С – кількість компонент зв’язаності суграфів графа G;

- кількість суграфів графа G.

Якщо суграфів немає, то .

Ця формула дає змогу прослідкувати такі властивості функції p(G,l):

1) p(G,l) це многочлен степеня S0 з коефіцієнтом 1 при старшому члені;

2) p(G,l) ділиться на l.

Нариклад, за теоремою 2.5.2 обчислимо p(G,l) для трикутного графа G.

 
 

 

 


Розпишемо кожен з випадків, нагадавши, що сам граф є своїм суграфом (випадок г):

 

а) S=0, C=3,

б) S=1, C=2,

в) S=2, C=1,

г) S=3, C=1, .

Тоді .

Простим перебором чисел від 1, знаходимо хроматичне число. Підставивши у цю формулу або , отримаємо, що p(G,1)=p(G,2)=0, тобто кількість правильних розфарбувань графа однією чи двома фарбами дорівнює нулеві – однією або двома фарбами граф розфарбовувати не можна. Хроматичне число цього графа є 3, оскільки його підставляння у формулу дало позитивний результат:

p(G,3)=1×2×3=3!=6

Властивості хроматичних поліномів:

1) p(G,l)= p(G1,lp(G2,l) (якщо G(p,l) складається з двох незв’язних частин, то розфарбування можна вибирати незалежно для двох незв’язних графів).

2) p(G,l)= p(G1,lp(G2,l) (якщо граф G отримано з двох графів склеюванням в одній точці х0).

3) p(G,l)= p(G1,lp(G2,l) (якщо граф G отримано з двох незв’язних графів склеюванням по ребру, зовнішньому для обох графів).

4) p(G,l)= p(G1,l)-p(G’,l) (якщо граф G отримано з G1 доданням ребра без зміни вершин, G’ – граф, отриманий з G1 склеюванням вершин, які інцидентні доданому ребру).

Граф G є однохроматичним тоді і тільки тоді, коли він не містить ні одного ребра; двохроматичним – тоді і тільки тоді, коли він не містить циклів непарної довжини.

Для розфарбування граней, утворених перетином прямих ліній на площині достатньо двох кольорів.

Необхідною і достатньою умовою розфарбування двома кольорами є те, що кожна вершина повинна мати парний степінь ³ 2.


Читайте також:

  1. CMM. Визначення моделі зрілості.
  2. I визначення впливу окремих факторів
  3. II. Визначення мети запровадження конкретної ВЕЗ з ураху­ванням її виду.
  4. II. Множення круглих багатоцифрових чисел на розрядні числа.
  5. II. Мотивація навчальної діяльності. Визначення теми і мети уроку
  6. Ocнoвнi визначення здоров'я
  7. S Визначення оптимального темпу роботи з урахуванням динаміки наростання втоми.
  8. А. Визначення розмірів і площі зони хімічного зараження.
  9. Алгебраїчний спосіб визначення точки беззбитковості
  10. Алгоритм визначення проекцій точок на поверхнях обертання
  11. Алгоритм побудови калібрувального графіка для визначення загального білка сироватки крові
  12. Алгоритм побудови калібрувального графіка для визначення загального білка сироватки крові




Переглядів: 1779

<== попередня сторінка | наступна сторінка ==>
Задача про чотири фарби. Правильне розфарбування графа | Поняття алгебраїчної операції

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.002 сек.