 |
Краткие теоретические сведения
|
|
|
|
Лабораторная работа № 5.
Элементы теории графов
Краткие теоретические сведения
В математической теории графов и информатике граф — это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Неориентированный граф — это пара множеств (V,E), где V — множество элементов, называемых вершинами, а E — подмножество множества неупорядоченных пар вершин из V, называемых рёбрами. Говорят, что вершины u и v соединены ребром, если 
.
Вершины и рёбра графа называются также элементами графа, число вершин в графе — порядком, число рёбер — размером графа. Для ребра e = {u,v} вершины u и v называются концевыми вершинами (или просто концами) ребра e. Два ребра называются смежными, если они имеют общую концевую вершину. Две концевые вершины одного и того же ребра называются соседними. Ребро называется петлёй, если его концы совпадают, т.е. e = {v,v}.
Степенью вершины называют количество рёбер, для которых она является концевой (при этом петли считают дважды). Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.
Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром. Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.
|
|
|
Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.
Граф называется:
связным, если для любых вершин u,v есть путь из u в v.
деревом, если он связный и не содержит простых циклов.
полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
двудольным, если его вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2.
планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
Бинарное отношение на множестве вершин графа, заданное как "существует путь из u в v", является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.
Ориентированный граф (сокращенно орграф) G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — это упорядоченная пара вершин (v,w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v 
w ведёт от вершины v к вершине w, при этом вершина w смежна с вершиной v.
Вершина u и ребро е называются инцидентными, если u является концом ребра е, и не инцидентными в противном случае.
Для представления графов чаще всего используют такие формы как матрица смежности, матрица инцидентности, списки.
Матрицей смежностей A(G) графа G называется матрица вида:
|
|
|
Матрицей инцидентности I ориентированного графа G называется матрица вида:
В списках для каждой вершины указывается перечень смежных с ней вершин.
Задание
Согласно номера по списку N определить вариант индивидуального задания по формуле V=N mod 5+1
Создать программу, которая получает и выводит в файл матрицы смежности и инцидентности, соответствующие варианту задания
Причем, исходные данные графа вводятся списками, затем преобразовываются в матрицу смежности, а матрица смежности преобразовывается в матрицу инцидентности.
Используя графический режим граф изображается на экране компьютера, вершины нумеруются (предварительно в тетради создается эскиз будущего изображения).
В отчете обязательными моментами являются распечатка файла с результатами и изображения полученного графа.
1. Области Украины
2. Районы Запорожской области
3. Районы г. Запорожья
4. Страны Европы
5. Страны СНГ
Вопросы для проверки и самопроверки
Что такое граф
В чем необходимость их использования
На примере полученного графа поясните его характеристики (согласно теоретическим сведениям)
Объяснить алгоритмы получения матрицы инцидентности из матрицы смежности и наоборот
Привести примеры использования графов в жизнедеятельности человека
Что такое файл
Почему в работе использование вывода информации в файл рациональнее чем на экран
Какие виды файлов обрабатываются средствами языка программирования Паскаль, какие из них использованы в вашей работе и почему
Каковы основные этапы работы с файлом, укажите их в вашей программе
Каковы основные этапы создания изображения на экране компьютера средствами языка Турбо Паскаль, укажите их в вашей программе
|
|
|
