Самостоятельная работа. «Графы. Вершины и рёбра» Вариант – 1. № 1. На рисунке 1. изображены одинаковые графы или различные? Почему? № 2. На рисунке 2 изображен граф. Сколько у него рёбер; вершин? № 3. В стране Врунляндия есть шесть городов и шесть дорог: дорога между городами Андерск и Бремен, дорога между городами Андерск и Враль, между городами Бремен и Враль, между городами Обманк и Зевак, между Бремен и Лжецк и между Враль и Лжецк. Можно ли по дорогам пройти с города Бремен в город Обманк. (Задачу решите с помощью графа)

Решение:

№ 1.

На рисунке 1 изображены два одинаковых графа. Они имеют одинаковое количество вершин (по 4) и одинаковое количество рёбер (по 5). Также у них одинаковая структура связей между вершинами.

№ 2.

На рисунке 2 изображен полный граф с 5 вершинами. В нём:

• вершин: 5
• рёбер: 10 (каждая вершина соединена с 4 другими, всего 5*4 = 20, но каждое ребро учтено дважды, поэтому 20 / 2 = 10)

№ 3.

Для решения построим граф, где города — вершины, а дороги — рёбра.

• Вершины: Андерск (А), Бремен (Б), Враль (В), Обманк (О), Зевак (З), Лжецк (Л).
• Рёбра: (А, Б), (А, В), (Б, В), (О, З), (Б, Л), (В, Л).

Построим граф: