1. Для взвешенного графа, заданного списком ребер, найти минимальное остовное дерево, воспользовавшись алгоритмом Краскала. Указание: в первой и второй строках




Скачать 136.14 Kb.
Название1. Для взвешенного графа, заданного списком ребер, найти минимальное остовное дерево, воспользовавшись алгоритмом Краскала. Указание: в первой и второй строках
Дата публикации30.03.2013
Размер136.14 Kb.
ТипДокументы
odtdocs.ru > Математика > Документы
1

1. Для взвешенного графа, заданного списком ребер, найти минимальное остовное дерево, воспользовавшись алгоритмом Краскала. (Указание: в первой и второй строках таблицы указаны концевые вершины ребер, а в третьей- веса соответствующих ребер).

7

7

7

7

7

7

1

2

3

4

5

6

5

4

8

1

2

3

4

5

6

2

3

4

5

6

1

8

9

9

1

4

9

16

25

36

20

15

3

17

28

23

14

6

5

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

Пока множество не пусто, добавляем ребра в графе , соблюдая условие: добавление не должно приводить к появлению цикла в

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








2

2 Для взвешенного графа, заданного списком ребер, найти кратчайший путь между вершинами x и y, воспользовавшись алгоритмом Дейкстры. х =1, y= 9 .

1

1

2

2

3

3

4

5

5

6

6

7

7

7

8

10

10

5

2

5

3

6

4

7

8

6

9

7

9

4

8

10

10

9

5

10

7

10

14

9

15

18

21

8

41

11

44

5

15

16

17

5

50

10

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

Каждой вершине сопоставим метку — минимальное известное расстояние от этой вершины до . На каждом шаге он «посещаем» одну вершину и пытаемся уменьшать метки. Алгоритм завершен, когда все вершины посещены.

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

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




Вершина

Метка

1

0

2

7

3

21

4

32

5

10

6

16

7

27

8

42

9

48

10

43



Кратчайший путь от вершины 1 до 9 равен 48, пролегает через вершины

1, 2, 6, 7, 10, 9.
3

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

Определим функцию таблицей истинности:










0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1


Для построения СДНФ выпишем все наборы, на которых функция равна 1: 001, 101, 111.

Для каждого набора построим элементарную конъюнкцию, равную единице на этом наборе:


Соединяя эти конъюнкции знаками дизъюнкции, получаем СДНФ заданной функции:


4

Для булевой функции , заданной вектором значений, найти совершенную конъюнктивную нормальную форму

.

Для булевой функции , заданной вектором значений, найти полином Жегалкина

Определим функцию таблицей истиности:









0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

1

Для построения СКНФ выпишем все наборы, на которых функция равна 0:

Для каждого набора построим элементарную конъюнкцию, равную единице на этом наборе:



Соединяя эти конъюнкции знаками дизъюнкции, получаем СКНФ заданной функции:



5

Для булевых формул F и G проверить, являются ли они эквивалентными.

















0

0

0

1

1

1

1

1

0

0

1

1

1

1

1

1

0

1

0

0

1

1

1

1

0

1

1

1

1

1

1

1

1

0

0

1

0

1

1

1

1

0

1

1

0

1

0

0

1

1

0

0

1

0

1

1

1

1

1

1

0

0

0

1


Сравнивая в таблице истинности столбцы, соответствующие и , делаем вывод, что данные булевы формулы не эквивалентны.


6

Проверить, является ли система булевых функций A полной.













0

0

1

0

1

1

0

1

1

1

0

1

1

0

0

1

1

0

1

1

0

0

0

1


Выясним принадлежность функции к классам и результаты занесем в таблицу Поста:
















-

+

-

-

-


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

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

Добавить документ в свой блог или на сайт

Похожие:

Алгоритмы на графах
Для заданного графа выполните следующие задания (при необходимости пронумеруйте вершины графа)

Решение Метод Беллмана-Форда
Найти все возможные маршруты, количество рёбер, в которых может быть [0; n 1], где n ϵ n и n – это количество вершин графа

1. Формулировка задачи Примеры
Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов...

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

Задачи для подготовки к экзамену 1 даны длины сторон прямоугольного...
Треугольник задан координатами своих вершин. Найти периметр и площадь треугольника

Решите 4 задачи из своего варианта. Используйте для ввода информации...
Используйте для ввода информации во всех задачах файл input txt, вывод — output txt

Вопрос: Вправе ли организация принимать ндс к вычету по счетам-фактурам,...
Ндс к вычету по счетам-фактурам, полученным от поставщика, в случае если в строках 3 "Грузоотправитель и его адрес" и 4 "Грузополучатель...

Управление Пенсионного фонда Российской Федерации
Жюри рассмотрит работы, опубликованные или вышедшие в эфир до 31 октября 2012 года, и определит победителей в 18 номинациях, в каждой...

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

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

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
odtdocs.ru
Главная страница