1 Чему равно хроматическое число приведенного графа?
2.Во Сколько ребер содержит паросочетание наибольшего размера в приведённом графе?
3.Во Чему равен размер наименьшего вершинного покрытия в приведенном графе?
4.Во Чему равно число независимости приведенного графа?
5.Во Сколько вершин содержит самый длинный цикл в приведенном графе?
6.Во Содержит ли граф подграфы, гомеоморфные K_5 и K_ { 3,3 }

7.Во Чему равна величина ex(19,G), где G - это граф, приведенный на картинке?
8.Во Чему равно наибольшее число k, для которого граф, приведенный на картинке, является k-связным?
9.Во Чему равно наименьшее число ребер, которое нужно удалить из приведенного графа, чтобы сделать его двудольным?

1. Чтобы определить хроматическое число приведенного графа, нужно найти минимальное число цветов, которыми можно раскрасить все вершины графа таким образом, чтобы никакие две смежные вершины не имели одинакового цвета. Можно использовать жадный алгоритм для раскрашивания графа. За начальный шаг можно взять первую вершину и окрасить ее в цвет номер 1. Затем рассматриваем следующую нераскрашенную вершину. Если она не имеет смежных вершин, окрашенных тем же цветом, то окрашиваем ее в цвет номер 1. Иначе выбираем наименьший номер цвета, отличный от цветов смежных вершин, и окрашиваем вершину в этот цвет. Повторяем этот процесс для всех нераскрашенных вершин и получаем конечное число цветов, которым можно раскрасить граф.

2. Паросочетание наибольшего размера в графе – это наибольшее множество ребер, такое что никакие два ребра не имеют общей вершины. Количество ребер в паросочетании наибольшего размера – это максимальное количество ребер, которые можно выбрать без образования ребер пересекающихся. Это может быть найдено с помощью различных алгоритмов, таких как алгоритм Макса-Флетчера.

3. Размер наименьшего вершинного покрытия в графе – это наименьшее количество вершин, такое что каждое ребро графа имеет хотя бы одну конечную вершину в вершинном покрытии. Существуют различные алгоритмы для нахождения размера наименьшего вершинного покрытия.

4. Число независимости приведенного графа – это наибольшее количество вершин, такое что никакие две из них не связаны ребром. Чтобы найти число независимости графа, можно использовать жадный алгоритм. Начиная с пустого множества независимости, добавляем по одной вершине, пока это возможно, то есть пока добавление новой вершины не приводит к появлению ребра между какими-либо двумя вершинами уже в множестве. Таким образом, число вершин в множестве независимости будет равно числу независимости графа.

5. Для нахождения самого длинного цикла в графе следует использовать поиск в глубину или другие алгоритмы обхода графа. Можно начать с каждой вершины и найти все возможные циклы, сохраняя максимальную длину. Таким образом, найденный цикл будет иметь наибольшую длину среди всех циклов в графе.

6. Чтобы определить, содержит ли граф подграфы, гомеоморфные K_5 и K_{3,3}, можно рассмотреть определение гомеоморфизма. Граф G содержит подграф, гомеоморфный K_5, если в нем можно найти 5 вершин и можно провести ребра между всеми парами этих вершин без пересечения ребер. Аналогично, граф G содержит подграф, гомеоморфный K_{3,3}, если в нем можно найти 6 вершин, разделенных на 2 группы по 3 вершины, и можно провести ребра между вершинами разных групп без пересечения ребер. Следовательно, чтобы определить, содержит ли граф G указанные подграфы, нужно проверить его структуру на присутствие указанных свойств.

7. Величина ex(19,G) - это максимальное количество ребер в графе G без треугольников (циклов размера 3). Для нахождения этого числа, нужно исследовать граф G и искать максимальную клику (полный подграф) без треугольников. После нахождения этой клики, можно добавить к ней ребра, чтобы получить новые треугольники. Таким образом, величина ex(19,G) будет равна размеру максимальной клики в графе G.

8. Чтобы определить, является ли граф G k-связным, нужно найти наименьшее число вершин, которые при удалении делают граф несвязным или снимают его связность на k компонент. Это может быть найдено с помощью алгоритма Форда-Фалкерсона или других алгоритмов поиска максимального потока в графе.

9. Чтобы сделать граф двудольным путем удаления наименьшего числа ребер, можно использовать алгоритм Бержа. Этот алгоритм применяется для проверки, можно ли раскрасить граф двумя цветами таким образом, чтобы соседние вершины имели разные цвета. Если удалить наименьшее число ребер, чтобы граф стал двудольным, это будет означать, что в графе не будет циклов нечетной длины.