Лабораторная работа Тема графы




Скачать 41.83 Kb.
НазваниеЛабораторная работа Тема графы
Дата публикации03.02.2014
Размер41.83 Kb.
ТипЛабораторная работа
skachate.ru > Информатика > Лабораторная работа



Лабораторная работа



Тема – графы.

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

Будем обозначать граф



где V - множество вершин, а E - множество ребер, причем

– для ориентированного графа и

– для неориентированного графа.

Будем использовать также обозначения | V | = n, | E | = m (мощность множества).

В теории графов классическим способом представления графа является матрица инциденций. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге (x, y)E, содержит "+1" в строке, соответствующей вершине x, "-1" в строке, соответствующей вершине y, и нули во всех остальных строках. Петлю, т.е. дугу вида (x, x), удобно представлять другим значением, например, 2, в строке x. Для неориентированного графа столбец, соответствующий ребру {x, y}, содержит 1 в строках, соответствующих x и y, и 0 - во всех остальных строках.

Второй способ представления графа – с помощью матрицы смежности размера n x n, где = 1, если существует ребро из x и y, и = 0 в противном случае. При этом подразумевается, что ребро {x, y} неориентированного графа идет как от x к y, так и от y к x. Поэтому матрица смежности для неориентированного графа всегда симметрична.

Более экономным в отношении памяти (особенно для неплотных графов, когда m гораздо меньше ) является способ представления графа с помощью списка пар, соответствующих его ребрам. Пара (x, y) соответствует дуге (x, y), если граф ориентированный, и ребру {x, y}, если граф неориентированный.

Лучшим решением во многих случаях является структура данных, которую назовем списками инцидентности. Она содержит для каждой вершины список вершин u, между которыми существуют дуги (v, u) для ориентированного графа, и ребра {v, u} – для неориентированного графа.

Типичные задачи, связанные с графами, – это сравнение графов (скажем, чертежей при распознавании изображений), нахождение кратчайшего пути по карте дорог, составление совместной системы уравнений по электронной цепи, нахождение критического ребра в графе, удаление которого приведет к расщеплению графа на две отдельные, не связанные между собой области.
^

Варианты заданий к лабораторной работе


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

Литература





  1. Костин А.В., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах. – М.: Высш. шк., 1987.

  2. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.

  3. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.

  4. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.

  5. Ленгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. – М.: Мир, 1989.

  6. Флорес И. Структуры и управление данными. – М.: Финансы и статистика, 1982.

  7. Стоун Г.С., Сиворек Д.П. Введение в организацию ЭВМ и структуры данных. – М.: Машиностроение, 1980.

  8. Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс. В двух частях. – М.: Мир, 1990.


^

Приложение


(справочное)

Пример оформления лабораторной работы




Тема

Перечислимые типы и множества

Цель работы

Научиться работать с множествами.

Задание

Дан текст из прописных латинских букв и цифр с точкой в конце. Вывести на экран монитора все буквы и цифры, входящие в текст не менее двух раз.

Алгоритм решения задачи

Описываем два множества:

  • множество латинских букв;

  • множество целых чисел от 0 до 9.

Описываем переменные, а также массивы:

  • letters - массив из 26 элементов, в который будут заноситься количество повторяющихся букв в тексте;

  • dig - массив из 10 элементов, в который заносятся повторяющиеся цифры в тексте.

Переменной a присваиваем множество латинских букв. Переменной d присваиваем множество цифр. Вводим строку символов. Определяем порядковый номер в строке символа "." (точка). Если искомый символ в строке отсутствует, то выводим на экран сообщение об ошибке и прекращаем выполнение программы.

Организуем цикл по символам строки. Последовательно выбираем символы строк и проверяем, какому множеству символов принадлежит текущий символ.
Текст программы

^ Program Labor_1;

uses crt;

type alf: set of 'a'..'z';

type digit: set of '0'..'9';

var str1, str2: string;

c: char;

i, k: integer;

letters: array[0..25] of byte;

dig: array[0..9] of byte;

begin

clrscr;

a:=['a'..'z']; {инициализация множества a}

d:=['0'..'9']; {инициализация множества d}

writeln(' Введите текст из прописных латинских букв');

writeln(' и цифр с точкой в конце.');

readln(str1);

k := Pos('.', str1);

if k = 0 then begin

writeln(' Ошибка входных данных ');

exit; end;

for i:=1 to k-1 do

begin

c:=str1[i];

if c in a then letters[ord( c ) - 97]:=letters[ord( c ) - 97]+1;

if c in d then dig[ord( c )-48]:=dig[ord( c )-48]+1;

end;

writeln;

writeln(' Повторяющиеся буквы более 2 раз:');

for i:=0 to 25 do

if letters[i]>=2 then writeln(chr(i+97), '-', lettrs[i]);

writeln(' Повторяющиеся цифры более 2 раз:');

for k:=0 to 9 do

if dig[k]>=2 then writeln(k, '-', dig[k]);

repeat until keypressed;

end.
Результаты работы программы

Введите текст из прописных латинских букв и цифр с точкой в конце:

hh 44 gggg 4 5 bbb.

Результат выполнения программы:

Повторяющиеся буквы более 2 раз

b - 3

g - 4

h - 2

Повторяющиеся цифры более 2 раз

4 - 3
Выводы

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

Похожие:

Лабораторная работа Тема графы iconЛабораторная работа Графы
Построить стягивающее дерево неориентированного графа методом поиска в ширину и вывести список рёбер дерева. Граф задан в текстовом...
Лабораторная работа Тема графы iconЛабораторная работа по теме «Тема 10. Лабораторная работа «Текстовые файлы»
Цель лабораторной работы состоит в изучении средств vb и средств vs для работы с текстовыми файлами
Лабораторная работа Тема графы iconЛабораторная работа № (из способы задания графов.)
Придумайте 6 графов: орграф, неорграф, мультиграф, псевдограф, несвязный граф, граф с изолированными вершинами. Опишите известными...
Лабораторная работа Тема графы iconЛабораторная работа № Установка и настройка ос семейства Windows...
Лабораторная работа № Изучение сетевых средств операционной системы ms windows. Диагностика сети средствами операционной системы....
Лабораторная работа Тема графы icon2. Графы, деревья, планарные графы; их свойства. Оценка числа деревьев. 4
Логика 1-го порядка. Выполнимость и общезначимость. Общая схема метода резолюций. 5
Лабораторная работа Тема графы iconТема: «Лабораторная работа»

Лабораторная работа Тема графы iconЛабораторная работа №7-9 Тема
Тема: Создание в программе CodeGear rad studio (C++Builder) клиентского приложения по технологии dbExpress для клиент-серверной субд...
Лабораторная работа Тема графы iconТема: Лабораторная работа «Немецкие поэты»

Лабораторная работа Тема графы iconЛабораторная работа №4
Цель: Так как лабораторная работа разделена на варианты, то у данной работы две цели
Лабораторная работа Тема графы iconЛабораторная работа №3 Лабораторная работа №3 " анализ сетевого траффика "
Знакомство со структурой тср/ip-пакетов и с составом его отдельных частей – заголовочной части, блока данных и трейлером

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


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