Головна

Інші підходи до розфарбуванні графів

  1. O інші умови, які рекламодавець і рекламне агентство вважають за необхідне передбачити в договорі;
  2. O62.2 Інші види слабкості пологової діяльності
  3. А) Соціологічні підходи до соціальних класів
  4. Аварійно-рятувальні та інші невідкладні роботи (АС і ДНР) в осередках інфекційних хвороб
  5. Автоматизація ділових процесів. Основні підходи до аналізу ділових процесів.
  6. Альтернативні підходи до визначення витрат і прибутку.
  7. Банківські операції та інші угоди кредитної організації

У 1943 р Г. Хадвігера висунув гіпотезу, тісно пов'язану з проблемою чотирьох фарб.

Гіпотеза Хадвігера а. Будь-зв'язний п-хроматичний граф стягаємо до До4.

для п ? 4 гіпотеза підтверджується. Справді, при п = 1 твердження тривіально. при п = 2 кожен зв'язний граф стягується до ребру, а при п = 3 - містить цикл і тому стягується до К3 . Наступна теорема доводить гіпотезу для п = 4.

Теорема 60.1. Кожен зв'язний n-хроматичний граф стягаємо до До4 .

нехай G - Зв'язний 4-хроматичний граф. Якщо в G є точки зчленування, то деякий його блок повинен бути 4-хроматичним, інакше з теореми 53.3 слід було б, що ? (G) < 4. стягніть G до цього блоку. З тієї ж причини блок залишиться 4-хроматичним після стягування ребер, інцидентних вершині ступеня 2. Таким чином, не втрачаючи спільності, можна вважати G блоком зі ступенями вершин не менше трьох.

нехай C = (v1, v2 , ..., Vp , v1) - простий цикл максимальної довжини р в G. Очевидно, що р ? 4. Просту ланцюг, що зв'язує дві несоседних вершини циклу С і не містить інших вершин цього циклу, назвемо З-хордою. Покажемо, що для будь-якої вершини v1 циклу С існує С-хорда, якій належить ця вершина. Так як deg v1 ? 3, То є ребро е = v1u, що не належить С. Якщо и VC, то ребро е є С-хордою. нехай u ? VC. Тоді по теоремі 34.1 існує простий цикл Ci = (v1, u2 , ..., V2 , ..., V1),що містить ребро е и

 
 

вершину v2. ланцюг L = (v1, І, ..., v2) Повинна мати деяку вершину vi відмінну від v2 і належить циклу З, інакше С не був би простим циклом максимальної довжини. частина ланцюга L від v1 до першої вершини, що належить циклу З, і буде шуканої З-хордою.

Припустимо, що існують дві С-хорди Т1 = (vi, ..., vj) и T2 = (vk , ..., Vl) із загальною вершиною t поза С. Тоді частина графа, що складається з С, Т1 и T2, Стягується до К4. Один з варіантів стягування зображений на рис. 60.1, а.

Тепер розглянемо випадок, коли не існує пересічних С-хорд. Будь-яка С-хорда ділить цикл С на дві прості ланцюга. Виберемо таку З-хорду Т1, щоб одна з цих ланцюгів З '= (vi , ...,vj) була найкоротшою, і візьмемо вершину vh на цьому ланцюзі (така вершина існує, оскільки С-хорда з'єднує дві несоседних вершини циклу). Розглянемо деяку З-хорду Т2 = (vk, ..., vi). Якщо при цьому вершина vi буде розташована на З ', то ланцюг (vk,..., vi), що належить циклу С, Буде коротше, ніж З '. отже, vi не лежить на ланцюгу С У цьому випадку частина графа, що складається з С, Т1 и Т2, Стягується до К4. Один з варіантів стягування показаний на рис. 60.1, б.

Після тогокак буде отримано граф К4 решту вихідного графа стягнемо до К4.

Відомо, що твердження гіпотези Хадвігера при n = 5 еквівалентно гіпотезі чотирьох фарб. А саме, вірна наступна

Теорема 60.2. Наступні два твердження еквівалентні:

1) гіпотеза чотирьох фарб вірна;

2) будь-який зв'язний 5-хроматичний граф стягаємо до К5.

На закінчення цього параграфа розглянемо один алгебраїчний підхід до проблеми розмальовки плоских графів. Детально про це див. [14].

 
 

 нехай G - Плоский граф, і ?: VG-> А (де А = {0, а, b, а + b} = (а) + (b) - Пряма сума двох циклічних груп другого порядку) - його розфарбування. Тоді умовою правильності обраної розмальовки виявиться така умова: yij = ? (vi) + ? (vj) ? 0 для будь-якого ребра vivj графа G. Тому для довільного циклу С =(v1, v2 , vn , .., vn+1), Vn+1= v1 повинні бути виконані вимоги

нехай тепер G - Довільний зв'язний граф, кожному ребру vivj якого поставлена ??у відповідність змінна yij. Отримаємо систему рівнянь S (G), записавши зоотношенія виду (1) для кожного циклу графа G, і сі-угему S (G)-для кожного циклу з деякого фіксованого базису циклів.

Лемма 60.3. Кожному рішенню системи S (G) при фіксованій забарвленні ?(v0) деякої вершини v0 однозначно відповідає правильна розфарбування графа G чотирма кольорами.

 
 

 Для заданої вершини v?VG розглянемо довільну ланцюг Pa - (V0 , v1 , ..., v?) і приймемо

де yij складають рішення системи S (G).

 В силу (1) значення ? {v?) не залежить від вибору ланцюга Р?, тому воно визначає колір вершини v?. Так як yij ? 0 для vivj € EG, то будь-які суміжні вершини сміють різні кольори. Таким чином, розфарбування, що задається формулою (2), правильна.

Так як граф може містити велику кількість циклів, то перейдемо від системи рівнянь S (G) до системи S (G).

Теорема 60.4. Кожному рішенню системи S (G) при фіксованій забарвленні ? (v0) Деякої вершини v0 однозначно відповідає правильна розфарбування графа G чотирма кольорами.

 
 

 В силу леми 60.3 досить показати, що рішення системи S (G) є і рішенням системи S (G). Для цього спочатку розглянемо довільний простий цикл

що не належить базису циклів З ' графа G. Відомо (§ 21), що С можна представити у вигляді суми по модулю 2 декількох циклів з С. нехай С = С1 + С2,
 
 

С1, С2 € С '

Аналогічні міркування можна привести і в тому випадку, коли цикл С є сумою не двох, а більшого числа циклів з базису циклів З '. Значить, співвідношення (1) виконується для будь-якого простого циклу. Якщо ж цикл С не простий, то необхідно представити його у вигляді об'єднання декількох простих циклів, для кожного з яких виконується (1).

Проблема чотирьох фарб | вчинені графи


правильна розфарбування | Оцінки хроматичного числа | розфарбування ребер | Зв'язок матроідних розкладів графів з розмальовками | Тріангулірованние графи |

© 2016-2022  um.co.ua - учбові матеріали та реферати