Практическая работа № 6. Тема:Задание графа различными способами и определение
Тема:Задание графа различными способами и определение
его характеристик
Цели работы:
4) изучить основы теоретико-множественного и графического представлений графов;
5) изучить простейшие свойства графов;
6) изучить основы матричного представления графов.
Пояснения:
Граф – это система, которая интуитивно может быть рассмотрена как множество точек и множество соединяющих их линий (геометрический способ задания графа). Точки называются вершинами графа, линии со стрелками – дугами, без стрелок – рёбрами.
Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.
Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми рёбрами (дугами), соединяющими вершины из этого множества. Если в графе удалить часть рёбер (дуг), то получим частичный граф. Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) – инцидентным соответствующим вершинам. Граф называется полным, если каждые две вершины его соединены одним и только одним ребром.
Вершины в графе могут отличаться друг от друга тем, скольким рёбрам они принадлежат. Степень вершины называется число рёбер графа, которым принадлежит эта вершина. Степень графа ещё называют его валентностью.
Вершина графа, для которой валентность равна 0 является изолированной, для которой равна 1 – висячей. Вершина называется нечётной, если валентность нечётное число. Вершина называется чётной, если валентность чётное число. Степень каждой вершины полного графа на единицу меньше числа его вершин.
Маршрутом в графе называется чередующаяся последовательность вершин и рёбер, в которой любые два соседних элемента инцидентны.
Путём называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги. Простой путь – путь, в котором ни одна дуга не встречается дважды.
Контур – путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).
Цепью называется множество рёбер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь – последовательность смежных вершин. Замкнутая цепь называется циклом. Можно определить простые и элементарные цепи. Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой цепью. Простая цепь (цикл, путь, контур), содержащая все рёбра (дуги) графа называется эйлеровой цепью.
Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.
Связностью графа называется минимальное число рёбер, после удаления которых граф становится несвязным.
Ребро e графа G называется ориентированным, если одну вершину считают началом ребра, а другую – концом, на рисунке его изображают стрелкой между вершинами. Таким образом, граф, все рёбра которого ориентированы, называется ориентированным графом.
Одна и та же вершина ориентированного графа может служить началом для одних рёбер и концом для других, поэтому различают две степени вершины: степень выхода и степень входа. Степенью выхода вершины орграфа называется число выходящих из вершины рёбер.
Степенью входа вершины орграфа называется число входящих в вершину рёбер.
В орграфах в зависимости от сочетаний степеней входа и выхода для данной вершины рассматривается три случая.
Изолированной вершиной называется вершина, у которой и степень входа и степень выхода равна 0. Источником называется вершина, степень выхода которой положительна, а степень входа равна 0. Стоком называется вершина, степень входа которой положительна, а степень выхода равна 0.
Путём в ориентированном графе называется последовательность ориентированных рёбер, т. е. для орграфов цепь называется путём. Простым путём в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза. Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром. Длиной пути называется число рёбер в этом пути.
Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром. Всякий полный ориентированный граф с n вершинами имеет простой ориентированный путь, проходящий через все вершины графа.
Петлёй называется ребро, у которого начальная и конечная вершины совпадают. Петля обычно считается неориентированной.
Мультиграфом называется граф, в котором пара вершин соединяется несколькими различными рёбрами. Для ориентированного мультиграфа вершины могут соединяться несколькими рёбрами в каждом из направлений.
Оборудование, аппаратура, материалы и их характеристики:персональные компьютеры с лицензионным программным обеспечением; доска, маркеры; рабочие тетради; раздаточный материал.
Порядок выполнения работы:
Студенты получают задания по вариантам. Метод решения выбирается студентами самостоятельно и зависит от приобретенных в процессе обучения навыков. В процессе выполнения практической работы преподаватель проводит как групповые, так и индивидуальные консультации по вопросам дополнительного разъяснения отдельных понятий и аспектов изученных тем, задания и оформления отчета.
1. Пусть орграф задан матрицей смежности. Постройте изображение этого графа, укажите степени вершин графа. По матрице смежности постройте матрицу инцидентности этого графа.
Таблица 1 – Задание № 1
| № варианта | Исходные данные | |||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
2. Граф G задан диаграммой.
а) составьте для него матрицу инцидентности;
б) постройте матрицу инцидентности;
в) укажите степени вершин графа;
г) составьте маршрут длиной 5, соединяющий вершину V2 и вершину V5;
д) постройте простой цикл, содержащий вершину V4;
е) определите вид заданного графа.
Таблица 2 – Задание № 2
| № варианта | Исходные данные |
 | |
 | |
 | |
 | |
 | |
 | |
 | |
 | |
 | |
 |
3. Ориентированный граф G (V, X) с множеством вершин V = {1, 2, 3, 4, 5, 6, 7, 8} задан списком дуг X.
а) постройте реализацию графа G;
б) укажите степени вершин.
Таблица 3 – Задание № 3
| № варианта | Исходные данные |
| X = {(1,2), (2,3), (4,3), (4,5), (6,5), (7,6), (7,1), (7,7), (7,2), (6,4), (4,4), (2,7), (6,4), (5,3)} | |
| X = {(1,4), (2,1), (4,3), (4,5), (2,6), (2,6), (7,1), (7,6), (3,2), (5,4), (3,4),(2,2), (6,2), (5,5)} | |
| X = {(1,5), (2,3), (2,3), (4,5), (4,6), (5,6), (5,1), (6,6), (3,2), (5,4), (6,4), (7,2), (6,7), (7,5)} | |
| X = {(1,1), (2,2), (2,3), (3,5), (4,6), (4,6), (5,1), (5,6), (5,2), (6,4), (7,4), (7,2), (7,2), (7,5)} | |
| X = {(1,1), (1,3), (1,3), (2,5), (2,6), (3,6), (3,1), (3,6), (3,7), (4,4), (4,6), (5,2), (6,3), (6,5)} | |
| X = {(1,3), (2,3), (2,3), (3,5), (3,6), (2,7), (4,1), (4,6), (4,2), (6,4), (6,4), (7,2), (6,6), (7,6)} | |
| X = {(1,2), (2,3), (4,3), (4,5), (6,5), (7,6), (7,1), (7,7), (7,2), (6,4), (4,4), (2,7), (6,4), (5,3)} | |
| X = {(1,4), (2,1), (4,3), (4,5), (2,6), (2,6), (7,1), (7,6), (3,2), (5,4), (3,4),(2,2), (6,2), (5,5)} | |
| X = {(1,5), (2,3), (2,3), (4,5), (4,6), (5,6), (5,1), (6,6), (3,2), (5,4), (6,4), (7,2), (6,7), (7,5)} | |
| X = {(1,1), (1,3), (1,3), (2,5), (2,6), (3,6), (3,1), (3,6), (3,7), (4,4), (4,6), (5,2), (6,3), (6,5)} |
Требования к отчету: Отчет должен содержать:
- название практической работы;
- формулировку цели работы;
- краткие теоретические сведения по теме работы в виде таблиц, графиков, диаграмм, схем, рисунков и формул;
- результаты решения заданий;
- выводы по работе;
- краткие письменные ответы на контрольные вопросы.
Текст отчета набирается на компьютере. Допускается тип шрифта Times New Roman, размер 12 – 14, межстрочный 1,5 интервал, выравнивание текста по ширине странице, абзацный отступ 1,25.
Контрольные вопросы:
1) Что называется графом? Ориентированным графом? Приведите примеры.
2) Что такое степень вершины?
3) Перечислите основные понятия, связанные с неориентированными графами.
4) Перечислите основные понятия, связанные с орграфами.
5) В чем состоит аналитический способ задания графа?
6) В чем состоит геометрический способ задания графа?
7) В чем состоит матричный способ задания графа?
8) Что называется маршрутом, циклом и цепью графа?
9) Сформулируйте понятие связности графа. Какой граф называют связным?
10) Какие два графа называются изоморфными?
11) Сформулируйте алгоритм изоморфизма двух графов.
12.Перечислите операции над графами.
Учебная и специальная литература:
1) Спирина М.С., Спирин В.В. Дискретная математика: Учебник. – М.: Издательский центр «Академия», 2009. – 370 с.
2) Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для высш. учеб. заведений. – М.: Издательский центр «Академия», 2009. – 304 с.
3) Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ – Петербург, 2008. – 352 с.