Контрольные задания > На карте области 5 стран. Нужно раскрасить их так, чтобы соседние страны (имеющие общую границу) были разного цвета. Постройте граф соседства (вершина — страна, ребро — соседство) по описанию: Страна 1 граничит с 2, 3, 5. Страна 2 граничит с 1, 3, 4. Страна 3 граничит с 1, 2, 4, 5. Страна 4 граничит с 2, 3. Страна 5 граничит с 1, 3. Какое минимальное количество цветов потребуется? (Подсказка: попробуйте раскрасить последовательно).
Вопрос:

На карте области 5 стран. Нужно раскрасить их так, чтобы соседние страны (имеющие общую границу) были разного цвета. Постройте граф соседства (вершина — страна, ребро — соседство) по описанию: Страна 1 граничит с 2, 3, 5. Страна 2 граничит с 1, 3, 4. Страна 3 граничит с 1, 2, 4, 5. Страна 4 граничит с 2, 3. Страна 5 граничит с 1, 3. Какое минимальное количество цветов потребуется? (Подсказка: попробуйте раскрасить последовательно).

Смотреть решения всех заданий с листа

Ответ:

Граф соседства:

  • Вершины: 1, 2, 3, 4, 5 (страны)
  • Рёбра: (1,2), (1,3), (1,5), (2,3), (2,4), (3,4), (3,5)

Раскраска графа:

  1. Страна 1: Цвет 1
  2. Страна 2: Соседствует с 1 (Цвет 1), поэтому Цвет 2
  3. Страна 3: Соседствует с 1 (Цвет 1) и 2 (Цвет 2), поэтому Цвет 3
  4. Страна 4: Соседствует с 2 (Цвет 2) и 3 (Цвет 3), поэтому Цвет 1
  5. Страна 5: Соседствует с 1 (Цвет 1) и 3 (Цвет 3), поэтому Цвет 2

Ответ: Минимальное количество цветов — 3.

ГДЗ по фото 📸
Подать жалобу Правообладателю

Похожие