Студопедия — Элементы теории графов
Студопедия Главная Случайная страница Обратная связь

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

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






 

Пара множеств называется графом, если элементами множества являются двухэлементные подмножества множества . Принято называть: множеством вершин или узлов, - множеством ребер графа . Если , то вершины и ,называют концами ребра , которое соединяет их. На рисун­ках вершины изображают точками или кружками, ребра — от­резками прямых или кривых. На рис. 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; просмотров: 807. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Сущность, виды и функции маркетинга персонала Перснал-маркетинг является новым понятием. В мировой практике маркетинга и управления персоналом он выделился в отдельное направление лишь в начале 90-х гг.XX века...

Разработка товарной и ценовой стратегии фирмы на российском рынке хлебопродуктов В начале 1994 г. английская фирма МОНО совместно с бельгийской ПЮРАТОС приняла решение о начале совместного проекта на российском рынке. Эти фирмы ведут деятельность в сопредельных сферах производства хлебопродуктов. МОНО – крупнейший в Великобритании...

ОПРЕДЕЛЕНИЕ ЦЕНТРА ТЯЖЕСТИ ПЛОСКОЙ ФИГУРЫ Сила, с которой тело притягивается к Земле, называется силой тяжести...

Дренирование желчных протоков Показаниями к дренированию желчных протоков являются декомпрессия на фоне внутрипротоковой гипертензии, интраоперационная холангиография, контроль за динамикой восстановления пассажа желчи в 12-перстную кишку...

Деятельность сестер милосердия общин Красного Креста ярко проявилась в период Тритоны – интервалы, в которых содержится три тона. К тритонам относятся увеличенная кварта (ув.4) и уменьшенная квинта (ум.5). Их можно построить на ступенях натурального и гармонического мажора и минора.  ...

Понятие о синдроме нарушения бронхиальной проходимости и его клинические проявления Синдром нарушения бронхиальной проходимости (бронхообструктивный синдром) – это патологическое состояние...

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