Основы дискретной математики. Щипцов В.В - 5 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

5
Введение
В настоящее время наряду с традиционными разделами классической
математики, применяемыми в различных сферах деятельности человеческого
общества, широкое распространение получили методы дискретной математики,
составными частями которой являются: теория графов, алгебра логики,
формальные языки и дискретные автоматы. Эти методы очень важны,
например, при разработке различных технических устройств и систем с
дискретным принципом действия, а также в планировании, при решении ряда
транспортных задач, при изучении функционирования “ малых групп” в
социологии и социальной психологии и многое другое.
Глава 1. Элементы теории графов
§1.1 Определения. Классификация задач теории графов
В дискретной математике важное место занимают задачи, связанные с
упорядочением тех или иных объектов, а также задачи, в которых изучаются
отношения между различного рода объектами. Приведем в качестве примера
несколько таких задач.
1. Нанести некоторую схему на печатную плату таким образом, чтобы
любые два проводника не пересекались между собой ни в каких точках (узлах),
кроме данных.
2. Указать для почтальона такой маршрут, чтобы пройденное им
расстояние было минимальным.
3. Для имеющейся сети шоссейных дорог, соединяющих данные
населенные пункты, указать маршрут между двумя любыми заданными
пунктами, который обеспечил бы максимальный транспортный поток между
ними.
Задачи такого рода удобно формулировать и решать, пользуясь
рисунком, состоящим из точек (вершин) и отрезков (ребер или дуг),
соединяющих эти вершины. Структуры такого типа объединяются названием -
графы, а изучающий их раздел дискретной математики носит название теории
графов. Приведем ряд определений и понятий, связанных с графами
.
Определение графа
Пусть задано некоторое конечное множество X = x
1
, x
2
, ... , x
n
,
элементы которого будем называть
вершинами
. Образуем из него новое
множество U = u
1
, u
2
, ... , u
m
, состоящее из пар элементов ( x
i
, x
j
)
множества X . Будем при этом различать два случая :
а) когда безразлично в каком порядке берутся вершины при образовании
из них пар; в этом случае пара (x
i
, x
j
) ( или (x
j
, x
i
) - все равно) называется
ребром, соединяющим вершины x
i
и x
j
;

Страницы