Реши задание на изображении
1. Хроматическое число графа
Ответ: \(\chi(G)=3\).
Внешние вершины \(a_1,a_2,a_3,a_4,a_5\) образуют цикл длины 5. Его нельзя раскрасить в два цвета, поэтому нужно не меньше трёх цветов.
Трёх цветов достаточно. Например, можно задать цветовые классы так:
- цвет 1: \(a_1,a_3,a_9,a_{10}\);
- цвет 2: \(a_2,a_4,a_6\);
- цвет 3: \(a_5,a_7,a_8\).
На каждом ребре концы имеют разные цвета. Значит, граф раскрашивается в три цвета, и \(\boxed{\chi(G)=3}\).
2. Гамильтонов цикл минимального веса
Ответ: граф гамильтонов; минимальный цикл — \(1-2-5-4-3-1\), его вес равен \(11\).
Значение \(\infty\) в матрице означает, что ребра нет. Переберём допустимые гамильтоновы циклы, считая циклы, проходящие в обратном направлении, одинаковыми:
\[ \begin{array}{c|c} \text{Цикл} & \text{Вес}\\ \hline 1-2-3-4-5-1 & 1+2+1+3+5=12\\ 1-2-5-4-3-1 & 1+4+3+1+2=11\\ 1-3-2-4-5-1 & 2+2+3+3+5=15\\ 1-3-4-2-5-1 & 2+1+3+4+5=15 \end{array} \]
Все вершины в цикле \(1-2-5-4-3-1\) встречаются по одному разу, и его вес наименьший. Поэтому минимальный гамильтонов цикл имеет вес \(\boxed{11}\).
Обсуждение
2 сообщенияПокажи как делать первое с рисунком и что нужно сделать как в школе коллеж
Первое задание: найти хроматическое число графа
Нужно раскрасить вершины графа так, чтобы соседние вершины имели разные цвета, и найти минимальное количество цветов.
Обозначим цвета:
- 🟥 — красный;
- 🟦 — синий;
- 🟩 — зелёный.
1. Раскрашиваем вершины
По рисунку можно использовать такую раскраску:
| Вершина | Цвет |
|---|---|
| \(a_1\) | 🟥 |
| \(a_2\) | 🟦 |
| \(a_3\) | 🟥 |
| \(a_4\) | 🟦 |
| \(a_5\) | 🟩 |
| \(a_6\) | 🟦 |
| \(a_7\) | 🟩 |
| \(a_8\) | 🟩 |
| \(a_9\) | 🟥 |
| \(a_{10}\) | 🟥 |
То есть на исходном рисунке нужно закрасить:
\[ \begin{aligned} \text{красным: }& a_1,a_3,a_9,a_{10};\\ \text{синим: }& a_2,a_4,a_6;\\ \text{зелёным: }& a_5,a_7,a_8. \end{aligned} \]
Схематично внешняя часть графа выглядит так:
a1 🟥
/ \
a5 🟩 a2 🟦
| |
a4 🟦 ------------- a3 🟥
Это только схема внешнего пятиугольника; остальные вершины \(a_6,\ldots,a_{10}\) закрашиваются указанными цветами на самом рисунке.
2. Почему двух цветов недостаточно?
Внешние вершины образуют цикл из пяти вершин:
\[ a_1-a_2-a_3-a_4-a_5-a_1. \]
Если использовать только два цвета, получится:
\[ a_1\text{ — красная},\quad a_2\text{ — синяя},\quad a_3\text{ — красная},\quad a_4\text{ — синяя}. \]
Тогда \(a_5\) должна быть красной, чтобы отличаться от \(a_4\). Но \(a_5\) соединена с \(a_1\), а они обе красные. Получается противоречие.
Значит, двух цветов недостаточно:
\[ \chi(G)\geq 3. \]
3. Вывод
Мы показали, что граф можно раскрасить тремя цветами, но двумя цветами нельзя. Поэтому
\[ \boxed{\chi(G)=3}. \]
Ответ: хроматическое число графа равно \(3\).
