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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск по сайту: