Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Задание 1. Способы представления графов. Нахождение характеристик графа.






ПРАКТИЧЕСКАЯ РАБОТА № 9.

Тема: «Операции над множествами и графами».

Теоретические сведения.

 

Граф - Пара объектов G = (X, Г), где Х - конечное множество, а Г –конечное подмножество прямого произведения Х*Х. При этом Х называется множеством вершин, а Г - множеством дуг графа G.

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

Если в множестве Г все пары упорядочены, то такой граф называют ориентированным.

Дуга - ребро ориентированного графа.

Граф называется вырожденным, если у него нет рёбер.

Вершина Х называется инцидентной ребру G, если ребро соединяет эту вершину с какой-либо другой вершиной.

Подграфом G(V1, E1) графа G(V, E) называется граф с множеством вершин V1 Î V и множеством ребер (дуг) EÎ E, - такими, что каждое ребро (дуга) из E1 инцидентно (инцидентна) только вершинам из V1. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

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

Вершины называются смежными, если существует ребро, их соединяющее.

Два ребра G1 и G2 называются смежными, если существует вершина, инцидентная одновременно G1 и G2.

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

Задание для студентов.

Задание 1. Для орграфа G 1, заданного матрицей смежности,

- нарисовать граф;

- привести теоретико-множественное представление графа;

- задать граф соответствием;

- определить полустепени исхода и захода всех вершин;

- определить количество петель графа;

- построить матрицу инциденций;

- построить список концов ребер.

Задание 2. Для орграфов G 1 и G 2, выполнить бинарные операции матричным способом: объединения; пересечения; разности, кольцевой суммы.

 

Задание 3. Для орграфа G 1 выполнить операции: дополнения; удаление вершины xi; удаление дуги ai; отождествление вершин xi и xj;

- стягивание дуги ai.

Примечание: номера вершин i и j выбрать самостоятельно.

Вариант Граф G 1 Граф G 2  
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 
 
           
           
           
           
           
           

 

           
           
           
           
           
           

 

 

Примеры решения задач:

Задание 1. Способы представления графов. Нахождение характеристик графа.

Дано: матрица смежности орграфа G 1:
           
           
           
           
           
           

Необходимо для орграфа G 1:

- нарисовать граф;

- привести теоретико-множественное представление графа;

- задать граф соответствием;

- определить полустепени исхода и захода всех вершин;

- определить количество петель графа;

- построить матрицу инциденций;

- построить список концов ребер.

Решение. a) Задана квадратная матрица , размерность которой определяет число вершин графа и отношение между вершинами графа G 1.

b) Теоретико-множественное представление графа задает граф G 1 перечислением множества вершин и дуг:

G 1= (X, A), где X ={ xi }, i =1, 2,..., 5 – множество вершин,

A ={ a i}, i =1, 2,..., 11– множество дуг,

причем a 1 = (x 1, x 3), a 2 = (x 1, x 4), a 3 = (x 1, x 5), a 4 = (x 2, x 1), a 5 = (x 2, x 2), a 6 = (x 2, x 4),
a
7 = (x 3, x 4), a 8 = (x 4, x 1), a 9 = (x 4, x 3), a 10 = (x 5, x 2), a 11 = (x 5, x 4).

В случае задания графа соответствием граф обозначается парой G = (X, Г),

где Г отображение множества Х в Х.

Отображением вершины xi – Г(xi) является множество вершин, в которые существуют дуги из вершины xi, т. е. Г(xi) = { xj / $ дуга (xi, xj) Î A }.

Так для орграфа G 1 задание соответствием выглядит следующим образом:

G 1= (X, A), где X ={ xi }, i =1, 2,..., 5 – множество вершин,

Г(x 1) ={ x 3, x 4, x 5}, Г(x 2) = { x 1, x 2, x 4}, Г(x 3) ={ x 4}, Г(x 4) ={ x 1, x 3}, Г(x 5) ={ x 2, x 4}.

c) Определение полустепеней исхода и захода вершин графа G 1.

Полустепенью исхода вершины xid 0(xi) называется количество дуг исходящих из этой вершины. Полустепенью захода вершины xidt (xi) называется количество дуг, входящих в эту вершину.

Характеристики вершин удобно находить по матрице смежности. Так сумма элементов i-й строки матрицы дает полустепень исхода вершины xi, а сумма элементов i-го столбца дает полустепень захода вершины xi.

Дляграфа G 1 характеристики полустепеней исхода и захода следующие:

d) Определение количество петель графа G 1.

Количество петель графа можно определить по графу визуально или по матрице смежности, определив количество элементов вида aii. В графе G 1 одна петля.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.022 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал