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




Скачать 338.77 Kb.
Название Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой
страница 3/4
Дата публикации 21.05.2014
Размер 338.77 Kb.
Тип Методическое пособие
literature-edu.ru > Математика > Методическое пособие
1   2   3   4

Сетевые графы.

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

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

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

(числа – технологические операции)

1 – начало работ, 2 – рытье котлована, 3 – монтаж фундамента,

4 – завоз металлоконструкций, 5 – монтаж подъемного крана,

6 – монтаж каркаса здания.
1

2

3

4

6
5


Рис. 14
Применение теории графов
Возникает вопрос: так ли нужны были графы в задачах? Разве нельзя прийти к решению логическим путем? Можно, но графы придали условиям наглядность, упростили решение и выявили сходство задач. Есть задачи, графы которых имеют сто и более вершин. А ведь именно такие задачи приходится решать современным инженерам и экономистам. Сейчас почти в любой отрасли науки и техники встретишься с графами: в электротехнике – при построении электрических схем; в химии и биологии – при изучении молекул и их цепочек; в экономике – при решении задач выбора оптимального пути для потоков грузового транспорта.

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

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

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


Рис. 15


Пример применения графов на производстве:



Рис.16
Смешанные

Оптоэлектрические

Механические

Электронные

Вычислительные машинмашины

Аналоговые

Цифровые

Комбинированные

Смена 1

Смена 2

Смена 3

Бригада 1

Бригада 2

Бригада 3

Предприятие

Цех 1

Цех 2
Другие цеха
Смена 1

Смена 2

Смена 3

Бригада 1

Бригада 2

Бригада 3
Практическая часть по теме «Графы»

Задача 1. Изобразите графически:

  1. Неориентированное и ориентированное ребра;

  2. Плоский граф,

  3. Полный неориентированный граф на трех, четырех, пяти вершинах;

  4. Неполный ориентированный граф на пяти вершинах;

  5. Петлю графа;

  6. Неориентированный и ориентированный мультиграф.

Решение:

1)


V2
Неориентированное ребро Ориентированное ребро


V2

V2

V2




V1

V3
2)


V4




V5




V1

V2

6)

V2

V1

5)

V5

V4

V3

V2

V1

4)

V1

V1

V5

V4

V3

V2

V4

V3

V2

V3

V2

V1
3)

Задача 2. Докажите, что в полном графе с n вершинами ребер.

Решение. Каждой вершине в полном графе с n вершинами принадлежит n – 1 ребро, но в произведении n(n-1) каждое ребро учтено дважды (так как одно ребро инцидентно двум вершинам). Следовательно, число ребер в полном графе с n вершинами равно .

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

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

Каждая вершина графа с девятью вершинами может иметь степень 0,1,2,3,4,5,6,7,8. Предположим, что существует граф G, все вершины которого имеют разную степень, то есть каждое из чисел последовательности 0,1,2,3,4,5,6,7,8 является степенью одной и только одной из его вершин. Но этого не может быть, так как если в графе есть вершина Vi степени 0, то в нем найдется вершина Vj со степенью 8. Эта вершина Vj должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с вершиной Vi , поэтому степень вершины Vi не может равняться 0. Таким образом, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой. Таким образом, доказано, что в любой момент найдутся хотя бы два шахматиста, сыгравшие одинаковое количество партий.

Задача 4. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими?

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

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

G2

G1


Задача 5. Из пункта А в пункт В выехали пять машин одной марки разного цвета: белая, черная, красная, синяя, зеленая. Черная едет впереди синей, зеленая – впереди белой, но позади синей, красная впереди черной. Какая машина едет первой и какая последней?

Ч

К

З

С

Б



Анализируя граф, получаем следующий порядок движения: красная, черная, синяя, зеленая, белая.
Задача 6. Пусть даны графы G1 и G2. Установите, изоморфны они или нет.

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

Запишем элементы xX и yY с соответствующими им парами чисел, где первое число – число исходов из вершины, а второе – число заходов в вершину. Далее определим частичную подстановку, соединяя вершины xi и yi с одинаковыми числами.

x1(1,1) x2(1,1) x3(3,2) x4(1,2) x5(2,2) x6(2,2) x7(1,1)


y1(2,2) y2(1,1) y3(2,2) y4(1,1) y5(1,2) y6(1,1) y7(3,2)
В результате получим подстановку x1 x2 x3 x4 x5 x6 x7

y4 y2 y7 y5 y3 y1 y6

Следовательно, графы G1 и G2 изоморфны.

Задача 7. Для неориентированного графа построить матрицу смежности и матрицу инцидентности.

D

С




7

4

3

6

2

А


E

B




1

5


Решение: Матрица смежности: А 0 1 1 0 0

В 1 0 1 0 1

C 1 1 0 1 1

D 0 1 1 0 0

E 0 1 1 1 0

A B C D E
Матрица инцидентности: А 1 1 0 0 0 0 0

В 1 0 0 0 1 1 0

C 0 1 1 0 0 1 1

D 0 0 1 1 0 0 0

E 0 0 0 1 1 0 1

1 2 3 4 5 6 7
Задача 8. Найдите эйлеров цикл в эйлеровом графе.


А

8

7

6

5

4

3

2

1


Решение: После выбора вершины А и прохождении ребер 1 и 2 имеются три возможности выбора: ребра 3,6 или 7. Выбираем ребро 3 или 6. Например, ребро 3. Далее обходим оставшиеся ребра и получаем эйлеров цикл 1,2,3,4,5,6,7,8.

Задача 9. Найдите цикл, содержащий все вершины, причем в точности по одному разу каждую.
Решение: Этот цикл: 1,2,3,4,5,6,19,18,14,15,16,17,7,8,9,10,11,12,13,20.

17

16




6

2

4

5

7

8

3

15

10

12

13




9



11






1



20

19

18

15

14



Упражнения для самостоятельного выполнения

1. Граф задан таблицей смежности.

1) Постройте изображение этого графа, укажите степени его вершин;

2) Постройте матрицу инцидентности этого графа.

а) б)

V

V1

V2

V3

V4

V5

V6




V

V1

V2

V3

V4

V5

V6

V1







1




1

1

V1







1

1







V2

1




1




1




V2










1




1

V3




1

2










V3

1










1

1

V4










2







V4

1

1







1




V5

1

1










1

V5







1

1

2




V6

1










1




V6




1

1










в) г)

V

V1

V2

V3

V4

V5

V6




V

V1

V2

V3

V4

V5

V6

V1







1

1







V1

2







1







V2




2

1







1

V2







1







1

V3

1

1




1







V3




1




1

1




V4

1




1




1

1

V4

1




1







1

V5










1







V5







1







1

V6

1

1




1







V6




1




1

1




д) е)

V

V1

V2

V3

V4

V5

V6




V

V1

V2

V3

V4

V5

V6

V1













1

1

V1







1

1







V2




2










1

V2













1

1

V3










1







V3

1







1




1

V4







1




1

1

V4

1




1




1




V5

1







1







V5




1




1







V6

1

1




1







V6




1

1







2

1   2   3   4

Похожие:

Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Сергей Николаевич Бердышев Технологии работы с клиентами разной трудности
Пособие содержит большое количество кейсов, с помощью которых легко понять особенности работы с различными заказчиками. Книга рассчитана...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Наркотическая угроза: знать, чтобы выжить!
Теперь совершенно очевидно, что она характерна не только для стран Западного мира. Этим злом оказались поражены народы всех континентов...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Методические указания по написанию контрольных работ 26 Ким для аттестации остаточных знаний 28
Учебно-методическое пособие предназначено для студентов направления: 080100, 080200, 100100, 100400, 230400, 072500
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Международные валютные отношения и валютный рынок Методическое пособие
Методическое пособие предназначено для студентов, обучающихся по специальности «Финансы и кредит» заочной формы обучения
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебно-методическое пособие для студентов Нижний Новгород 2009
Темперамент, Характер. Воля: Учебно-методическое пособие для студентов. Н. Новгород: нгпу, 2009. 42с
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебно-методическое пособие для проведения практических занятий для...
Методы научных исследований: учебно-методическое пособие для проведения практических
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебно-методическое пособие Н. Новгород
...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебно-методическое пособие для студентов специальностей «История»
Шинаков Е. А., Поляков Г. П., Чубур А. А. Основы восточноевропейской археологии (учебно-методическое пособие). – Брянск, рио бгу,...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon И самостоятельной работы студентов
Учебное пособие предназначено для студентов Волжского государственного инженерно-педагогического университета, обучающихся по специальности...
Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой icon Учебное пособие Текст предоставлен правообладателем Логопатопсихология:...
«Логопатопсихология: учеб пособие для студентов / под ред. Р. И. Лалаевой, С. Н. Шаховской.»: Гуманитарный издательский центр владос;...
Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции