Как видите, иногда графы позволяют очень просто решать довольно хитри обычные задачи. ? Вопросы 1 Вспомните, где вам встречались графы. 2 Как называются линии, связывающие вершины графа? 3 Как можно проверить, одинаковы два графа или нет? Задачи 116 На рисунке 19 изображены графы. Сколько у каждого из них рёбе изолированных вершин? 117 Одинаковы ли графы, изображённые на рисунке 20? 118 Нарисуйте три разных графа, в каждом из которых з вершины.

Вопросы

1. Вспомнить, где встречались графы: графы используются для представления различных сетей, например, дорожных сетей, социальных сетей, электрических цепей и т.д.
2. Линии, связывающие вершины графа, называются рёбрами или дугами.
3. Проверить, одинаковы ли два графа, можно сравнив их матрицы смежности или списки смежности. Если они совпадают после перенумерации вершин, то графы одинаковы.

Задачи

1. Задача 116:

   На рисунке 19 изображены два графа: a) и б).

   • Граф a): 0 изолированных вершин и 5 ребер.
   • Граф б): 2 изолированные вершины и 5 ребер.
2. Задача 117:

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

3. Задача 118:

   Пример трех разных графов, в каждом из которых 3 вершины:

   • Граф 1: Три вершины, не соединенные ребрами (три изолированные вершины).
   • Граф 2: Три вершины, соединенные в линию (две смежные вершины и одна изолированная).
   • Граф 3: Три вершины, соединенные в треугольник (все вершины смежные).