Теория графов

Цель работы: Ознакомиться с основными понятиями и определениями графа, способами задания графов и видами графов.

Порядок выполнения работы:

Практическая работа рассчитана на 2 часа аудиторных занятий, включающих в себя следующее:

1. Изучить:

- Основные понятия и определения. Понятие графа.

- Способы задания графов. Виды графов.

- Смежность, инцидентность.

2. Решить упражнения к данному разделу. Выполнить каждый пункт упражнения согласно варианту. Вариант определяется как сумма двух последних цифр зачётной книжки, если количество заданий в пункте упражнения меньше, чем полученная цифра, то эта цифра делится пополам (берётся её целая часть).

3. Оформить отчет о проделанной работе в соответствии с требованиями.

4. Проработать контрольные задания СРС.

Требования к отчету:

Отчет по практической работе распечатывается в виде твердой копии и состоит из следующих пунктов:

Вариант индивидуального задания;

Результаты полученных решений заданий;

Ответы на контрольные задания СРС.

Методические указания

Граф G задается множеством точек или вершин х₁ x₂,..., х_n (которое обозначается через X) и множеством линий или ребер a₁, а₂,..., а_m (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (X, А).

Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом. Если ребра не имеют ориентации, то граф называется неориентированным.В случае когда G = (X, А) является ориентированным графом и мы хотим пренебречь направленностью дуг из множества А, то неориентированный граф, соответствующий G, будем обозначать как G = (X, А).

В этой книге, когда дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т. е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин X и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества X в X, а граф в этом случае обозначается парой G = (X, Г).

а) Ориентированный граф; б) неориентированный граф; в) смешанный граф.

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

Для алгебраического задания графов используются матри­цы смежности и инцидентности.

Матрица смежностиA =(a_ij)определяется одинаково для ориентиро­ванного и неориентированного графов. Это квадратная матрица порядка n, где n - число вершин, у которой

a_ij =

Матрица смежности полностью задает граф.

Матрицей инцидентностиB = (b_ij) ориентированного графа называет­ся прямоугольная матрица (n ´ m), где n – число вершин, m – число ребер, у которой

b_i =

Для неориентированного графа матрица инцидентности B задается следующим образом:

b_i =

Матрица инцидентности, также, как и матрица смежности, полностью задает граф.

Матрицы смежности и инцидентности удобны для задания графов на ЭВМ.

Упражнения для выполнения:

1. Задача. Дан ориентированный граф G0 = (X, R) рис. Найти множество достижимости и множество контрдостижимости вершины Х2. Выяснить какими свойствами обладает бинарное отношение R. Построить матрицу смежности и матрицу инцидентности орграфа G0.

2. Дан неориентированный граф G = (X, U) рис. Занумеруйте вершины графа и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G. Занумеруйте рёбра графа и запишите его матрицу инцидентности.

Контрольные задания для СРС

1. Перечислите все возможные способы задания графов.

2. Что характеризует сумма элементов столбца матрицы смежности неориентированного графа?

3. Как по матрице смежности определить число ребер неориентиро­ванного графа?

4. Как по матрице инцидентности, не рисуя граф, определить его матрицу смежности?

Дата добавления: 2015-07-26; просмотров: 404; Нарушение авторских прав

Мы поможем в написании ваших работ!