ГДЗ: § 3 / Граф и способы его задания / Вероятность и статистика 10 класс

Граф — представление объектов и связей между ними с помощью множества точек, некоторые из которых попарно соединены линиями. Точки называются вершинами графа, соединяющие их линии — рёбрами. Вершины и рёбра при необходимости обозначают буквами или числами.

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

Например, вершины \( a, b, c, d \) и рёбра \( ab, bc, cd, ac \) (квадрат \( abcd \) без стороны \( ad \), но с диагональю \( ac \)). Матрица смежности:

Матрица симметрична относительно диагонали, на диагонали стоят нули (петель нет), число единиц равно удвоенному числу рёбер: 8 = 2 · 4.

В ориентированном графе на каждом ребре указано направление (стрелка): по ребру можно двигаться только от начала к концу, как по дороге с односторонним движением. В неориентированном графе направления нет. Матрица смежности неориентированного графа симметрична, ориентированного — в общем случае нет: 1 стоит в строке начала и столбце конца ребра.

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

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

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

Степень вершины — количество рёбер, проведённых из этой вершины. Вершина степени 0 называется изолированной.

От 0 (изолированная вершина) до \( 12 - 1 = 11 \) (вершина соединена со всеми остальными). Причём в одном графе степени 0 и 11 одновременно встретиться не могут.

Нет. Вершина степени 2 в простом графе с тремя вершинами должна быть соединена с обеими другими вершинами, в том числе с вершиной степени 0, а та не соединена ни с кем. Противоречие. Это частный случай теоремы 1: у простого графа всегда есть две вершины одинаковой степени.

Нет. По теореме 2 сумма степеней всех вершин равна удвоенному числу рёбер, то есть всегда чётна, а 13 — нечётное число.

Каждое ребро добавляет по единице к степеням двух своих концов, поэтому сумма степеней равна \( 2 \cdot 10 = 20 \).

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

Цепь — путь, в котором ни одно ребро не повторяется (вершины повторяться могут). Например, для графа на рисунке 38 пути \( abcdeg \) и \( bcfba \) — цепи, а путь \( abaf \) — нет, так как ребро \( ab \) проходится дважды.

Цикл — цепь, у которой начальная и конечная вершины совпадают (замкнутая цепь). Рёбра в цикле не повторяются; если не повторяются и вершины (кроме начальной и конечной), цикл называется простым. Замкнутый путь \( aba \) циклом не является: ребро \( ab \) в нём повторяется.

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

Эйлеров цикл в связном графе (или мультиграфе) существует тогда и только тогда, когда все вершины графа имеют чётные степени. Дополнение: если ровно две вершины имеют нечётную степень, то эйлерова цикла нет, но есть эйлеров путь, начинающийся в одной из нечётных вершин и заканчивающийся в другой.