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


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Ему соответствует матрица смежности А.

010010

А= 010111

Замечание: если матрица не является симметричной, то она не может быть матрицей смежности неориентированного графа.

Например: 0111

А= 0001 - несимметрична (а12 ≠а31)=>не

Является матрицей смежности

Графа.

II .ОРИЕНТИРОВАННЫЕ ГРАФЫ.

Определение:

Ребро с графа G называют ориентированным, если одну вершину считают началом ребра, а другую - концом.

На рисунке ориентированное ребро изображают стрелкой между вершинами.

Определение.

Граф, все ребра которого ориентированы, называется ориентированным.

Пример:

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

Определение.

Степенью выхода вершины орграфа называется число выходящих из вершины ребер.

Определение.

Степенью входа вершины орграфа называется число входящих в вершину ребер.

Пример.

В орграфах в зависимости от сочетания степеней входа и выхода для данной вершины рассматриваются три случая:

Изолированной вершиной называется вершина, у которой и

Степень входа и степень выхода равна 0.

Источником называется вершина, степень выхода которой

Положительна, а степень входа равна 0.

Стоком называется вершина, степень входа которой положительна,

А степень выхода равна 0.

Пример:

Определение.

Путем в ориентированном графе называется последовательность ориентированных ребер.

Определение.

Простым путем в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза.

Определение.

Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром.

Определение.

Длиной пути называется число ребер в этом пути.

Замечание.

Петля обычно считается неориентированной.

Матрица смежности.

Для двух вершин Vi и Vj (i ≠j) существуют две принципиальные возможности: все ребра выходят из одной вершины и заходят в другую, или для каждой вершины существуют как входящие, так и исходящие ребра.

Например:

Кратность всех ребер равна 1, кратная петля (с кратностью 1) есть только при вершине V1, потому матрица смежности имеет вид

111

М = 001

Главным недостатком матрицы смежности ориентированного графа является, то, что не всегда возможно определить, ориентированный граф или нет. Несимметричность может являться достаточным условием ориентированности. Для задания матрицы смежности орграфа (если она получается симметричной) надо указать это отдельно, например Aор .

Определение.

Орграф называется сильно связным, если для любых двух вершин xi , xj найдется путь с началом в xi и концом в xj.

Пример:

 

Пути в орграфах.

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

Возникает задача поиска путей между парой вершин в ориентированном графе.

Путь G =(F, X)-ориентированный граф, а М – его матрица смежности. По определению, его дуга является путем длины 1. Булево произведение матрицы М с самой собой обозначается М². В этой матрице число 1 символизирует наличие пути длины 2. По матрице М³=М ·М ·М можно определить все пути длина 3; и вообще, матрица М хранит сведения о путях длины к.

Наконец, в матрице М*=М+М²+…+М записаны пути любой длины между вершинами.

Матрица М* называется матрицей достижимости.

Пример: Вычислить матрицу достижимости орграфа

Решение.

Напишем матрицу смежности орграфа

0100

М= 0011

2)Найдем М²:

0100 0100 0011

М² = 0011 · 0011 = 0010

0000 0000 0000

0011 0011 0000

Число 1 соответствует путям длины 2 в орграфе, а именно ABC, ABD, BDC.

2) Вычислим М³ и М4 :

М³=М2·М= 0010

0000 =>есть один путь длины 3 : ABCD

3)М4 = М³·М= 0000

0000

4)М*=М+М²+М³+М4

0111

М*= 0011 - матрица достижимости.

Пример:

Последнее изменение этой страницы: 2016-08-28

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...