Топ питань
Часова шкала
Чат
Перспективи

Критичний граф

граф, у якому кожна вершина або ребро є критичним елементом З Вікіпедії, вільної енциклопедії

Критичний граф
Remove ads

Критичний граф граф, у якому видалення будь-якої вершини або ребра призводить до зменшення хроматичного числа графу.

Thumb
Вгорі зліва — вершинно-критичний граф з хроматичним числом 6. Решта N-1 подграфов мають хроматичне число 5.

Пов'язані визначення

  • -критичний граф — це критичний граф із хроматичним числом k.
  • Граф G з хроматичним числом k є вершинно-k-критичним, якщо кожна з його вершин є критичним елементом[1].

Властивості

  • Нехай G є k-критичним графом із n вершинами і m ребрами. Тоді:
    • G має тільки одну компоненту.
    • G — скінченний (теорема де Брёйна — Ердеша [2]).
    • δ(G) ≥ k − 1, тобто будь-яка вершина суміжна щонайменше k − 1 іншим вершинам. Строгіше, G реберно (k − 1)-зв'язний[3].
    • Якщо граф G (k − 1)-регулярний (кожна вершина суміжна рівно k − 1 іншим), то граф G або є повним графом Kk, або непарним циклом (теорема Брукса[4]).
    • 2m ≥ (k − 1)n + k − 3[5].
    • 2m ≥ (k − 1)n + [(k − 3)/(k2 − 3)]n[6].
    • Або G можна розбити на два менших критичних графи з ребром між кожною парою вершин, де дві вершини беруться з різних частин, або граф G має щонайменше 2k − 1 вершин[7]. Строгіше, або G має розклад такого типу, або для кожної вершини v графу G існує k-розфарбування, в якому v є єдиною вершиною зі своїм кольором, а всі інші класи кольорів мають щонайменше дві вершини[8].
  • Граф G є вершинно-критичним тоді і тільки тоді, коли для будь-якої вершини v існує оптимальне підхоже розфарбування, в якому вершина v одна представляє клас кольору.
  • 1-критичних графів не існує.
  • Єдиний 2-критичний граф — це K2.
  • Всі 3-критичні графи вичерпуються простими циклами непарної довжини[9].
  • Як показав Хайош[10], будь-який k-критичний граф можна сформувати з повного графу Kk комбінацією побудови Хайоша[ru] з операцією ототожнення двох несуміжних вершин. Граф, утворений таким способом, завжди вимагає k кольорів у будь-якому правильному розфарбуванні.
Thumb
4-критичний, але не реберно-критичний граф, оскільки
  • Хоча кожен реберно-критичний граф обов'язково є критичним, зворотне хибне. Наприклад, граф наведений праворуч, є 4-критичним, але не реберно-критичним[11].
Remove ads

Варіації та узагальнення

  • Двічі критичний граф — це зв'язний граф, у якому видалення будь-якої пари суміжних вершин зменшує хроматичне число на 2. Одна з нерозв'язаних задач — чи є Kk єдиним двічі критичним k-хроматичним графом[12].

Див. також

  • Фактор-критичний граф

Примітки

Література

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads