Презентация на тему "Раскраска графов"

Содержание

• 
  Слайд 1

  ПРЕЗЕНТАЦИЯ НА ТЕМУ: «Раскраска графов»

  Выполнила: Килочкина В.А Проверила: Новик Н.Г

• 
  Слайд 2
  

  Раскраска графа по степеням вершин Алгоритм Упорядочить вершины по степеням начиная с наибольшей степени вершины. Задать начальное значение счетчика k=1. Первую вершину окрашиваем в цвет kи заносим в букет B(k). Просматриваем следующую неокрашенную вершину, если она несмежная с вершинами букета B(k) то окрашиваем ее в цвет k, иначе пропускаем. Проверяем количество просмотренных вершин, если i n(i- номер текущей вершины), то возврат в п.4, иначе k=k+1 и просмотр списка начинается заново исключая окрашенные вершины. Проверка на окончание поиска: если неокрашенных вершин не осталось, то конец поиска, иначе п.5.

• 
  Слайд 3
  

  Пример Задан граф. Раскрасить по степеням вершин.

• 
  Слайд 4
  
• 
  Слайд 5
  

  1 2 3 10 11 4 12 9 7 5 6 8

• 
  Слайд 6