Мегаобучалка Главная | О нас | Обратная связь


Представление систем с помощью графов



2016-01-26 582 Обсуждений (0)
Представление систем с помощью графов 0.00 из 5.00 0 оценок




Граф G на множестве вершин X и множестве друг U.

G(X,U)

Uij=(xi,xj),

Дуга Uj исходя из xi и заходит в xj. Такая дуга становится инцидентной вершинам xi и xj.

Если взять две вершины , и x<y, то вершина Х предшествует вершине Y, следовательно y следует за x.

Если записано x≤y следовательно x=y или из вершины x в y существует путь.

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

 

Некая вершина , которая следует за всеми вершинами подмножества Y множества X называется мажорантой (стоком). Может существовать несколько мажорант.

 

Вершина , которая предшествует всем вершинам подмножества Y множества X называется минорантой (истоком). Может существовать несколько минорант.

 

Для неориентированного графа вводится понятие: локальная степень вершины X – число ребер инцидентных вершине x.

Обозначается:

Если четно, то вершина тоже и наоборот.

Граф называется однородным степени n, если локальная степень всех вершин для любого .

 

Для ориентированного графа: множество дуг, исходящих из вершины xi записывается и называются локальной степенью вершины или полустепень исходящей вершины xi.

Ориентированный граф называется однородным, если все локальные степени имеют одно и тоже значение:

, для любого

Если , то вершина x является изолированной.

Если , а , то эта вершина является входом.

Если , – вершина является выходом.

Неориентированный граф является связанным, если любые xi, xj можно соединить цепью, следовательно для ориентированного графа вводятся понятия сильно связанного графа.

 

Граф сильно связан, если любые xi, xj существуют из xi в xj.

 

Способы представления графов

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

 

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

Свойства матрицы смежности для ориентированного графа:

1) каждый нулевой столбец соответствует источнику

2) каждая нулевая строка – строку

3) если все элементы главной диагонали равны 0, то в графе нет петель

4) появление единицы для любого xi,j . i=j соответствует петле

5) матрица не симметрична

2. Матрица инцидентности

В неориентированный

 

в ориентированный

Ребра должны быть пронумерованы!

 

3. Матрица изоморфности

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

Пример:

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

 

матрица инцидентности

 

матрица изоморфности

 



2016-01-26 582 Обсуждений (0)
Представление систем с помощью графов 0.00 из 5.00 0 оценок









Обсуждение в статье: Представление систем с помощью графов

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

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



©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (582)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.007 сек.)