Контрольная работа по дискретной математике

Задать граф следующими способами: перечислением матрицами смежности и инцидентности. Определить следующие основные характеристики графа: число ребер и дуг; число вершин; коэффициент связности графа; степени всех вершин; цикломатическое число графа. Коэффициент связности графа...

2014-06-23

21.44 KB

79 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


Федеральное агентство по образованию Российской Федерации

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

Контрольная работа по дискретной математике

Вариант № 21

Выполнил: студент группы

АУЗ – 161с Тюляева И.А.

Проверил: Акулов Л.Г.

Волгоград 2010


Дано вариант №21:

Задание 1. Задать граф следующими способами: перечислением, матрицами смежности  и инцидентности.

 Решение:

Способ перечисления:

Множество вершин: X={x1, x2, x3, x4, x5}

Множество связей: V={<x1 x2>, <x1 x3>, <x2 x4>, <x3 x4>, <x3 x5>}

Множество изолированных вершин: пусто.

Матрица инцидентности:

V1

V2

V3

V4

V5

X1

1

1

0

0

0

X2

-1

0

0

0

1

X3

0

-1

1

1

0

X4

0

0

0

-1

-1

X5

0

0

-1

0

0

Матрица смежности:

X1

X2

X3

X4

X5

X1

0

1

1

0

0

X2

0

0

0

1

0

X3

0

0

0

1

1

X4

0

0

0

0

0

X5

0

0

0

0

0


Задание 2.

Определить следующие основные характеристики графа:

  •  число ребер и дуг;
  •  число вершин;
  •  коэффициент связности графа;
  •  степени всех вершин;
  •  цикломатическое число графа.

Решение:

Число ребер – 0. Число дуг – 5.

Число вершин – 5.

Коэффициент связности графа – 1.

Степени всех вершин:

Х1

Х2

Х3

Х4

Х5

Полустепень исхода

2

1

2

0

0

Полустепень захода

0

1

1

2

1

Степень

2

2

3

2

0

Цикломатическое число графа = (число связей – число вершин) + коэффициент связности. Т.е. 5-5+1=1; цикломатическое число равно 1.

Задание №3.

Определить, является ли данный граф:

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

Решение:

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

Данный граф не является двудольным, т.к. имеет циклы нечетной длины. Преобразуем данный граф в двудольный путем добавление новой вершины X6, новой связи V6 и переносом связи V4 в другое положение:

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

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

Преобразуем данный граф в мультиграф:

Преобразуем данный граф в псевдограф:

Задание 4. Привести пример подграфа, частичного графа и частичного подграфа.

Решение:

Подграф:

Частичный подграф:

Частичный граф:

Задание 5. Произвести реберную и вершинную раскраски  графа с определением вершинного и реберного хроматического числа.

 Решение:

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

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

Вершинная раскраска:

Хроматическое число равно 2

Реберная раскраска:

Хроматическое число равно 3

Задание 6. Упорядочить граф матричным способом и построить порядковую функцию, функцию Гранди.

 Решение:

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

X1

X2

X3

X4

X5

X1

0

1

1

0

0

X2

0

0

0

1

0

X3

0

0

0

1

1

X4

0

0

0

0

0

X5

0

0

0

0

0

1

2

1

2

0

0

2

0

0

0

*

*

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

Функция Гранди:

Порядковая функция:

Задание 7. Определить метрические характеристики графа: диаметр, радиус, эксцентриситет каждой вершины, центральные вершины.

 Решение:

1. Определим расстояния между парами вершин:

d(x1,x2) = 1

 d(x1,x3) = 1  d(x2,x3) = 2

 d(x1,x4) = 2  d(x2,x4) = 1  d(x3,x4) = 1

 d(x1,x5) = 2  d(x2,x5) = 3  d(x3,x5) = 1  d(x4,x5) = 2

2. Определим диаметр как d(G) = max d(xi, xj): d(G)=3

3. Определим эксцентриситет каждой вершины:

 r(x1) = 2 r(x2) = 3 r(x3) = 2 r(x4) = 2 r(x5) = 3

4. Определим радиус графа как r(G) = min r(xi): r(G) = 2

5. Определим центральные вершины: x1, x3, x4.


V2

V1

V5

V4

V3

X1

X2

X4

X3

X5

V2

V1

V5

V4

V3

X1

X2

X4

3

X5

X1

X2

X4

X6

X3

X5

V3

V2

V5

V6

V4

V1

V2

V1

V5

V3

X1

X2

X4

X3

X5

V2

V1

V5

V4

V3

X1

X2

X4

X3

X5

V2

V1

V5

V4

V3

X1

X2

X4

X3

X5

V2

V1

V5

V4

X1

X2

X4

X3

V2

V1

X1

X2

X3

V2

V1

V5

V3

X1

X2

X4

X3

X5

1

2

1

2

1

1

2

1

3

2

Уровни

0

1

X3

X4

X1

X2

X5

Уровни

0

1

1

0

2

1

0

2

1

0

1

0



 

Другие похожие работы, которые могут вас заинтересовать.
13249. Контрольная работа по прикладной фотограмметрии 437.96 KB
  Дистанционное зондирование используется для сбора и записи информации о морском дне о Солнечной системе об атмосфере Земли. Космические аппараты дистанционного зондирования Земли используются для изучения природных ресурсов Земли и решения задач метеорологии. Космические аппараты для исследования природных ресурсов оснащаются в основном оптической или радиолокационной аппаратурой. Науки ориентированные на полевые работы к числу которых относятся такие как геология лесоводство и география также обычно используют дистанционное...
11013. Использование дидактических игр в обучении математике в первом классе 81.37 KB
  Существуют особые «сензитивные» периоды, когда дети активно «впитывают» все окружающее. Таким периодом является младший школьный возраст. У первоклассника нет лучшего пути математического становления, кроме как в игровой деятельности.
1137. Использование различных организационных форм при обучении математике в 3 классе 110.18 KB
  Цель исследования: изучение возможности осуществления фронтальной индивидуальной и групповой форм работы на уроках математики в начальных классах и выявление их влияния на развитие личности ребёнка на усвоение им математических знаний и умений на классный коллектив в целом. Структура и объём дипломной работы. Общий объём работы 62 страниц. Очевидно что для классификации различных форм работы на уроке понимания их сущности разработки способов их организации и осуществления использования рационального сочетания фронтальной групповой и...
18080. Дидактическая игра как средство развития познавательных способностей младших школьников при обучении математике 473.69 KB
  Дидактические игры и занятия способны давать хороший результат лишь в том случае если преподаватель ясно представляет какие задачи смогут быть решены в процессе проведения игры и в чем особенности проведения этих занятий в период раннего детства. Велико воспитательное значение математики: она открывает младшим школьникам дидактические игры занимательного характера. В результате игры на равных в работу включаются как хорошо подготовленные ученики так и слабые учащиеся. В этой книге он знакомит нас со своими мыслями о воспитании детей в...
11832. Адаптированная образовательная программа по математике во 2 –ом Б классе для учащегося с легкой степенью умственной отсталости 103.85 KB
  Теоретические аспекты психологических особенностей детей с умственной отсталостью. Опыт психологического сопровождения детей с умственной отсталостью в Крыму. Педагогические навыки сопровождения детей с умственной отсталостью приобретенные на базе МБОУ Сакская средняя школа № 2 Республики Крым...
3933. Работа с массивами в PHP 8.92 KB
  Вставка удаление и замена элементов в массиве Функция rry_push добавляет один или несколько элементов в конец массива а функция rry_pop удаляет последний элемент массива. Функция rry_splice удаляет length элементов массива начиная со смещения offset и если задан третий параметр заменяет удаленные элементы элементами массива replcement если параметр length не задан удаляются элементы до конца массива. Функция rry_unique удаляет из массива повторяющиеся значения оставляя только одно из них. Функция rry_merge сливает...
10584. Работа над словарем 12.01 KB
  Работа над лексическим запасом является одной из основных целей и задач в методике преподавания иностранного языка и наряду с этим одной из самых сложных проблем по ряду причин одной из которых является динамичный характер лексики. Что касается лексического состав современного немецкого языка то количество лексических единиц используемых носителями языка в повседневном общении Stndrtsprche колеблется в пределах от 300. Совершенно очевидно что освоить такой объем сложно если не сказать не возможно даже носителю языка не говоря уже о...
19204. Работа с прессой 31 KB
  Предоставление материалов для печати, на основе которых затем журналистами готовятся сообщения, репортажи, статьи, очерки; ответы на запросы прессы и предоставление комплексных информационных услуг (возможности для журналистов по сбору и технической обработке исходной информации), мониторинг - отслеживание, анализ и оценка сообщений печати, радио и телевидения. Принятие мер, при необходимости, по исправлению ошибок в сообщениях и выступление с опровержениями.
14839. Работа с текстом в CorelDraw 184.46 KB
  Изменение расположения символов текста Виды текста В Corel Drw существует два вида текста художественный и простой. Художественный текст можно модифицировать как любой графический объект при этом он не перестает быть текстом даже после применения эффектов. Однако...
17402. Племенная работа в собаководстве 16.13 KB
  Идеология племенной работы в FCI заключается в том что разведение собак должно быть основано на долгосрочных целях и обоснованных основополагающих принципах. В нем в частности указано: племенная деятельность осуществляется только с использованием функционально и генетически здоровых психически крепких породистых собак; генетически здоровой считается породистая собака в том случае если она передает по наследству стандартные отличительные качества породный тип и типичное для породы поведение но при этом не...
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.