Некоторые определения и понятия теории графов

ЛЕКЦИЯ 1

Введение

АНАЛИЗА ТЕКСТОВ

ПРАКТИКУМ ПО РАЗВИТИЮ НАВЫКОВ ЧТЕНИЯ И

Резько Петр Васильевич

Нарчук Александр Петрович

по курсу “История немецкого языка” (для студентов II курса

специальности “немецкий язык”)

Подписано к печати 20.Х.1999 г. Формат 60 x 84 1 / 16

Бумага писчая № 1 Печать офсетная Усл. п. л. 4,18

Уч. изд. л. 3,5 Тираж 100 экз. Заказ 57

Отпечатано в РИК ГГУ им. Ф. Скорины

г. Гомель, ул. Советская, 104

Комбинаторика раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбинаторных конфигураций. Это изучение включает в себя вопросы существования комбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задач перечисления, в частности определение числа конфигураций данного класса. Простейшим примером комбинаторных конфигураций являются перестановки, сочетания и размещения. Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (диссертация Комбинаторное искусство), Я. Бернулли (работа Искусство предположений), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейбница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций методу производящих функций. Возвращение интереса к комбинаторному анализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам. Классические комбинаторные задачи это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок. Например, в 1859 г. У. Гамильтон придумал игру Кругосветное путешествие, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа. Это одна из самых известных задач комбинаторики - задача коммивояжера.

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

Дата добавления: 2014-12-27