Листок 1. Графы в нашей жизни, парные отношения. Теория.

Листок 1. Графы в нашей жизни, парные отношения. Теория.

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

1) Страны - вершины графа, рёбра – наличие общей границы;

2) Люди – вершины графа, рёбрами связаны те, кто знакомы между собой;

3) Атомы в молекуле – вершины графа, химические связи – рёбра графа;

4) Последовательности действий: узлы – состояния, рёбра – действия.

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

Графы для электрических цепей часто являются мультиграфами. Мультиграф – это граф, в котором некоторые пары вершин соединены более чем одним ребром.

Петля – это ребро, соединяющее вершину графа саму с собой. Граф с петлями называется псевдографом. Граф связный, если от каждой вершины можно дойти до любой.

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

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

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

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

Графы могут быть использованы для изображения любых парных отношений, но чаще всего они используются для следующих видов:

1) Отображения из одних множеств в другие, перестановки;

2) Иерархии, каталоги, свойства;

3) Последовательности действий, направленные пути;

4) Связи и соединения.

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

Сюръекция – отображение, при котором каждый элемент первого множества переводится в какой-нибудь элемент другого множества.

Инъекция – отображение, при котором разные элементы первого множества переводятся в разные элементы второго.

Биекция – взаимно-однозначное отображение.

Листок 1. Графы в нашей жизни. Задачи.

1. Дети, наблюдая за фокусником и его волшебной шляпой, заметили, что

a) если он кладёт в шляпу платок, то через минуту вынимает оттуда шар;

b) если он кладёт в шляпу шар, то через минуту вынимает оттуда кролика;

c) если он что-то вынимает из шляпы, то через минуту машет палочкой;

d) если он машет палочкой, то через минуту достаёт из кармана платок;

e) если он достаёт из кармана платок, то через минуту кладёт его в шляпу;

f) если он вынимает из шляпы кролика, то через минуту достаёт из кармана шар;

g) если он достаёт из кармана шар, то через минуту кладёт его в шляпу;

Сейчас фокусник достал из кармана шар, что он будет делать через 7 минут?

Упражнение. Какие из нарисованных ниже графов одинаковы?

А	B	С	D	Е
F	G	H

1. На шахматной доске 3х3 стоят два черных и два белых коня (см. рис.)

Как поменять черных и белых коней местами за наименьшее число ходов?

(*) Докажите, что число ходов не может быть меньше.

Указание 1.

Нарисовать и слепить граф соединений клеток между собой ходом коня.

Указание 2.

Часть клеток внутри доски можно вынести за пределы её, не изменив граф соединений.

3. К предыдущей задаче – можно ли поменять коней так, белые кони стояли в верхнем левом и нижнем правых углах, а чёрных – в двух остальных?

4. Кузнечик умеет прыгать только ровно на 50 см. Он хочет обойти 8 точек, отмеченных на рисунке (сторона клетки равна 10 см). Какое наименьшее количество прыжков ему придётся сделать? (Разрешается посещать и другие точки плоскости, в том числе вне сетки. Начинать и заканчивать можно в любых точках).

Дата добавления: 2015-10-21