Расчетно-графическая работа «Элементы теории графов» по разделу 2.

Вариант 1

1. Дана матрица смежности графа:

Изобразить граф на рисунке.

2. Привести пример четырехвершинного графа, имеющего

две вершины степени 3.

3. Указать все цепи, связывающие вершины и в графе,

изображенном на рис. 1.

Рис. 1

4. Найти все связные графы с 4 вершинами

5. Дан граф, изображенный на рис. 1. Записать матрицу инциденций

\графа.

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

Вариант 2

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

2. Определить, планарен ли граф, изображенный на рис. 1.

Рис. 1

3. Дан граф, изображенный на рис. 2. Записать матрицу инциденций

графа.

Рис. 2.

4. Указать все цепи, связывающие вершины и в графе,

изображенном на рис. 3.

Рис. 3

5. На рис. 4 дан сетевой график. Требуется:

1) ввести обозначения вершин и ребер;

2) построить дерево путей сетевого графика и найти по нему критический путь;

3) построить таблицу позволяющую найти критический путь и резервы времени.

6. Найти граф, имеющий матрицу смежности

Вариант 3

1. Найти матрицу смежности графа, изображенного на рис. 1

Рис. 1

2. Указать не планарный пятивершинный граф

3. Найти все неизоморфные деревья с шестью вершинами

4. Дана матрица смежности графа:

Изобразить граф на рисунке.

5. Определить, планарен ли граф, изображенный на рис. 1.

Рис. 1

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

Вариант 4

1. Найти объединение и пересечение графов, изображенных

на рис. 1

Рис. 1

2. Дан граф, изображенный на рис. 2. Записать матрицу инциденций

графа.

Рис. 2.

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

4. Привести пример пятивершинного гамильтонова графа.

5. На рис. 3 дан сетевой график. Требуется:

1) ввести обозначения вершин и ребер;

2) построить дерево путей сетевого графика и найти по нему критический путь;

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

Рис. 3

6. Дана матрица смежности графа:

Изобразить граф на рисунке.

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

Основная литература

Москинова Г.И.Дискретная математика. Математика для менеджера в примерах и упражнениях: учеб. пособие. – М.: Логос, 2002. – 240 c.

Лихтарников Л.М., Т.Г.Сукачева. Математическая логика: Курс лекций. Задачник-практикум. Решения. – СПб.: Лань, 2008. – 288 c.

Судоплатов С.В., Е.В.Овчинникова. Элементы дискретной математики: учеб. – М.: ИНФРА-М; Новосибирск: НГТУ, 2003. – 280 c.

Дополнительная литература

Андерсон Д.А. Дискретная математика и комбинаторика: пер. с англ./ – М.: Изд. дом «Вильямс», 2003. – 960 c.

Хаггарти Р. Дискретная математика для программистов: пер. с англ. М.: Техносфера, 2003. – 315 c.

Болтянский, В.Г., Савин А.П. Беседы о математике: Кн. 1. Дискретные объекты. – М.: ФИМА, МЦНМО, 2002. – 368 c.

8. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Не предусмотрено.

Рабочая программа дисциплины

«Дискретная математика»

Подписано в печать _________. Формат 60´ 84/16. Бумага для множ. аппаратов.

Печать плоская. Усл. печ. л. ___. Уч.-изд. л.____. Тираж ____ экз. Заказ № ____.

ФГАОУ ВПО «Российский государственный профессионально-педагогический университет». Екатеринбург, ул. Машиностроителей, 11.

Ризограф ФГАОУ ВПО РГППУ. Екатеринбург, ул. Машиностроителей, 11.