Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Подготовка к контрольной работе № 3



Комплект материалов для подготовки к контрольным мероприятиям для групп МП-21,22,23,24,25 (1-й поток)

И для групп МП-26, 27, 28, 29 (2-й поток)

Модуль 2

Подготовка к контрольной работе № 3

Контрольная работа № 3 состоит из 2-х частей: часть 1 включает 6 заданий, часть 2 – два задания. Правильное решение каждого задания части 1 оценивается 1 баллом. Правильное решение каждого задания части 2 оценивается ориентировочно 2 баллами. Максимальное количество баллов, которое можно получить за контрольную работу № 3, составляет 10 баллов. Начисленные баллы учитываются в рамках накопительной балльной системы.

Контрольная работа № 3 рассчитана на 1 час 20 минут. Структура контрольной работы показана в табл. 1, примерные варианты КР № 3 приведены в таблице 2.

Таблица 1
Описание задания
  Часть 1
Неориентированный граф задан множеством вершин и ребер: а) построить диаграмму; б) указать какой-либо путь, не являющийся цепью; какую-либо цепь, не являющуюся простой цепью; цикл, не являющийся простым; простой цикл (в каждом варианте что-нибудь одно).
Для данного графа найти: а) цикломатическое число; б) хроматическое число.
а) Построить неориентированный граф по матрице смежности (инцидентности); б) Найти матрицу смежности или инцидентности графа.
а) Написать код дерева (в одних вариантах бинарный, в других – из натуральных чисел); б) Построить дерево по коду (в одних вариантах по бинарному, в других – из натуральных чисел).
Ориентированный граф задан множеством вершин и ребер: а) построить диаграмму; б) определить, является ли граф связным, сильно связным.
а) Построить ориентированный граф по матрице смежности (инцидентности); б) Найти матрицу смежности или инцидентности орграфа.
Задача из перечня задач повышенной сложности главы 3 учебного пособия Олейник Т.А. Основы дискретной математики: теория и практика. М.:МИЭТ, 2010.
Задача из перечня задач повышенной сложности главы 3 учебного пособия Олейник Т.А. Основы дискретной математики: теория и практика. М.: МИЭТ, 2010.

 

Таблица 2

  Примерный вариант 1 КР №3
  Часть 1
1. Пусть - граф с вершинами и ребрами , , , , , , . а) Построить диаграмму графа . б) Указать на графе какой-либо путь, не являющийся цепью, и простой цикл.
2. Для графа (задание 1) найти: а) цикломатическое число; б) хроматическое число, указать соответствующую раскраску.
3. а) Построить граф по матрице инцидентности . б) Для графа из п. а) выписать матрицу смежности.
4. а) Нарисовать какое-нибудь дерево с 8-ю ребрами, занумеровать его вершины и построить его код из натуральных чисел. б) Построить дерево по коду (0000010101011111).
5. Пусть - ориентированный граф с вершинами и дугами , , , , . а) Построить диаграмму графа . б) Является ли граф связным? сильно связным?
6. а) Построить граф по матрице смежности . б) Выписать матрицу инцидентности графа из п. а).
Доказать, что в связном графе любые две простые цепи максимальной длины имеют по крайней мере одну общую вершину.
Доказать, что граф непланарен.
  Примерный вариант 2 КР №3
  Часть 1
1. Пусть - граф с вершинами и множеством ребер , , , , , , , , . а) Построить диаграмму графа . б) Указать на графе какую-либо цепь, не являющуюся простой цепью, и простой цикл.
2. Для графа (задание 1) найти: а) цикломатическое число; б) хроматическое число.
3. а) Построить граф по матрице инцидентности . б) Для графа из п.а) выписать матрицу смежности.
4. а) Нарисовать какое-нибудь корневое дерево с 9-ю ребрами и построить его бинарный код. б) Построить дерево по коду[2 2 5 5 5 9 5 9].
5. Пусть - ориентированный граф с вершинами и дугами , , , , . а) Построить диаграмму графа . б) Является ли граф связным? сильно связным?
6. а) Построить граф по матрице инцидентности . б) Выписать матрицу смежности графа из п. а).
Часть 2
7. Показать, что граф с вершинами и двумя компонентами связности имеет не более ребер.
8. Используя теорему Кирхгофа, показать, что число остововв полном графе с помеченными вершинами равно .

Задания 2-й части контрольной работы №3 формулируются на основе и с использованием банка задач, приведенного в учебном пособии Олейник Т.А. «Основы дискретной математики: теория и практика. М.:МИЭТ, 2010»: Л.1. § 3.1 - § 3.8, задачи повышенной сложности 3.1 – 3.42.

Для подготовки к выполнению части 2 контрольной работы № 3 рекомендуется прорешать задачи из этого списка.

 




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

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.