Выпиши отсюда все определения так, чтобы я смогла списать контрольную работу по…

На фото только задачи (–), готовых определений там нет. Ниже собраны определения и факты, которые нужны для этих задач.

Основные понятия

1. Граф — набор точек (вершин) и линий (рёбер), которые соединяют некоторые пары вершин.
2. Вершина графа — точка. Ребро — линия, соединяющая две вершины.
3. Степень (валентность) вершины — число рёбер, выходящих из этой вершины. Вершина чётная, если её степень чётная, и нечётная, если степень нечётная.
4. Взвешенный граф (схема дорог, таблица расстояний, задачи , , ) — граф, у рёбер которого указаны числа (длины, протяжённости).

Пути, цепи, циклы
. Путь — последовательность вершин, в которой каждые две соседние вершины соединены ребром.
. Цепь — путь, в котором ни одно ребро не повторяется (и не повторяются вершины). Длина цепи — число её рёбер.
. Цикл — цепь, у которой первая и последняя вершины совпадают. Длина цикла — число его рёбер.
. Простой цикл — цикл, в котором все вершины, кроме первой и последней, различны, то есть никакая вершина не проходится дважды.
. Кратчайший путь между двумя вершинами (задачи , , ) — путь с наименьшей суммарной длиной рёбер. Длина пути во взвешенном графе — сумма длин его рёбер.

Связность
. Связный граф — граф, в котором от любой вершины можно дойти до любой другой по рёбрам.

Важные факты для задач

• Сумма степеней всех вершин равна удвоенному числу рёбер: .
• Число вершин нечётной степени в любом графе всегда чётно. Из этого следует:
  • задача : вершин с нечётной валентностью может быть только чётное число;
  • задача : вершин с нечётной степенью (по друга и по друзей) , число нечётное, значит, так быть не может;
  • задача : вершин нечётной степени чётное число, поэтому граф, где больше вершин и все они нечётные, должен иметь чётное число вершин, например .
• Задача : каждый мальчик дружит с девочками, каждая девочка с мальчиками. Число рёбер , значит, делится на , а делится на . Тогда , , всего человек. Условие «больше и меньше » даёт при , но не меньше . Значит, при получается , что не больше . Подходящего числа нет, возможно, в условии опечатка (число должно быть кратно ).