Граф. Вершины и рёбра графа

Ребята, перед вами несколько схем.

Первая схема представляет собой родословное дерево потомков Льва Николаевича Толстого – выдающегося русского писателя, публициста, мыслителя. Рядом вы видите схему молекулы глюкозы (одного из основных источников энергии для организма). Затем идёт электрическая схема утюга и схема линий метрополитена Санкт-Петербурга. Каждая из этих схем показывает связь между отдельными элементами. В родословном дереве линия идёт от отца к сыну (или дочери). Схема молекулы показывает, в каком порядке связаны между собой атомы углерода, водорода и кислорода. На схеме метро связи – это перегоны между соседними станциями. А электрическая схема утюга показывает, как соединить между собой детали, чтобы получился работающий прибор.

В математике для изображения и изучения связей между различными объектами применяется граф. Слово «граф» в переводе с греческого языка означает «пишу, черчу, рисую».

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

Если вершина является концом ребра, то говорят, что ребро исходит из этой вершины или что оно входит в неё.

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

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

Теперь посмотрите на два графа, которые получены друг из друга «движением вершин».

Эти графы считают одинаковыми, так как в графе важны только сами вершины и связи. А вот взаимное расположение вершин не важно.

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

Посмотрите на такие графы.

И в одном, и в другом графе рёбра одни и те же. Вершины этих двух графов связаны одинаково, а значит, графы одинаковы. Вот только второй граф можно назвать более удобным, ведь посмотрев на него, мы сразу видим, что он состоит из двух не связанных частей.

Отметим, что при решении задач нужно стараться изображать графы как можно проще и яснее. Давайте убедимся в этом на примере.

На острове расположены шесть городов: А, Б, В, Г, Д и Е. Известно, что дорога проложена между городами А и Б, между городами А и Г, между городами Б и Г, между городами Б и Д, между городами В и Г, между городами В и Е и между городами Г и Д. Может ли житель города А попасть в город Е, если ему нельзя проходить через город Г?

Чтобы ответить на вопрос, построим граф. Города изобразим вершинами, а дороги – рёбрами.

Посмотрев внимательно на получившийся граф становится понятно, что житель города А не сможет попасть в город Е, если ему нельзя проходить через город Г.

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

Задание первое. На рисунке изображены графы. Сколько у каждого из них рёбер, вершин, изолированных вершин?

Решение. Первый граф. У него 5 рёбер и 5 вершин, одна из которых изолированная.

Второй граф. У него 6 рёбер и 9 вершин, три из которых изолированные.

Задание второе. Выясните, одинаковы ли графы, изображённые на рисунке.

Решение. Давайте внимательно посмотрим первые два графа. У каждого из них по 5 вершин. А вот количеством рёбер данные графы отличаются: у одного из них 8 рёбер, а у другого только 5. Если у графов отличается число вершин или число рёбер, то, очевидно, они не могут быть одинаковыми. Следовательно, данные графы не одинаковы.

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

Задание третье. Нарисуйте 4 разных графа, в каждом из которых 4 вершины.

Решение.

Друзья, на этом мы закончим наше занятие. До встречи на следующих занятиях!