WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:   || 2 |

«РАБОЧАЯ ПРОГРАММА по дисциплине Дискретная математика Направление подготовки 230100.62 Информатика и вычислительная техника Факультет переподготовки инженерных кадров ...»

-- [ Страница 1 ] --

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Волгоградский государственный технический университет»

Факультет электроники и вычислительной техники

Кафедра «Системы автоматизированного проектирования

и поискового конструирования»

УТВЕРЖДАЮ

Проректор по учебной работе ВолгГТУ А.М. Дворянкин «_»_ 2011 г.

РАБОЧАЯ ПРОГРАММА

по дисциплине «Дискретная математика»

Направление подготовки 230100.62 «Информатика и вычислительная техника»

Факультет переподготовки инженерных кадров Заочная форма обучения Курс Семестр Число зачетных единиц Всего часов по учебному плану Всего часов аудиторных занятий Лекции, час. Лабораторные работы, час. Форма итогового контроля по дисциплине экзамен Волгоград Рабочая программа составлена на основании ФГОС ВПО и учебного плана бакалавриата по направлению 230100.62 «Информатика и вычислительная техника», утвержденного приказом ректора ВолгГТУ.

Составитель рабочей программы канд. техн. наук, доцент Н.П.Садовникова Рабочая программа одобрена на заседании кафедры «Системы автоматизированного проектирования и поискового конструирования».

Протокол от «15» сентября 2011 г. № Заведующий кафедрой д-р техн. наук, профессор В.А. Камаев Одобрено научно-методическим советом ФПИК Протокол от «_» _ 20_ г. № _ Председатель НМСФ, декан ФПИК, д-р техн. наук, профессор А.Н. Савкин

1. ЦЕЛИ И ЗАДАЧИ УЧЕБНОЙ ДИСЦИПЛИНЫ

1.1. Цель преподавания дисциплины Целью дисциплины является формирование у будущего специалиста теоретических знаний и практических навыков по применению дискретной математики в профессиональной деятельности.

1.2. Задачи изучения дисциплины В процессе изучения курса студент должен:

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

- научиться выполнять операции над множествами, определять свойства отношений и операции, идентифицировать графы, преобразовывать и минимизировать переключательные функции;

- получить математическую основу для формализации и решения прикладных задач.

1.3. Взаимосвязь учебных дисциплин Дисциплина относится к циклу математических и общих естественнонаучных дисциплин. Изучение данной дисциплины базируется на курсах " Линейная алгебра и аналитическая геометрия», "Математический анализ", "Информатика". Основные положения дисциплины используются в дальнейшем в курсах "Математическая логика и теория алгоритмов", "Технология программирования", "Программирование на языках высокого уровня", «Моделирование систем», «Методы оптимизации», «Основы трансляции», «Теория автоматического управления» и др.





1.4. Компетенции, формируемые в результате освоения учебной дисциплины Общекультурные компетенции (ОК):

ОК-6 стремится к саморазвитию, повышению своей квалификации и мастерства;

ОК -10 использует основные законы естественнонаучных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования;

ОК-11 осознает сущность и значение информации в развитии современного общества; владеет основными методами, способами и средствами получения, хранения, переработки информации;

Перечисленные выше компетенции предполагают следующие знания, умения и навыки.

Студент должен знать:

знать основные определения и понятия изучаемых разделов дискретной математики;

классы задач дискретной математики, необходимые для анализа методы решения задач теории множеств, теории графов, комбинаторики;

Студент должен уметь:

применять изученные методы для решения практических задач;

Студент должен иметь навыки:

решения типичных заданий, решаемых на основе изучаемого теоретического материала 2. СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ "Дискретная математика" Таблица 2.1- Содержание учебной дисциплины "Дискретная математика" множество. Универсальное множествами. Конечные и бесконечные множества.

Эквивалентность множеств.

Отображение множеств. Свойства отображений. Отношения и их свойства. Разбиение множества на Бинарные отношения. Отношения Свойства действий. Простейшие алгебраические системы. Подгруппы. конечные группы. Кольца, тела ентированные графы Элементы собы задания графов. Матрица инОК- циденций, матрица соседства вершин. Геометрическая реализация графа. Степень вершины. Цепь и путь цикл и контур. Связность графа.

представлении графа как дерева.

Теорема о сумме степеней графа.

Изоморфизм графов. Отношение порядка и отношение эквивалентности на графе.

произведения. Размещения с повторениями. Размещения без повторений. Перестановки. Сочетания. Сочетания с повторениями.

Полиноминальная формула. Метод рекуррентных соотношений.

Кр – контрольная работа, Ко – контрольный опрос, Эк - экзамен

3. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ДИСЦИПЛИНЫ

Таблица 3.1- Практические занятия 1 Операции над множествами. Конечные и бесконечные 2 Графы и их основные свойства. Маршруты, цепи, циклы, связность.

3 Деревья. Ориентированные, упорядоченные и бинарные деревья. Обходы бинарных деревьев. Кратчайший 4 Решение задач на нахождение Эйлеровых и гамильтоновых циклов в графе. Построение матрицы циклов 5 Элементы комбинаторики. Перестановки, сочетания, размещения. Рекуррентные соотношения Студенту необходимо выполнить одну контрольную работу, состоящую из восьми задач по темам «Теория множеств», «Теория графов», «Деревья», «Элементы комбинаторики»





3.2. Организуемая самостоятельная работа студентов (ОргСРС) Самостоятельная работа студентов заключается в изучении рекомендуемой литературы согласно разделам рабочей программы, решении типовых задач, выполнении контрольной работы.

Студенту необходимо выполнить одну контрольную работу, состоящую из восьми задач по темам «Теория множеств», «Теория графов», «Деревья», «Элементы комбинаторики»

Таблица 3.2 - Самостоятельная работа студентов 3.2 Основная и дополнительная литература 3.2.1 Основная литература 1. Дискретная математика : конспект лекций : учеб. пособие / Муха Ю. П., Авдеюк О. А. ; ВолгГТУ. - 2-е изд., стер. - Волгоград : РПК "Политехник", 2007. - 104 с.;

2. Авдеюк, О. А. Теория графов. Конспект лекций для студентов заочного отделения : учеб. пособие / О. А. Авдеюк. – Волгоград : ИУНЛ ВолгГГУ, 2011. –76 с. ;

3. Новиков, Ф. А. Дискретная математика для программистов/ Учеб. для вузов / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. - 364 с. 3.2. 3.2.2 Дополнительная литература 1. Бовда, Н. Д.Дискретная математика [Текст] : курс лекций : учеб. пособие. Ч. 1 / Н. Д. Бовда ; ВолгГТУ. - Волгоград : РПК "Политехник", 2005. - 96 с.;

2. Спирина, М. С.Дискретная математика [Текст] : учебник / М. С. Спирина, П. А. Спирин. - М. : Академия, 2004. - 368 с.

3.2.3 Перечень методических указаний 1. Комплект методических указаний к практическим занятиям по дискретной математике (электронный вариант). Режим доступа:

http://edu.vstu.ru/course/, 2. Бовда Н. Д. Дискретная математика. Учебное пособие / ВолгГТУ – Волгоград, 2005г.

4 ПРОТОКОЛ СОГЛАСОВАНИЯ РАБОЧЕЙ ПРОГРАММЫ

Таблица 4.1- Протокол согласования учебной дисциплины Наименование дисци- Наименование ка- Подпись зав.кафедрой, с плин, изучение которых федры, с которой которой проводится соглаопирается на данную проводится согласо- сование рабочей програмдисциплину вание мы, предложения об изменении (если имеются)

5 ЛИСТ ИЗМЕНЕНИЙ И ДОПОЛНЕНИЙ, ВНЕСЕННЫХ В РАБОЧУЮ

ПРОГРАММУ

Таблица 5.1- Лист изменений и дополнений, внесенных в рабочую программу Виды дополнений Дата и номер протоко- Дата утверждения и и изменений ла заседания кафедры, на котором были рас- подпись декана (председасмотрены и одобрены теля НМС) факультета изменения и дополнения. Подпись заведующего кафедрой

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

ДИСКРЕТНАЯ МАТЕМАТИКА

I. Основы теории множеств

II. Отношения. Функции

III. Алгебраические действия общего типа

IV. Элементы теории графов

V. Деревья

VI. Элементы комбинаторики

Понятие множества. Способы задания множеств. Операции над множествами.

Диаграмма Эйлера-Венна. Конечные и бесконечные множества. Эквивалентность множеств.

Отображение множеств. Свойства отображений.

Под множеством обычно понимают совокупность определенных и хорошо различимых объектов, которые рассматриваются как единое целое. Объекты, составляющие множество, называются его элементами. Тот факт, что x является элементом множества M, записывается так: x M, где символ обозначает отношение принадлежности элемента множеству. Если x не является элементом множества M, то пишут: x M.

Множества, состоящие лишь из конечного числа элементов, называются конечными множествами.

В математике часто приходится сталкиваться с другими – не конечными, или, как принято говорить, бесконечными множествами. Примерами бесконечных множеств могут послужить числовые множества:

Примеры числовых множеств:

1) – множество всех натуральных чисел – {1,2,3, …};

2) – множество всех целых чисел – {…,-2,-1,0,1,2,…};

3) – множество рациональных чисел (это числа, которые могут быть представлены в виде дроби, числитель которой – целое число, а знаменатель – натуральное, т.е. x=a/b, где aцелое, b-натуральное);

4) – множество вещественных (действительных) чисел (это все рациональные и иррациональные числа);

5) – множество комплексных чисел (это числа, вида х=a+ib, где a и b-вещественные, i– мнимая единица: i2= -1);

6) 2 – множество всех упорядоченных пар вещественных чисел (x,y), – вся вещественная плоскость;

7) n – n-мерное вещественное пространство, где n – натуральное число, – множество всех упорядоченных последовательностей из n вещественных чисел («энок») или n-мерное вещественное пространство.

Множество, не содержащее ни одного элемента, называется пустым и обозначается.

Пустое множество конечно. Число элементов в пустом множестве равно нулю.

Способы задания множества Все элементы некоторого определенного множества обладают некоторым свойством, общим для всех элементов этого множества. Например: множество всех четных чисел;

множество всех белых гусей; множество букв русского алфавита. Поэтому для задания множества можно:

1) либо задать свойство, которым должны обладать все его элементы;

2) либо указать (перечислить) все элементы этого множества.

Оба этих подхода, в сущности, представляют одно и то же, разница лишь во внешнем оформлении.

Тот факт, что х является элементом множества М, записывается так: х М. В этом случае говорят, что х входит в М, содержится в М или принадлежит М. Если х не является элементом множества М, то пишут х М.

То, что некоторое множество М состоит из элементов x, y, …, t,… записывают так:

М={x,y,…,t,…}, где многоточием обозначаются не выписанные элементы. Например: A={a,b,c}, M={2,4,6,8,10,…}.

Если элементы множества обозначаются при помощи некоторых индексов, например: х, х,…,х,…, то пишут также: М= х, где =,,…,,… – множество индексов.

(где Г=,,…,,… – индексное множество).

То, что множество состоит из элементов, обладающих некоторым свойством, записывают так: М={x: ………}, где на месте многоточия перечисляют свойства элементов.

Читается это так: «множество М состоит из элементов х, таких, что…». Например: M={x: x=a/2, где а и x }.

Для некоторых числовых множеств имеются свои способы записи:

Отрезок числовой оси: [a, b]={x: a x b, где a,b,x и a b }.

Полуинтервал: (a, b]={x: a x b, где a,b,x и a b }, Два множества называются равными, если они состоят из одних и тех же элементов, т.е.

A=B тогда и только тогда, когда для любого элемента a A следует: a B, и для любого элемента b B следует: b A.

Таким образом, множество однозначно определяется своими элементами и не зависит от порядка их записи. Например, множество из трех элементов a, b и c допускает 6 видов записи:

{a,b,c}= {a,c,b}= {b,a,c}= {b,c,a}= {c,a,b}= {c,b,a}.

Если все элементы множества A являются одновременно элементами множества B, то A называется подмножеством или частью множества B.

Пишут A B или В А, читается: А входит в В, или А содержится в В, или В содержит А, или В покрывает А. Множество В называется в этом случае надмножеством А. Таким образом, A B тогда и только тогда, когда для любого элемента a A следует: a B.

Пустое множество является подмножеством любого множества, а любое множество является одним из своих подмножеств.

Если A B и А В, то А называется собственным подмножеством множества В, а В – собственным надмножеством множества А.

Пишут A B или В А. Таким образом, A B тогда и только тогда, когда для любого элемента a A следует: a B, и существует элемент b B такой, что b A. Символическая запись Множество всех подмножеств данного множества А называется булеаном А и обозначается 2А. Число элементов в булеане конечного множества из n элементов равно 2n.

Множество, являющееся надмножеством любого множества в данном рассуждении, называют универсальным множеством или универсумом и обозначают.

Операции над множествами Объединением двух множеств A и B (или теоретико-множественной суммой) называется множество, состоящее из всех элементов, являющихся элементами хотя бы одного из множеств A или B. Таким образом, Для графического изображения операции объединения множеств используются диаграммы Эйлера-Венна, где множества представлены как замкнутые области, а результат операции показан заштрихованной частью (см. рис.1).

Пересечением двух множеств A и B (или теоретико-множественным произведением) называется множество элементов, принадлежащих одновременно и A, и B. Таким образом, Диаграмма Эйлера-Венна для пересечения двух множеств показана на рис.2.

Относительным дополнением множества B до множества A (или элементов A, которые не являются элементами B, таким образом, A \ B {x : x Абсолютным дополнением множества A называется множество всех A U \ A, где U – некоторое универсальное множество, которое является рассуждении. Диаграмма на рис.4.

Симметрической разностью двух множеств A и B называется объединение двух разностей A \ B и B \ A, т.е. A B= (A \ B) (B \ A).

Диаграмма на рис.5.

Декартовым (прямым) произведением двух множеств A и B называется множество всех упорядоченных последовательностей Множества A и B в прямом произведении А В называют координатными осями, а элементы x А и y В – проекциями вектора z=(x,y) А В на координатные оси или координатами точки z (абсциссой и ординатой соответственно). Будем обозначать их прА z и прВ z.

Пусть множество М А В, проекцией множества М на ось А называется множество всех абсцисс векторов из М, проекцией множества М на ось В называется множество всех ординат векторов из М, т.о. прА М={ прА z: z М}={x А: y В и (x,y) М} и прВ М={ прВ z: z М}={y В:

x А и (x,y) М}.

Для многомерного случая A1 A2 A3 … An, каждое множество Ai называется i-той координатной осью. Проекция вектора z=(a1, a2,…, an) на i-тую координатную ось равна его iтой координате: прi z=ai, где i=1,2,…,n. Если М A1 A2 … An, то прi М={ прi z: z М}.

Определены также проекции вектора z и множества векторов М на несколько координатных прi1, i2…ik М = { прi1, i2…ik z: z М } – множество k-мерных векторов.

(или вектор, проведенный в эту точку из начала координат). Тогда прi (а1, а2, а3)=ai, где i=1,2,3, Бинарные отношения. Отношения эквивалентности и упорядоченности. Диаграммы Бинарные отношения N–местным отношением или n–местным предикатом Р на множествах A1,A2,,An, называется любое подмножество декартова произведения A1 A2 An. При n=2 отношение называется бинарным. Бинарные отношения чаще рассматриваются, как отношения между элементами одного и того же множества. Пусть это множество М, тогда Р M M={(х,у):

х,у M}.

То, что два элемента х и у находятся в отношении Р, записывается так: (х,у) Р или хРу или х~у(Р) – читается: «х находится с у в отношении Р». В некоторых случаях может использоваться также запись вида: y=Р(x), и соответствующая терминология: y является образом x относительно Р и x является прообразом y относительно Р. Если Р А В, то множество всех образов элементов x A называют образом множества А в множестве В и обозначают Р(А)={y B: x A и y=Р(x)}. Множество всех прообразов элементов y B называют прообразом множества В в множестве А и обозначают Р-1(В)={x A: y B и y=Р(x)}.

Отношение эквивалентности эквивалентности или просто эквивалентностью, если оно рефлексивно, транзитивно и симметрично. Для обозначения этого отношения чаще используется запись a b без указания Р.

Значение этого отношения заключается в том, что с помощью него множество разбивается в объединение попарно непересекающихся подмножеств (классов эквивалентности).

Пусть « » – эквивалентность на множестве М. Подмножество Ка М, состоящее из всех элементов М, эквивалентных элементу а М, называется классом эквивалентности элемента а по отношению « », т.е. Ка={ х: х а, где а, х М }.

Утверждения:

1) Два класса эквивалентности множества М либо совпадают, либо не пересекаются.

2) Любой элемент множества М попадает в один и только один класс эквивалентности.

Поэтому множество М разбивается на попарно непересекающиеся классы эквивалентных между собой элементов.

Множество всех классов эквивалентности для М по отношению « » называется фактор– множеством и обозначается М/. А процесс разбиения М на классы эквивалентности называется факторизацией.

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

Упорядоченность называется линейной, если для любых элементов а, b М = либо (a,b) Р, либо (b,a) Р. Множество М в этом случае называется линейно–упорядоченным или цепью.

Для обозначения отношения упорядоченности обычно используют знаки (или ), (или ). При этом a b равнозначно b a, и запись ab означает, что a b и a b. Если ab, то говорят, что а предшествует b (находится перед b), а b следует за а (находится после а). Т.о., для любых двух элементов цепи обязательно должно выполняться одно из двух: либо a b, Утверждение: если множество М упорядочено или линейно–упорядочено, то и каждое его подмножество упорядочено тем же отношением.

Пусть А М и М – упорядоченное множество. Элемент х М называется верхней (нижней) границей множества А, если для а А = а х ( х а ). Множество А в этом случае называется ограниченным сверху (снизу). Естественно, что А может иметь не одну верхнюю (нижнюю) границу, а множество верхних (нижних) границ. Тогда наименьшая из верхних границ А называется верхней гранью множества А и обозначается sup(А) – супремум.

Аналогично, наибольшая из нижних границ множества А называется нижней гранью А и обозначается inf(А) – инфимум. (Иначе говоря, верхняя грань А есть нижняя граница множества всех верхних границ А, а нижняя грань А есть верхняя граница множества всех нижних границ А.) Линейно–упорядоченное множество называется вполне упорядоченным, если у каждого его непустого и ограниченного снизу подмножества есть нижняя грань. Иными словами, упорядоченное множество является вполне упорядоченным, если любое его непустое подмножество имеет первый элемент.

Для графического изображения конечных частично или линейно упорядоченных множеств служит диаграмма Хассе.

Пусть М – упорядоченное множество и элементы x, y M, причем xy. Говорят, что y покрывает x, если не существует элемента z M такого, что x z y.

На диаграмме Хассе элементы множества М изображаются в виде точек. Две точки x и y соединяются отрезком прямой в том и только том случае, когда y покрывает x. При этом точку x рисуют ниже точки y.

1) M ={ 1, 2, 3, 4, 5, 6 } упорядочено отношением. Тогда его диаграмма выглядит так, как показано на рисунке 2.1. Такая диаграмма характерна для линейно упорядоченных множеств.

отношением включения – « ». Тогда его диаграмма выглядит как на рисунке 2.2.

3) M ={ 1, 3, 5, 7, 15, 21, 35, 105 } упорядочено отношением P={ (x, y) : y делится на x }.

Его диаграмма Хассе изображена на рисунке 2.3 и совпадает с предыдущей диаграммой с точностью до обозначения элементов. Между элементами этих множеств можно установить биективное отображение, сохраняющее имеющуюся упорядоченность элементов. Говорят, что такие7множества изоморфны (подобны) между собой относительно заданных на них отношений порядка.

Бинарное отношение Р называется однозначным, если для всякого элемента x пр1Р существует не более одного (а может быть и вовсе ни одного) значения y пр2Р.

Всюду определенное и однозначное бинарное отношение f A B называется функцией или отображением множества А в множество В. Если А и В числовые множества, то функция называется числовой.

у) f чаще обозначают y = f(x), и поскольку отображение – это частный случай бинарных отношений, то определены все ранее введенные понятия: образа и прообраза для элементов и множеств, области определения и области значений отображения (или функции), а также понятия композиции отображений и обратного отображения.

Элемент х называется неподвижной точкой отображения, если f(x) = x.

Отображение f : A B называется инъективным или взаимно-однозначным отображением прообраз. Подчеркнем, что не все элементы множества В обязаны иметь прообраз (должны быть чьими-нибудь образами).

Отображение называется сюрьективным (или сюрьекцией или отображением множества элементы множества В являются чьими-нибудь образами (имеют по крайней мере один прообраз).

отображением A на B), если оно одновременно инъективно и сюрьективно.

Биективное отображение A на А называется тождественным отображением, если все его элементы являются неподвижными точками, т.е. x A следует, что f(x) = x.

Утверждения:

1) Если f : A В и g : В С – две функции, то g f: AC – тоже является функцией.

2) Пусть f : A В – функция. Для того, чтобы f -1: В А было функцией, необходимо и достаточно, чтобы f было биективным отображением. В этом случае f –1 называется отображением, обратным к f, или обратной функцией. При этом f -1 – также биективно, f -1 f =IA – тождественное отображение А и f f -1 =IB – тождественное отображение В.

Отображение f : A В называется обратимым слева (справа), если существует отображение fЛ-1: В А ( fП-1: В А ) такое, что f Л-1 f =IA ( f f П-1 =IB ).

Способы задания действий. Свойства действий. Простейшие алгебраические системы.

Подгруппы. конечные группы. Кольца, тела и поля.

Основные понятия Пусть А – непустое множество и n 1. Тогда n –арным действием (или n –местной операцией) на множестве А называется отображение некоторого подмножества декартова Могут рассматриваться также нуль–арные действия (операции), которые по определению отмечают некоторый элемент из А. При n = 1 операция называется унарной, например, а–1. При n = 2 – бинарной, например a+b. При n = 3 – тернарной, например, нахождение центра тяжести векторов на плоскости f(x,y,z)=(x+y+z)/3. И т.д.. Чаще всего рассматриваются бинарные операции, для которых по определению некоторым парам элементов x, y A (или каждой паре элементов в частном случае), взятых в определенном порядке, сопоставляется третий элемент z A, называемый результатом выполнения операции над операндами x и y.

Отметим, что действие всегда задается на определенном множестве, поэтому в этом смысле сложение на множестве натуральных чисел и сложение на множестве рациональных чисел – разные действия, т.к. отличаются множествами, на которых они заданы.

На одном и том же множестве может быть задано несколько действий.

Множество всех действий (операций), заданных на множестве А, называется сигнатурой А, т.е. (А)= {,,,…} – сигнатура А. Множество А вместе с заданной на нем сигнатурой, возможно пустой, называется универсальной алгеброй или алгебраической системой и обозначается (А, ).

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

z = (x, y) или z = x y, если z A – результат некоторого действия над x и y A, а « » – обозначение действия (традиционно для обозначения действия используются знаки: +, –,, :, /, и т.д., при этом, используемое обозначение не обязательно показывает совпадение действия с известным элементарным действием). Запись вида z = x*y или z = x y, или z = xy называется мультипликативной, а z = x + y – аддитивной. При этом используется обычная терминология: операнды называются сомножителями (слагаемыми), а результат – произведением (суммой), хотя само действие может не иметь ничего общего с обычным умножением или сложением чисел.

Способы задания действий 1) Указать закон (формулу), выделяющий те пары элементов из А, для которых определен результат, и то, как строится результат для каждой такой пары, т.е. z = (x, y).

2) Непосредственно перечислить все результаты действия. Наиболее удобным представлением в таком случае является так называемая таблица Кэли (таблица умножения при мультипликативной записи). Слева и сверху этой прямоугольной таблицы выписываются все элементы множества, а на пересечении строк и столбцов – результат действия над соответствующими элементами или знак «–», если результат не определен. Теоретически такая таблица может быть построена для любого множества, конечного и даже бесконечного, практически рассматриваются только конечные множества и конечные таблицы.

Пусть на множестве А задано действие « », и В А. Тогда В называется замкнутым по отношению к действию, если для любых элементов x, y В x y В.

Например, рассмотрим действия сложения и вычитания на множестве целых чисел, т.е.

(, + ) и (, – ), и множество натуральных чисел. Тогда замкнуто по отношению к сложению и не замкнуто по отношению к вычитанию, поскольку не для любых пар натуральных чисел x и y результат (x-y).

Пусть имеются множества с действиями: ( А, ) и ( В, ). Множества А и В называются изоморфными относительно действий «» и «», если существует биективное отображение f:А В такое, что для любых элементов а1 и а2 из А и соответствующих им элементов b1 и b из В, где b1= f(а1) и b2= f(а2), результат (а1 а2) определен, т.е. А, тогда и только тогда, когда результат (b1 b2) В и при этом f(а1 а2)= (b1 b2), т.е. результаты также соответствуют друг другу.

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

1) Рассмотрим множество положительных вещественных чисел с умножением ( 0, ) и множество всех вещественных чисел со сложением (, +). Тогда изоморфизм устанавливается законом f(x)=ln(x), т.к. по свойствам логарифма ln(x y)=ln(x)+ln(y) для любых x, y 0.

2) Рассмотрим (, +) и ( S, ), где S={ 21, 22, 23, 24, … }. Множества изоморфны относительно действий, т.к. для любых пар натуральных чисел x, y и соответствующих им 2x и 2y S 2x+y=2x 2y.

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

Свойства действий (операций) Пусть в множестве А определено действие, обозначаемое «».

Действие называется неограниченно-применимым, если результат действия ху определен для любой пары элементов х, у А, т.е. ху А.

Действие называется коммутативным, если для любой пары элементов х, у А, для которых определен результат z=ху А, обязательно определен и результат z =ух А, и при этом z=z (т.е. ху=ух).

Действие называется ассоциативным, если для любой тройки элементов х, у, z А, для которой определены результаты (ху) и ((ху)z), обязательно определены и результаты (уz) и (х(уz)), и наоборот. Причем выполняется равенство ((ху)z)= (х(уz)).

Действие называется обратимым, если для любой пары элементов х, у А всегда существуют такие u, v А, что определены результаты (хu) и (vх) и выполняются равенства (хu)=y (обратимо справа) и (vх)=y (обратимо слева).

Действие называется сократимым справа, если для любой тройки элементов х, у, z А, для которой определены результаты (хz) и (уz), равенство (хz)=(уz) выполняется тогда и только тогда, когда x=y. Аналогично, действие называется сократимым слева, если для любой тройки элементов х, у, z А, для которой определены результаты (zx) и (zy), равенство (zx)=(zy) выполняется тогда и только тогда, когда x=y. Если действие сократимо как справа, так и слева, то оно называется сократимым.

Элемент еп А называется нейтральным справа относительно данного действия, если для любого х А результат (xеп) определен и равен х. Аналогично, элемент ел А называется нейтральным слева относительно данного действия, если для любого х А результат (елx) определен и равен х. Элемент е А называется нейтральным относительно данного действия, если он является нейтральным как справа, так и слева одновременно, т.е. (еx)=(xе)=х для любого х А. При мультипликативной записи нейтральный элемент называется единицей и обозначается «1», при аддитивной записи – нулем и обозначается «0».

Элемент x А называется обратным к элементу х А, если определены результаты (хх )и (х х) и имеет место равенство (хх )=е (обратный справа) и (х х)=е (обратный слева), мультипликативной записи обратный элемент обозначается «х-1», а при аддитивной – «–х».

Элемент x А называется идемпотентным, если результат (хx) определен и равен х.

Заметим, что относительно данного действия в множестве может существовать лишь один нейтральный элемент. Действительно, если предположить, что е1 и е2 два нейтральных элемента, то для любого элемента х А, в том числе и для х=е аналогично, для х=е элементом к нейтральному является он сам.

Простейшие алгебраические системы Алгебраические системы определяются множеством и заданными на нем действиями, обладающими теми или иными свойствами. Среди алгебраических систем некоторые выделяются в виду их особой важности и имеют особые наименования.

Множество, с заданным на нем бинарным действием называется группоидом или оперативом. Группоид называется частичным, если действие не обладает свойством неограниченной применимости; мультипликативным, если используется мультипликативная запись действия, и аддитивным в случае аддитивной записи действия.

Множество, в котором задано неограниченно – применимое и ассоциативное действие, называется полугруппой. Таким образом, полугруппа – это группоид с ассоциативным действием. При мультипликативной записи – с ассоциативным умножением, при аддитивной – с ассоциативным сложением.

Полугруппа с нейтральным элементом называется моноидом.

Множество, в котором задано неограниченно – применимое, ассоциативное и обратимое действие, называется группой. Таким образом, группа – это полугруппа с обратимым действием, т.е. для любых элементов x, y G найдутся элементы u, v G такие, что xu=y и vx=y. Группа (полугруппа) называется абелевой, если действие коммутативно. Для абелевых групп чаще используется аддитивная запись действия, т.е. x, y, z G (x+y)+z=x+(y+z), 1. В любой группе существует единица (нейтральный элемент) и при том только одна.

Для любого элемента группы существует обратный элемент и при том только один.

2. Если в полугруппе существует нейтральный элемент и для любого е элемента существует обратный, то она является группой.

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

2. Рассмотрим (, ). Умножение во множестве натуральных чисел неограниченно– применимо и ассоциативно. Нейтральный элемент по умножению равен 1, обратный элемент имеется только у 1, поэтому это моноид.

(, ) – также моноид, (, ), (, ) – моноиды, здесь обратные имеют все элементы, кроме нуля, поэтому \{0} и \{0} образуют группы по умножению.

3. Рассмотрим 2М – булеан произвольного множества М. Тогда (2М,) – моноид. Так как объединение любых двух подмножеств М снова будет подмножеством М, т.е. объединение неограниченно–применимо. Для любых трех А, В, С М (АВ)С=А(ВС), т.е.

объединение ассоциативно, нейтральным элементом относительно объединения является – пустое множество. Обратных элементов нет (кроме пересечение неограниченно–применимо на 2М и ассоциативно. Нейтральным элементом относительно пересечения на 2М является само множество М, но обратный элемент есть только для М.

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

5. Множество всех многочленов с коэффициентами, являющимися элементами произвольной группы, относительно операции сложения многочленов образует группу, т.к. для любых многочленов f(x) = a0 + a1x + a2x2+…+anxn и g(x) = b0 + b1x + b2x2+…+bnxn их сумма (f(x)+g(x)) = (a0+b0) + (a1+b1)x + (a2+b2)x2+…+(an+bn)xn – также многочлен. Сложение ассоциативно, нейтральный элемент – многочлен, все коэффициенты которого равны нулю, обратным к произвольному многочлену f(x) является многочлен [–f(x)], все коэффициенты которого имеют противоположные знаки.

Непустое подмножество Н элементов группы G называется подгруппой, если оно само образует группу относительно действия в G.

Из этого определения следует, что для любых элементов a, b H результат действия (a b) также принадлежит Н, нейтральный элемент e H является также нейтральным и в группе G. И, в силу единственности обратного элемента в группе, ясно, что обратный элемент для любого элемента h из Н будет обратным для h также во всей группе G.

(О подгруппе) Непустое подмножество Н группы G является подгруппой тогда и только тогда, когда 1) для любых элементов a, b H результат действия (a b) также принадлежит Н; и 2) для любого элемента h Н обратный элемент h–1 также принадлежит Н.

Доказательство. Необходимость следует из определения подгруппы.

Для доказательства достаточности покажем, что нейтральный элемент группы принадлежит подмножеству Н, т.е. е Н. Т.к. по пункту 2 для любого элемента а Н по пункту 1 результат (а а-1) Н, но (а а-1) =е – нейтральный элемент группы. Таким образом, е Н, что и требовалось доказать. И, следовательно, Н – подгруппа G. (Ассоциативность действия переходит автоматически с G на Н).

Примеры подгрупп:

1) Аддитивная группа четных чисел является подгруппой группы (, + ) целых чисел по сложению, последняя в свою очередь является подгруппой группы (, + ) рациональных чисел по сложению, которая в свою очередь является подгруппой группы (, + ) вещественных чисел по сложению. Все аддитивные группы чисел являются подгруппами группы комплексных чисел по сложению.

2) Мультипликативная группа ( 0, ) положительных вещественных чисел по умножению является подгруппой мультипликативной группы ( \ {0}, ) вещественных чисел без нуля и не является подгруппой (,+ ), т.к. у них разные нейтральные элементы.

3) Подмножество {e} является подгруппой любой группы. Сама группа также является одной из своих подгрупп.

4) Пересечение любого числа подгрупп группы G является подгруппой группы G.

I. Конечные группы Группа (полугруппа) называется конечной, если она состоит из конечного числа элементов. Число элементов конечной группы называется е порядком. Любая подгруппа конечной группы конечна. И если Н G – подгруппа группы G, то для любого элемента а G множество На={х: x=ha, для любых h H} называется левым классом смежности для G относительно Н. Понятно, что число элементов в На равно порядку Н. (Аналогично можно сформулировать определение аН – правого класса смежности относительно Н).

Важно то, что для любой подгруппы Н группы G любые два левых (правых) класса смежности по Н либо совпадают, либо не пересекаются, поэтому любая группа может быть представлена как объединение непересекающихся левых (правых) классов смежности по Н.

Действительно, если два класса Нa и Hb, где a, b G, имеют общий элемент х, то существует t H такое, что x = ta. И тогда левый класс для х: Нх={y: y=hx= h(ta) = (ht)a} Ha, но a= t-1x и Нa={y: y=ha= h(t-1x) = (ht-1)x} Hx. Отсюда Нх = Нa. Аналогично можно показать, что Нх = Нb. И, следовательно, Нa = Нb. Если же классы Нa и Hb не имеют общих элементов, то они и не пересекаются.

Такое разбиение группы на левые (правые) классы смежности называется разложением группы по подгруппе Н.

Порядок конечной группы делится на порядок любой е подгруппы.

Доказательство. Так как G – конечная группа, то и любая е подгруппа Н имеет конечный порядок. Рассмотрим разложение группы по подгруппе Н. В каждом классе смежности в этом разложении число элементов одинаково и равно порядку Н. Поэтому, если n – порядок группы G, а k – порядок подгруппы Н, то n=m k, где m – число классов смежности по Н в разложении группы G.

подгруппе Н совпадают), то Н называется нормальным делителем группы G.

Утверждение: если G – коммутативная группа, то любая е подгруппа Н является нормальным делителем G.

Циклические подгруппы «произведении» трех элементов (аbc) =(аb)c = а(bc). Аналогично вводится понятие Произведение n одинаковых элементов группы называется степенью элемента и любого элемента группы a G обозначают а0=е – нейтральный элемент группы G. А отрицательные степени элемента a-n определяют как (a-1)n или (an)-1, где a-1 – обратный элемент аа (аa-1)a-1 a-1 =еn =e. Таким образом, (a-1)n = (an)-1.

В аддитивной группе аналогом степени элемента an будет n-кратное к нему, обозначаемое обычно na, которое не стоит воспринимать как произведение n на а, поскольку любого натурального n, где (-a) – обратный к a G.

Легко показать, что при выбранных обозначениях для любых целых чисел m и n и для любого a G выполняются известные свойства: а) при мультипликативной записи an am = an +m и (an)m = anm; б) при аддитивной записи na+ma = (n+m)a и n(ma)=(nm)a.

Подгруппа Аg называется циклической подгруппой группы G, порожденной элементом g.

Эта подгруппа всегда коммутативна, даже если сама G не коммутативна. Если группа G совпадает с одной из своих циклических подгрупп, то она называется циклической группой, порожденной элементом g.

Если все степени элемента g различны, то группа G называется бесконечной циклической группой, а элемент g – элементом бесконечного порядка.

Если среди элементов циклической группы имеются равные, например, gk=gm при km, то gk-m=e; и, обозначив k-m через n, получим gn=e, n.

Наименьший натуральный показатель n такой, что gn=e, называется порядком элемента g, а сам элемент g называется элементом конечного порядка.

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

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

Эти действия, как и в случае групп и полугрупп, могут быть весьма разнообразными. И для обозначения этих действий в общем случае лучше всего было бы употреблять какие–либо отвлеченные от установившихся понятий значки, например: «», «*», « » и т.п.. Однако, по сложившейся традиции, в алгебраических системах с двумя действиями приняты обозначения «+» и « » (или « ») и при этом используется обычная терминология для этих действий:

«сложение» и «умножение». Хотя сами эти действия могут и не иметь ничего общего со сложением и умножением обычных чисел.

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

Кольцом называется непустое множество R, для элементов которого определены две бинарные операции - сложение и умножение (обозначаемые + и - соответствнно; знак - обычно опусткается), причем предполагаются выполненными следующие аксиомы колец (a, b, c О R):

Коммутативность сложения: a+ b = b + a.

Ассоциативость сложения: a + (b + c) = (a + b) + c.

Обратимость сложения (возможность вычитания): уравнение a + x = b имеет решение x III.

Дистрибутивность умножения относительно сложения: a (b + c) = a b + a c и (b + c) a = IV.

Кольцо является обобщением системы (Z, +, Ч ) целых чисел, однако в кольце условие a b = ba может нарушаться и равенство a b = 0 может иметь место и тогда, когда a 0 и b Из свойств I - III ясно, что элементы кольца образуют абелеву группу относительно сложения: она называется аддитивной группой кольца. Нуль 0 этой группы относительно умножения является "поглощающим" элементом, т.е. a - 0 = 0-a= 0 для любого элемента a кольца. Кольцо, вообще говоря, может содержать и т.н. делители нуля, т.е. такие ненулевые элементы a и b, произведение которых равно 0. Единицей назывется такой элемент 1 кольца R, что a - 1 = 1 - a = a для всех aО R. Кольцо не обязано обладать единицей, но если она есть, то только одна.

1) множество всех целых чисел;

2) множество всех четных чисел и вообще целых чисел, кратных данному числу m;

3) множество всех рациональных чисел;

4) множество всех действительных чисел;

5) множество всех комплексных чисел;

6) множество всех гауссовых чисел, т.е. комплексных чисел a + bi с целыми a и b;

рациональными, действительными или комплексными коэффициентами;

8) множество всех функций, непрерывных на данном отрезке чмсловой прямой;

комплексными) элементами;

10) множество всех кватернионов;

11) множество всех чисел Кэли;

12) множество всех симметричных матриц порядка n с действительными элементами относительно сложения матриц и йорданова умножения a о b =(ab + ba), где в правой части стоят обычные произведения матриц;

13) множество всех векторов трехмерного пространства относительно обычного сложения и векторного умножения.

Во многих случаях на умножение в кольцах накладывают дополнительные ограничения.

Так, если a(bc)=(ab)c, то кольцо называют ассоциативным (примеры 1 - 10); если в кольце выполняются равенства (aa)b = a(ab), (ab)b = a(bb), то он называется альтернативным (например, 11); если в кольце выполняются равенства ab = ba и (ab)(aa)=((aa)b)a, то то оно называется йордановым кольцом (например, 12); если в кольце выполняются равенства a2=0, a(bc) + b(ca) + c(ab) = 0, то оно называется кольцом Ли (пример 13); если ab=ba, то кольцо называется коммутативным (примеры 1- 8, 12). Ассоциативно-коммутативное кольцо с единицей и без делителей нуля называется областью целостности (примеры 1 - 7).

Ассоциативное кольцо, в котором при a 0 разрешимы оба уравнения ax = b и xa = b, называется телом (примеры 3 - 5, 10); тело обладает единицей и не имеет делителей нуля.

Коммутативное тело называется полем.

Понятие графа. Ориентированные и неориентированные графы Элементы графа:

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

Связность графа.

Основные определения Теория графов – обширный самостоятельный раздел дискретной математики. Годом рождения теории можно считать 1736 г. Л.Эйлер решил задачу о кенигсбергских мостах, которая привела к нахождению критерия существования в графе специального маршрута.

Термин «граф» был предложен в 1936 г. венгерским математиком Д.Кенигом.

Граф (от греческого gr a jw - пишу) - множество V вершин и набор E неупорядоченных и упорядоченных пар вершин; обычно граф обозначают как G(V, E).

Неупорядоченная пара вершин называется ребром, упорядоченная пара - дугой.

Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги - ориентированным (или орграфом).

Пара вершин может быть соединена двумя или более ребрами (или, соответственно, дугами одного направления), такие ребра (или дуги) называются кратными.

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

Вершины, соединенные ребром или дугой, называются смежными.

Ребра, имеющие общую вершину, тоже называются смежными.

Ребро (или дуга) и любая из его вершин называются инцидентными.

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

Граф без петель и параллельных ребер называется простым, в противном случае – мультиграфом.

Граф, не имеющий ребер, называется пустым, а не имеющий вершин (а значит и ребер) – нуль-графом.

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

Количество вершин в графе называется порядком графа.

Степенью или валентностью вершины называется число инцидентных ей ребер.

Вершина нулевой степени называется изолированной. Вершина степени 1 называется висячей, а ребро, инцидентное ей, называется висячим ребром. Заметим, что петля добавляет двойку к степени вершины.

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

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

Способы задания графов Граф можно задать диаграммой, матрицей ициденций, матрицей смежности, списком связей и перечнем ребер.

1)Каждому графу можно поставить в соответствие некоторую схему на плоскости, если вершины изображать точками, а ребра — линиями. Эта схема называется диаграммой графа или просто графом. Ребра на диаграмме могут быть отрезками прямых или дугами линий. Один и тот же граф можно изобразить разными диаграммами. (Рис.4.1,4.2) Такие диаграммы называются изоморфными.

На рис. 4.3 изображен ориентированный граф G — (V, Е), V= {а, b, с, d), E={(a, b), {b, b), (b, с), (с, b), (b, с), (с, а), (с, d)}. Этот граф имеет петлю (ребро, соединяющее вершину с ней самой) и кратные ребра (две вершины соединены более чем одним ребром).

2)Матрица инциденций – это двумерный массив размерности nxm Матрица смежности – это двумерный массив N*N.

Задание графа списками связи осуществляется с помощью одномерного массива размерности N для хранения указателей. Элемент массива – указатель на начало списка, в котором содержится информация о вершинах графа, смежных с рассматриваемой.

Для хранения перечня ребер необходим двумерный массив размерности M*2. Строка массива описывает ребро.

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

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

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

Любая вершина, инцидентная двум рядом стоящим ребрам маршрута, называется внутренней или промежуточной вершиной. Так как ребра и вершины в маршруте могут повторяться, то внутренняя вершина может также оказаться начальной или конечной вершиной.

Маршрут неориентированного графа называют неориентированным маршрутом (составной цепью), а маршрут орграфа называют ориентированным маршрутом (составным путем). Если все ребра незамкнутого маршрута попарно различны, то такой маршрут неориентированного графа называется цепью путем. Если попарно различны все вершины незамкнутого маршрута, то такой маршрут неориентированного графа называется простой цепью простым путем. Если попарно различны все ребра замкнутого маршрута, то такой маршрут неориентированного графа называется циклом контуром. Замкнутый маршрут, в котором попарно различны все вершины, кроме первой и последней, называется в неориентированном графе простым циклом простым контуром.

Маршрут назовем нетривиальным, если он содержит хотя бы одно ребро; для систематичности рассуждений вводится еще нуль-маршрут этот маршрут состоит только из одной вершины графа.

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

Отношение связности рефлексивно (вершина всегда связана сама с собой), симметрично (из связности вершины с вершиной следует связность вершины с вершиной )и транзитивно (если вершины и вершины связаны, то связаны и вершины, ). Таким образом, отношение связности для вершин есть отношение эквивалентности. Поэтому существует такое разбиение множества вершин графа на попарно непересекающиеся подмножества (классы эквивалентности), что все вершины в каждом подмножестве связаны, а вершины из различных подмножеств не связаны. Каждое такое подмножество вершин графа вместе с ребрами, инцидентными этим вершинам, образует связный подграф. Следовательно, неориентированный граф представим единственным образом в виде объединения непересекающихся связных подграфов. Эти подграфы называют связными компонентами рассматриваемого графа. Связный граф является своей единственной компонентой связности.

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

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

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

Орграф называется слабым (или слабосвязным), если связным графом является его неориентированный дубликат. На рис. 4.8 изображен сильный орграф, на рис. 4.9 односторонний, а на рис. 4.10 слабый. Поскольку вершина графа достижима из себя, то одновершинный орграф будет одновременно и сильным, и односторонним, и слабым. Каждый сильный орграф является односторонним, а каждый односторонний - слабым. Очевидно, что две любые несовпадающие вершины сильного орграфа принадлежат некоторому контуру.

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

Маршрут, содержащий все вершины орграфа, называется остовным.

Теорема 4.1 Орграф является сильным тогда и только тогда, когда в нем есть остовный контур, является односторонним тогда и только тогда, когда в нем есть остовный путь.

Отношение взаимной достижимости вершин орграфа рефлексивно, симметрично и транзитивно. Как отношение эквивалентности оно разбивает множество вершин орграфа на классы эквивалентности, объединяя в один класс все вершины, достижимые друг из друга.

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

Орграф называется несвязным, когда его неориентированный дубликат не является связным графом.

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

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

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

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

Числом вершинной связности (или просто числом связности) графа называется число, равное наименьшему числу вершин, удаление которых приводит к несвязному или одновершинному графу.

Можно нарушить связность графа, удаляя некоторые его ребра (дуги).

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

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

Он разбивается на блоки, каждый из которых представляет собой максимальный неразделимый подграф.

Задачи теории графов развлекательных задач и головоломок, например:

задача о кенигсбергских мостах (задача Эйлера), развитие которой привело к циклу задач об обходах графов;

задачи о перевозках, решение которых привело к созданию эффективных методов решения транспортных задач и др.

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

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

Так, Г. Кирхгоф при составлении полной системы уравнений для токов и напряжений в электрической схеме предложил, по существу, представлять такую схему графом и находить в нем деревья, с помощью которых выделяются линейно независимые системы контуров.

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

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

Наряду с термином граф в начале 20 века употреблялись в качестве синонимов и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт.

В проблематике теории графов можно выделить направления, носящие более комбинаторный или более геометрический характер.

К комбинаторным относятся, например, задачи о построении графов с заданными свойствами, задачи о подсчете и перечислении графов с фиксированными свойствами.

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

Примерами задач о подсчете являются задачи о нахождении количеств неизоморфных графов с одинаковым числом вершин и (или) ребер. Получены асимптотические формулы для числа неизоморфных деревьев с n вершинами и для числа неизоморфных графов без петель и кратных ребер с n вершинами.

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

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

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

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

Найдены критерии и построены эффективные алгоритмы установления k - связности графа.

Характерным специфическим направлением теории графов является цикл проблем, связанных с раскрасками графов, в которых изучаются разбиения множества вершин (ребер), обладающие определенными свойствами, например, смежные вершины (ребра) должны принадлежать различным множествам (вершины и ребра из одного множества окрашиваются одним цветом). Так, было доказано, что наименьшее число цветов, достаточное для раскраски ребер любого графа без петель с максимальной степенью вершин s, равно [ 3 s/ 2 ], а для раскраски вершин любого графа без петель и кратных ребер достаточно s + 1 цветов.

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

Определение дерева. Свойства деревьев. Теорема о представлении графа как дерева.

Теорема о сумме степеней графа. Изоморфизм графов. Отношение порядка и отношение эквивалентности на графе.

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

Связный неориентированный граф без циклов (в частности, без петель и кратных ребер) называется деревом. Несвязный неориентированный граф без циклов называется лесом, а его связные компоненты — деревьями.

Например, граф на рис. 5.1 — дерево, на рис. 5.2 — лес.

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

Применительно к деревьям многие доказательства и рассуждения оказываются намного проще.

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

Теорема. Любые две вершины дерева связаны одной и только одной цепью.

С помощью построения оптимального дерева могут быть решены задачи оптимизации на графах. Рассмотрим одну из задач.

Задача. Известны расстояния между каждой парой из п вершин. Нужно так соединить вершины, чтобы получился неориентированный граф — дерево с минимальной суммарной длиной ветвей (кратчайший остов).

Правило построения (алгоритм) такого кратчайшего остова следующее. Строится ребро, соединяющее две вершины, между которыми наименьшее расстояние. Одна из вершин считается корнем дерева, а вторая соединяется со следующей вершиной, выбираемой так, чтобы расстояние между ними было меньше, чем расстояние до любой другой из оставшихся вершин.

Так же строятся следующие ребра.

Пропускается при этом лишь построение ребер, образующих циклы с ранее построенными. Таким образом получается дерево с n - 1 ребрами и с заданными вершинами, суммарная длина ребер у которого минимальна Алгоритм сохраняется для мультиграфа каждому ребру которого приписана мера Например, для мультиграфа на рис. 5.3 с ребрами и их мерами:

В ряде задач полезны двудольные графы.

имеет один конец из другой — из Двудольные графы применяются, когда изучаемые объекты разделяются на две группы так, что внутри групп интересующие нас взаимодействия отсутствуют. Например, в генетике — признаки и гены, в химии — кислоты и основания, в экономике — производители и потребители.

Пример двудольного графа приведен на рис. 5.4, на диаграмме его вершины часто располагают на параллельных прямых.

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

Свойства деревьев Теорема 5.1. Пусть G(X, E) – неориентированный граф с p вершинами и q ребрами.

Тогда следующие утверждения эквивалентны.

2. Любые две различные вершины x и y графа G соединены единственной простой цепью.

3. G – связный граф, утрачивающий это свойство при удалении любого из его ребер.

6. G – ациклический граф, причем если любые две его вершины x и y соединить ребром e, то в полученном графе будет ровно один простой цикл.

Определение, аналогичное дереву, можно ввести и для орграфа.

Орграф G(X, E) называется прадеревом или ориентированным деревом, растущим из корня x0, при следующих условиях:

1. Неориентированный граф G', соответствующий графу G, является деревом.

2. Единственная простая цепь между x0 и любой другой вершиной x графа G' является путем в орграфе G, идущим из вершины x0 в вершину x.

На рис.5.5 изображено ориентированное дерево.

В неориентированном графе G(X, E) вершина x называется концевой или висячей, если (x) = 1, т.е. если этой вершине инцидентно единственное ребро e. Это ребро также называется концевым или висячим. С висячими вершинами связана следующая теорема.

Теорема 5.2. В любом дереве G(X, E) с p 2 вершинами имеется не менее двух концевых вершин.

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

Теорема 5.3. (А. Кэли, 1897 г.). Число помеченных деревьев с p вершинами равно pp-2.

Отметим, что среди pp-2 помеченных деревьев с p вершинами могут быть и изоморфные.

Подграф G1(X1, E1) неориентированного графа G(X, E) называется каркасом, или остовным деревом графа G, если G1 – дерево и X = X1.

Теорема 5.4. Граф G(X, E) тогда и только тогда обладает каркасом, когда он связен.

неориентированный граф G(X, E), каждому ребру e E которого поставлено в соответствие число (e) 0, называемое весом или длиной ребра e.

Аналогично можно определить нагруженный орграф.

Изоморфизм графов множествами вершин существует взаимно однозначное соответствие, сохраняющее смежность.

значение на любом графе, изоморфном. Полный набор инвариантов определяет граф с точностью до изоморфизма.

том и только в том случае, когда ребро инцидентно вершинам и.

вершинами деревьев, а также между их ребрами можно установить взаимно однозначное Другими словами, два дерева изоморфны, если между их вершинами можно установить взаимно однозначное соответствие, сохраняющее отношение инцидентности (смежности).

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

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

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

Изоморфное отображение дерева на себя называется автоморфизмом дерева.

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

Дерево называется асимметричным, если его группа автоморфизмов есть единичная Примеры асимметричных деревьев порядка 7, 8, 9.

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

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

Правило суммы. Правило прямого произведения. Размещения с повторениями.

Размещения без повторений. Перестановки. Сочетания. Сочетания с повторениями.

Полиноминальная формула. Метод рекуррентных соотношений. Метод производящих функций. Метод траекторий Комбинаторика - раздел математики, в котором изучаются задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых из элементов заданного конечного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия, ответить на вопрос «сколькими способами?».

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

Правило умножения (основной принцип): если из некоторого конечного множества первый объект (элемент x ) можно выбрать n1 способами и после каждого такого выбора второй объект (элемент y ) можно выбрать n 2 способами, то оба объекта ( x и y ) в указанном порядке можно выбрать n1 n2 способами.

Этот принцип, очевидно, распространяется на случай трех и более объектов.

Правило суммы. Если некоторый объект x можно выбрать n1 способами, а объект y можно выбрать n 2 способами, причем первые и вторые способы не пересекаются, то любой из указанных объектов ( x или y ), можно выбрать n1 n2 способами.

Это правило распространяется на любое конечное число объектов.

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

Существуют две схемы выбора m элементов 0 m n из исходного множества: без возвращения (без повторений) и с возвращением (с повторением). В первом случае выбранные элементы не возвращаются обратно; можно отобрать сразу все элементов или последовательно отбирать их по одному. Во второй схеме выбор осуществляется поэлементно с обязательным возвращением отобранного элемента на каждом шаге. Мы рассмотрим только первую схему.

Пусть дано множество, состоящее из n различных элементов.

каждое из которых состоит из m элементов, взятых из данных n элементов. При этом размещения отличаются друг от друга как самими элементами, так и их порядком.

Число размещений из n элементов по m элементов обозначается символом An и вычисляется по формуле Для составления размещения An надо выбрать m элементов из множества с n элементами и упорядочить их, т. е. заполнить m мест элементами множества. Первый элемент можно выбрать n способами, т. е. на первое место можно поместить любой из n элементов.

После этого второй элемент можно выбрать из оставшихся n 1 элементов n 1 способами.

Для выбора третьего элемента имеется n 2 способа, четвертого - n 3 способа, и, наконец, для последнего m -го элемента - n m1 способов. Таким образом, по правилу умножения, существует n n 1 n 2 n m 1 способов выбора m элементов из данных n элементов, т.

е. An Перестановками из n элементов называются размещения из n элементов по n элементов, отличающиеся друг от друга лишь порядком элементов.

Число перестановок из n элементов обозначается символом Pn и вычисляется по формуле каждое из которых состоит из m элементов, взятых из данных n элементов. Эти соединения отличаются друг от друга хотя бы одним элементом. В отличие от размещений, порядок следования элементов здесь не учитывается.

Число сочетаний из n элементов по m элементов обозначается символом C n и вычисляется по формуле С помощью сочетаний можно записать формулу бинома Ньютона:

Числа C n, C n,, являются биномиальными коэффициентами и для них выполняется следующее условие 1 Cn Cn Рекуррентные соотношения При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского "recurrere" - "возвращаться").

Проиллюстрируем метод рекуррентных соотношений на конкретном примере.

Пример1. Найти число сочетаний из n по r с повторениями, т.е. число элемент так как каждое такое сочетание может быть получено присоединением к Последовательно применяя (25), находим тогда, полагая в (6) r = 2 получим При r = 3 из равенства (26), учитывая формулы (27),(28) и равенство (22) получим Проверяем истинность гипотезы методом математической индукции. При r = равенство (9) верно в силу первой формулы из (7). Теперь находим т.е. (9) верно и при подстановке вместо r. Следовательно, согласно принципу математической индукции, формула (9) верна для любого натурального r. Задача решена.

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

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

Пример 2 Найти число сочетаний из m по n с повторениями, т.е.

Для из формулы (5) имеем следующее рекуррентное соотношение Для того чтобы равенство (10) имело место и при n = 1 достаточно считать, что в дополнение к равенствам (7).

Умножим обе части равенства (10) на и сложим почленно все равенства, тогда получим известно, что значит, из единственности разложения функции в ряд Маклорена, следует Задача решена.

Метод траекторий Для комбинаторной задачи указывается геометрическая интерпретация, которая сводит задачу к подсчету числа путей (траекторий), обладающих определенным свойством. Этим методом фактически была решена задача в примере 8.

Проиллюстрируем метод траекторий еще на одном примере.

Пример 3. Возле кассы собрались n + m человек, причем n из них имеют монеты стоимостью 50 копеек, а другие имеют лишь по рублю Сначала в кассе нет денег, билет стоит 50 копеек. Сколько всего имеется способов размещения всех покупателей в очереди так, чтобы ни один из них не ждал сдачи?

Допустим, что покупатели расположены в очереди некоторым образом. Пусть Ясно, что значение, определяемое формулой (13), является разностью между количеством пятидесятикопеечных монет и количеством рублей, которые будут поданы в кассу первыми k покупателями из очереди.

Введем на плоскости декартову прямоугольную систему координат Oxy. Построим в ней называть ломаную траекторией, соответствующей данному способу размещения покупателей в очереди. Каждая траектория состоит из n + m отрезков, n из которых направлены вверх, а m направлены вниз. Если указать номера тех отрезков, которые направлены вверх, то тем самым траектория будет полностью определена. Следовательно, общее число траекторий, т.е. число возможных размещений покупателей в очереди, равно.

Траектории, соответствующие тем способам размещения покупателей, при которых ни один покупатель не ждет сдачи, не имеют общих точек с прямой. Действительно, если для некоторого то, в лучшем случае, это означает, что первые покупателей подали в кассу одинаковое количество полтинников и рублей а следующий покупатель подал рубль и вынужден ожидать сдачу. Определим число траекторий, имеющих общую точку с прямой. Поставим в соответствие каждой траектории T, имеющей с прямой хотя бы одну общую точку, ломаную по следующему правилу. До первой общей точки с прямой ломаная совпадает с T, а далее является симметричным отображением T относительно прямой. Все ломаные заканчиваются в точке прямой. Установленное соответствие является взаимно однозначным. Число ломаных типа, равно числу ломаных, соединяющих точки O и. Это число легко подсчитать.

Если ломаная состоит из y отрезков, направленных вниз, и x отрезков, направленных вверх, общую точку с прямой равно Следовательно, искомое число траекторий, соответствующих тем способам размещения покупателей, при которых ни один покупатель не ждет сдачи, равно Теория множеств Множество — это совокупность объектов, называемых его элементами.

N = {1,2,3,...} — множество натуральных чисел.

Z = {0, ±1, ±2, ±3,...} — множество целых чисел.

Q = {p/q| : р, q целые, q 0} — множество рациональных чисел.

Примеры 1. {1; 1} множество, элементами которого являются числа 1; 1.  2. "(  I    читается  как  "такие,  что").  Запись  множества  читается  следующим  образом: "множество X состоит из элементов x , принадлежащих R (вещественные числа),  такие что, выполняется условие x21=0".  3. Дан отрезок [a,b], где a,b (R и ab. Записать его в виде множества:    4. Дан интервал (a,b), где a,b  R и ab. Записать его в виде множества:    Подмножеством множества S называется множество А, все элементы которого Два множества называются равными тогда и только тогда, когда каждое из них является подмножеством другого.

Объединением множеств А и В называется множество AUB = {х : х А или х В}.

Пересечением множеств А и В называется множество Дополнением множества В до А называется множество А\В = {х : х Аи х В}.

Мощностью конечного множества S называется число его элементов.

Отношения Бинарным отношением между множествами А и В называется подмножество R в А х В. Если А = В, то говорят, что R — отношение на А.

Бинарное отношение между конечными множествами может быть описано на словах (при помощи подходящих предикатов), как множество упорядоченных пар, как орграф и с помощью матрицы.

Отношение R на множестве А называется рефлексивным, если xRx для всех х А;

симметричным, если xRy = уRx для всех х, у А; кососимметричным, если (хRy и уRx = х = у) для всех х, у, z А; транзитивным, если (хRy и уRz) = xRz для всех х, yz А.

Рефлексивное, симметричное и транзитивное отношение R на множестве А называется отношением эквивалентности. Классом эквивалентности элемента х А является подмножество Еx = {z А : zRx}.

Рефлексивное, кососимметричное и транзитивное отношение R на множестве А называется частичным порядком. Множества, на которых определено такое отношение, в свою очередь, называются частично упорядоченными множествами.

Теория графов Граф G - совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Каждое ребро e из E инцидентно ровно двум вершинам v', v'', которые оно соединяет. При этом вершина v' и ребро e называются инцидентными друг другу, а вершины v' и v'' называются смежными.

Часто пишут v', v'' из G и e из G. Если |V(G)|=n, |E(G)|=m, то граф G есть (n,m) граф, где n - порядок графа, m - размер графа.

Ребро (v',v'') может быть ориентированным и иметь начало (v') и конец (v'') (дуга в орграфе).

Ребро (v,v) называется петлей (концевые вершины совпадают).

Граф, содержащий ориентированные ребра (дуги), называется орграфом.

Граф, не содержащий ориентированные ребра (дуги), называется неографом.

Ребра, инцидентные одной паре вершин, называются параллельными или кратными.

Граф с кратными ребрами называется мультиграфом.

Граф, содержащий петли (и кратные ребра), называется псевдографом.

Конечный граф - число вершин и ребер конечно.

Пустой граф - множество ребер пусто (число вершин может быть произвольным).

Полный граф - граф без петель и кратных ребер, каждая пара вершин соединена ребром. Обозначение для полного графа с n вершинами - Kn.

Граф называется двудольным, если существует такое разбиение множества его вершин на две части, что концы каждого ребра принадлежат разным частям (долям).

Если любые две вершины двудольного графа, входящие в разные доли, смежны, то граф называется полным двудольным. Обозначение для полного двудольного графа с n и m вершинами - Kn,m.

Локальная степень вершины - число ребер ей инцидентных. В неографе сумма степеней всех вершин равна удвоенному числу ребер (лемма о рукопожатиях).

Петля дает вклад, равный 2 в степень вершины.

Следствие 1 из леммы о рукопожатиях. Произвольный граф имеет четное число вершин нечетной степени.

Следствие 2 из леммы о рукопожатиях. Число ребер в полном графе n(n-1)/2.

В орграфе две локальных степени вершины v: deg(v)+ и deg(v) - (число ребер с началом и концом в v) Графы равны, если множества вершин и инцидентных им ребер совпадают.

Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.

Граф называется регулярным (однородным), если степени всех его вершин равны.

Матрица инцидентности A. По вертикали указываются вершины, по горизонтали ребра. aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро - петля, то aij=2.

Список ребер. В первом столбце ребра, во втором вершины им инцидентные.

Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. Dij= число ребер, соединяющее вершины i,j.

Матрица Кирхгофа: bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii=deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.

Отношение вершин графа "существует маршрут, связывающий вершины" является отношением эквивалентности, задающее разбиение графа на компоненты связности. Индекс разбиения - k.

Маршрут - последовательность ребер, в которых каждые два соседних ребра имеют общую вершину.

Маршрут, в котором начало и конец совпадают - циклический.

Маршрут в неографе, в котором все ребра разные - цепь.

Маршрут в орграфе, в котором все дуги разные - путь.

Путь, в котором начало и конец совпадают - контур.

Цепь с неповторяющимися вершинами - простая.

Циклический маршрут называется циклом, если он цепь и простым циклом, если эта цепь простая.

Вершины связанные, если существует маршрут из одной вершины в другую.

Связанный граф - если все его вершины связаны.

Число ребер маршрута - его длина.

Эйлеров цикл - цикл графа, содержащий все его ребра.

Эйлеров граф - граф, имеющий Эйлеров цикл.

Теорема Эйлера. Конечный неориентированный граф эйлеров тогда и только тогда, когда он связан и степени его вершин четны.

Теорема. Мультиграф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин нечетной степени равно 0 или 2.

Гамильтонов цикл - простой цикл, проходящий через все вершины.

Дерево - связный граф без циклов.

Лес (или ациклический граф) - неограф без циклов (может быть и несвязным).

Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны:

2. G - связный граф, содержащий n-1 ребро;

3. G - ациклический граф, содержащий n-1 ребро;

4. Любые две несовпадающие вершины графа G соединяет единственная цепь.

5. G - ациклический граф, такой, что если в него добавить одно ребро, то в нем Остов (каркас) связного графа - дерево, содержащее все вершины графа.

Определяется неоднозначно.

Редукция графа - остов с наибольшим числом ребер.

Цикломатическое (или циклический ранг) число графа =m-n+c, где n - число вершин,m - число ребер, c - число компонент связности графа.

Коциклический ранг (или коранг) *=n-c.

Теорема. Число ребер неографа, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно цикломатическому Неограф G является лесом тогда и только тогда, когда (G)=0.

Неограф G имеет единственный цикл тогда и только тогда, когда (G)=1.

Остов неографа имеет * ребер.

Ребра графа, не входящие в остов, называются хордами.

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

Комбинаторика Правило умножения (основной принцип): если из некоторого конечного множества первый объект (элемент x ) можно выбрать n1 способами и после каждого такого выбора второй объект (элемент y ) можно выбрать n 2 способами, то оба объекта ( x и y ) в указанном порядке можно выбрать n1 n 2 способами.

Правило суммы. Если некоторый объект x можно выбрать n1 способами, а объект y можно выбрать n 2 способами, причем первые и вторые способы не пересекаются, то любой из указанных объектов ( x или y ), можно выбрать n1 n способами.

Размещениями из n элементов по m 0 m n элементов называются соединения, каждое из которых состоит из m элементов, взятых из данных n элементов. При этом размещения отличаются друг от друга как самими элементами, так и их порядком.

Число размещений из n элементов по m элементов обозначается символом An и вычисляется по формуле Перестановками из n элементов называются размещения из n элементов по n элементов, отличающиеся друг от друга лишь порядком элементов.

Число перестановок из n элементов обозначается символом Pn и вычисляется по формуле Сочетаниями из n элементов по m 0 m n элементов называются соединения, каждое из которых состоит из m элементов, взятых из данных n элементов. Эти соединения отличаются друг от друга хотя бы одним элементом. В отличие от размещений, порядок следования элементов здесь не учитывается.

Число сочетаний из n элементов по m элементов обозначается символом C n и вычисляется по формуле

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

КОНТРОЛЬНОЙ РАБОТЫ

ПО ДИСЦИПЛИНЕ

«ДИСКРЕТНАЯ МАТЕМАТИКА»

1 Задания на выполнение самостоятельной работы 1.1 Общие сведения о работе Контрольная работа представляется преподавателю в печатном виде.

Контрольная работа считается выполненной, если она удовлетворяет Перечень заданий для контрольных работ приведен в Приложении 2 Методика выбора варианта При выполнении контрольных заданий студент подставляет вместо параметров n, m, k следующие значения:

n - число букв в полном имени студента;

m - число букв в отчестве;

k - число букв в фамилии.

3 Требования к оформлению и объему самостоятельной работы В состав контрольной работы входят:

Титульный лист (пример Приложение 1);

Оглавление; Текст контрольной работы;

Список использованной литературы.

Шрифт Times New Roman, размер шрифта 14, интервал - 1,5. Документ должен содержать верхний колонтитул, в котором указывается: фамилия студента, предмет и номер контрольной работы, нижний колонтитул должен содержать нумерацию страниц (выравнивание от центра).

Объем работы не должен превышать 10 страниц.

4 Порядок регистрации, проверки и возвращения на доработку Контрольная работа сдается преподавателю за 10 дней до начала сессии.

5 Список рекомендуемой литературы 1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера- М.: Энергоатомиздат, 1988 г.

2. Яблонский С.В. Введение в дискретную математику.- М.: Наука, 1986 г.

3. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики». М., МАИ, 1992.

4. Я.М. Ерусалимский «Дискретная математика». М., Вузовская книга, 2001.

5. С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики», Москва, ИНФРА-М, 2002.

6. Ф.А. Новиков «Дискретная математика для программистов». СПб: Питер, 2001.

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Волгоградский государственный технический университет»

Факультет электроники и вычислительной техники Кафедра «Системы автоматизированного проектирования I. Множества и операции над ними 1) Для задач a-c определить результаты действий A B, A B, A\B, B\A, A+B.



Pages:   || 2 |
 
Похожие работы:

«Московский городской Дворец детского (юношеского) творчества Организационно-технологическая программа Развитие одаренности СБОРНИК РАБОТ УЧАЩИХСЯ ПО ПРОЕКТНО-ИССЛЕДОВАТЕЛЬСКОЙ ДЕЯТЕЛЬНОСТИ И ПРИКЛАДНОМУ ТВОРЧЕСТВУ (ГУМАНИТАРНОЕ НАПРАВЛЕНИЕ) ЗА 2007-2008, 2008-2009 УЧ.ГГ. МОСКВА, 2010 В настоящем сборнике предпринята попытка возродить традицию публикации лучших исследовательских и творческих работ учащихся, представленных на разные конференции и конкурсы, проводимые разными Центрами и отделами...»

«Submitted on: July 5, 2013 Открывая библиографии для будущего – Перспективные модели библиографий при проведении совместных научных исследований up the bibliographies for the future – Перевод на русский язык доклада: “Opening A collaborative research-driven model for bibliographies” Translated by: Александра Теплицкая (Alexandra Teplitskaya), Russian State Library, Moscow, Russian Federation Хэг Хьёсьён (Hege Stensrud Hsien) Исследования и Коллекции, Национальная библиотека Норвегии, Осло,...»

«МИНОБРНАУКИ РОССИИ Волжский политехнический институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования Волгоградский государственный технический университет ВПИ (филиал)ВолгГТУ УТВЕРЖДАЮ Зам. директора по учебной работе 2011 г. Защита информации рабочая программа дисциплины (модуля) Закреплена за кафедрой Информатика и технология программирования Учебный план 230100_62-11-12-3933_zaoch_2vsh.plz.xml по направлению 230100.62 -...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ВОЗДУШНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ГРАЖДАНСКОЙ АВИАЦИИ (МГТУ ГА) УТВЕРЖДАЮ Проректор по УМР В.Криницин __ 2007 г. РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ СД.08. Электро и приборное оборудование воздушных судов (Наименование, шифр по ГОС) Специальность (специализация) 160905. (Шифр по ГОС) Факультет Авиационных систем и комплексов Кафедра...»

«Пояснительная записка к тематическому планированию по технологии 2 класс Учебный предмет Технология имеет практикоРоль и место данной ориентированную направленность. Его содержание не только дисциплины в дает ребенку представление о технологическом процессе как образовательном совокупности применяемых при изготовлении какой-либо процессе. продукции процессов, правил, навыков, предъявляемых к технической документации требований, но и показывает, как использовать эти знания в разных сферах...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования Тихоокеанский государственный университет УТВЕРЖДАЮ Проректор по учебной работе С.В. Шалобанов 2007 г. ПРОГРАММА ДИСЦИПЛИНЫ по кафедре Cтроительные и дорожные машины ГИДРАВЛИЧЕСКИЕ И ПНЕВМАТИЧЕСКИЕ СИСТЕМЫ СДМ Утверждена научно-методическим советом университета для направления подготовки 190000 - Транспортные средства (специальность 190603.65 – Сервис и техническая эксплуатация...»

«140400.68:08 РАБОЧАЯ ПРОГРАММА НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ ПРАКТИКИ Трудоемкость з.е./час. Форма контроля Курс Семестр Зачет 2 4 6/216 1. ЦЕЛИ И ЗАДАЧИ НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ ПРАКТИКИ Научно-исследовательская практика является обязательным компонентом учебного процесса подготовки магистров. Цели практики: формирование и развитие профессиональных знаний в сфере избранной специальности, закрепление полученных теоретических знаний по дисциплинам направления и специальным дисциплинам магистерских...»

«Департамент образования города Москвы Государственное бюджетное образовательное учреждение высшего профессионального образования города Москвы МОСКОВСКИЙ ГОРОДСКОЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ Педагогический институт физической культуры и спорта Программа вступительного испытания для абитуриентов, поступающих на базе профессионального образования Теория и методика физического воспитания и адаптивной физической культуры по направлению: 49.03.02 Физическая культура для лиц с отклонениями в...»

«СИСТЕМА КАЧЕСТВА РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ Компьютерные методы в тепловых двигателях (ОД.А.02; с. 2 из 13 цикл ОД.А.00 Обязательные дисциплины основной образовательной программы подготовки аспиранта по отрасли Технические науки, специальность 05.04.02 – Тепловые двигатели) Рабочая программа составлена на федеральных государственных требований к структуре основной профессиональной образовательной программы послевузовского профессионального образования (аспирантура), утвержденных приказом...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОЛОГОДСКОЙ ОБЛАСТИ ВОЛОГОДСКИЙ ПОЛИТЕХНИЧЕСКИЙ ТЕХНИКУМ Утверждаю: Директор БОУ СПО ВО Вологодский политехнический техникум _/ М.В. Кирбитов / Приказ № от 20 г. ОСНОВНАЯ ПРОФЕССИОНАЛЬНАЯ ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ – ПРОГРАММА ПОДГОТОВКИ КВАЛИФИЦИРОВАННЫХ РАБОЧИХ ПО ПРОФЕССИИ 260807. ПОВАР, КОНДИТЕР форма подготовки очная с....»

«Шестьдесят третья сессия Всемирной ассамблеи здравоохранения 20 мая 2010 г. N° 4 Программа заседаний на четверг, 20 мая 2010 г. Время Пленарное заседание Комитет A Комитет B Зал Ассамблеи Зал XVIII Зал XVII Восьмое заседание Четвертое заседание 09:00 Девятое заседание Пятое заседание 14: Седьмое заседание 17: Сразу после завершения Десятое заседание Шестое заседание пленарного заседания Содержание Программа работы Ассамблеи здравоохранения I. II. Отчет о совещаниях III. Технические брифинги по...»

«АДМИНИСТРАЦИЯ МУНИЦИПАЛЬНОГО ОБРАЗОВАНИЯ САРАПУЛЬСКИЙ РАЙОН ПОСТАНОВЛЕНИЕ с. Сигаево 18 ноября 2013 г. № 1103 Об утверждении ведомственной целевой программы Техническое перевооружение агропромышленного комплекса Сарапульского района на 2013-2017 годы Руководствуясь ст. 179.3 Бюджетного кодекса РФ и Уставом муниципального образования Сарапульский район, Администрация МО Сарапульский район постановляет: 1. Утвердить ведомственную программу Техническое перевооружение агропромышленного комплекса...»

«МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ДОШКОЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ДЕТСКИЙ САД КОМБИНИРОВАННОГО ВИДА ИЗУМРУДНЫЙ ГОРОД УТВЕРЖДЕНА УТВЕРЖДЕНА советом Детского сада приказ от 17.10.2013 г.№ 18 -о.д. 15.10.2013 г. заведующий О.В.Абросимова Программа развития Тамбов, 2013 1 СТРУКТУРА 1.Паспорт Программы развития..3 2.Информационная справка об учреждении 2.1.Общие сведения об учреждении..6 2.2.Организация образовательного процесса.7 2.3.Социальное партнерство детского сада..8 2.4.Текущее ресурсное...»

«ПРОГРАММА Всероссийской научной конференции Наука и власть: проблема коммуникаций 26 сентября 2008, г. Москва Москва 2008 Организаторы Всероссийской научной конференции Наука и власть: проблема коммуникаций Отделение общественных наук РАН; Центральный экономико-математический институт РАН; Институт государства и права РАН; Институт научной информации по общественным наукам РАН; Институт истории естествознания и техники им. С.И. Вавилова РАН; Институт проблем развития науки РАН; Московский...»

«СИБИРСКИЙ УНИВЕРСИТЕТ ПОТРЕБИТЕЛЬСКОЙ КООПЕРАЦИИ ПРОГРАММА ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ ПО СПЕЦИАЛЬНОСТИ 260807. 51 Технология продуктов общественного питания Новосибирск ВВЕДЕНИЕ Вступительные испытания для абитуриентов, поступающих на специальность 260807.51 Технология продуктов общественного питания, проводятся в форме собеседования. Программа вступительных испытаний составлена с учетом требований государственного образовательного стандарта начального профессионального образования, для лиц...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ Утверждаю Ректор СФУ _ Е.А Ваганов _ 2012 г. Основная профессиональная образовательная программа послевузовского профессионального образования (аспирантура) по специальности 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям) Присуждаемая ученая степень -...»

«СИСТЕМА КАЧЕСТВА ОСНОВНАЯ ПРОФЕССИОНАЛЬНАЯ ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА с. 2 из 14 ПОСЛЕВУЗОВСКОГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПО СПЕЦИАЛЬНОСТИ 05.11.16- ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНЫЕ И УПРАВЛЯЮЩИЕ СИСТЕМЫ (ПО ОТРАСЛЯМ) 1 ОБЩИЕ ПОЛОЖЕНИЯ 1.1 Настоящая основная образовательная программа послевузовского профессионального образования (далее – ОП ППО), реализуемая ФГБОУ ВПО Алтайский государственный технический университет имени И.И. Ползунова (далее – Университет) по подготовке аспирантов по...»

«Автономная некоммерческая организация высшего профессионального образования РЕГИОНАЛЬНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ Принято на заседании Ученого совета 14. 01. 2013 г., протокол №5 Утверждаю Ректор АНО ВПО РФЭИ С.Л. Аксенов 14 января 2013 г. ОТЧЕТ о результатах самообследования МАГИСТЕРСКИХ ПРОГРАММ (080100.68 Экономика; 080200.68 Менеджмент) укрупненной группы направлений подготовки и специальностей 080000 Экономика и управление АНО ВПО Региональный финансово-экономический институт г....»

«Министерство образования и науки Российской Федерации Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Томский политехнический университет УТВЕРЖДАЮ Директор ИГНД Е.Г. Язиков _ _ 2007 г. ТЕХНИКО-ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЕ ПРОЕКТОВ РАЗРАБОТКИ МЕСТОРОЖДЕНИЙ УРАНА ПО МЕЖДУНАРОДНЫМ СТАНДАРТАМ Рабочая программа учебной дисциплины по программе подготовки магистров направления 130100 Геология и разведка полезных ископаемых Институт...»

«1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ ДИАГНОСТИКА И ТЕХНИЧЕСКОЕ ОБСЛУЖИВАНИЕ МАШИН ЛЕСНОГО ХОЗЯЙСТВА И ЛЕСНОЙ ПРОМЫШЛЕННОСТИ ПРОГРАММА Для подготовки к вступительным испытаниям выпускников средних специальных учебных заведений, поступающих на заочную сокращенную форму получения образования в УО Белорусский государственный технологический университет в 2014 году Введение Краткая характеристика современного...»






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.