Студопедия Главная Случайная страница Обратная связь

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

Элементы теории графов




 

Пара множеств называется графом, если элементами множества являются двухэлементные подмножества множества . Принято называть: множеством вершин или узлов, - множеством ребер графа . Если , то вершины и ,называют концами ребра , которое соединяет их. На рисун­ках вершины изображают точками или кружками, ребра — от­резками прямых или кривых. На рис. 1.14. приведен граф множеством вершин и множеством ребер .

  A B C D
A
B
C
D

 

  A B C D
(A,B)
(B,C)

Рис. 1.14. Неориентированный граф и его матрицы смежности и инцидентности

 

Матрицей смежности графа называется матрица размера , содержащая в пересечении строки и столбца единицу, если и ноль — в противном случае.

Ясно, что матрицы смежности графов симметричны относительно главной диагонали, поэтому в памяти ком­пьютера их можно представлять верхним или нижним треуголь­ником.

Матрицей инцидентности графа называется матрица размера , содержащая в пересечении строки и столбца единицу, если конец ребра .

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

Пара множеств называется ориентированным гра­фом, или короче — орграфом, если элементами множества яв­ляются двучленные последовательности элементов множества . Здесь тоже называется множеством вершин или узлов, а множеством дуг или ориентированных ребер. Запись будем использовать для обозначения дуги и говорить, что она выходит из вершины и входит в вершину , или начало, конец дуги. На рисунках дуги изображают стрелками. На рис. 1.15 приведен орграф , где . Петлей называется дуга вида , но мы будем рассматривать орграфы без петель. Дуга называется обратной по отношению к дуге , а в паре их называют взаимно обратными.

A B C D
A
B
C
D

 

  A B C D
-1
-1

Рис. 1.15. Ориентированный граф и его матрицы смежности и инцидентности

Соотнесенный орграф для неориентированного графа получается из заменой каждого ребра парой взаимно обратных дуг, а соотнесенный неориентированный граф для орграфа получается из заменой каждой дуги и каждой пары взаимно обратных дуг на ребро. Если две вершины связаны ребром или дугой, то говорят, что эти ребро или дуга инцидентны им, а сами вершины называют смежными или соседями. Степенью вершины называется число инцидентных ей ребер или дуг. Вершина с ну­левой степенью называется изолированной, с единичной — тупиковой. В орграфах число входящих в вершину (выходящих из вершины) дуг называется степенью входа (выхода}, а неизолированная вершина с нулевой степенью входа (выхода) называется истоком (стоком). В графе : вершины и смежны, — изоли­рованная, и — тупиковые вершины. В орграфе имеем: вершины и - истоки с единичной степенью выхода, вершина сток со степенью входа два.

Далее будем использовать термин «граф», если неважно, о каком типе графа идет речь или если тип графа ясен из контекста. Хотя большинство следующих определений будет дано для не­ориентированных графов, все они, естественно, переносятся на орграфы. Особые пояснения для орграфов даются в скобках.

 

 







Дата добавления: 2015-08-30; просмотров: 253. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.01 сек.) русская версия | украинская версия