Студопедия

КАТЕГОРИИ:

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



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

Читайте также:
  1. A. Элементы резания при точении
  2. AGb III. Проблемы общей теории перевода 105
  3. AGb III. Проблемы общей теории перевода 149
  4. AGb III. Проблемы общей теории перевода 203
  5. Cовременные теории мотивации
  6. II. Материальные элементы (МЭ)
  7. III.4.3) Виды и элементы вины.
  8. А) Основные элементы измерительных приборов
  9. Абстрактные, корневые, листовые и полиморфные элементы
  10. Аксиоматический способ построения теории

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

Граф Г – геометрическая фигура, построенная на множестве вершин V = {v1, v2, … vm} и ребер R = {r1, r2, … rn}:

Г = (V, R). (1)

Если ребра ориентированы, то их называют дугами, а граф - ориентированным (орграфом). При этом вершины называются узлами.

 

 
 

 


а) б)

Рис. 1

 

Примеры использования графов для моделирования:

1. Неориентированные графы описывают (моделируют) дороги между населенными пунктами А, B, C и D (см. рис. 1, а).

2. Орграф описывает однонаправленные каналы передачи информации (см. рис. 1, б).

Дуга ri, связанная с злом vj, называется инцидентной этому узлу, причем, если заходит – положительно инцидентная, если выходит – отрицательно инцидентная.

Два узла vk и vi смежны, если им инцидентна одна дуга. Аналогично, две дуги смежны, если они инцидентны одному узлу, причем, если одна выходит, а другая заходит – последовательно смежны, в противном случае - параллельно смежны.

Дуга, выходящая из узла и в нее же заходящая, называется петлей.

Узел, из которого дуги только выходят, называется истоком, а в который только заходят – стоком. Узлы сток и исток – висячие узлы.

Связи в системе можно изображать двояко:

1) элементы – это вершины, а связи – дуги (вершинный граф),

2) элементы – дуги, а связи – узлы (реберный или сигнальный граф).

Структуры графов можно представить как графически, так и структурными матрицами. Известны 2 вида структурных матриц: матрицы смежности, инцидентности (инциденций).

Матрица смежности – квадратная матрица А = {aij}, , где m – число узлов, т.е. Аmxm, для которой

 

Число единиц в матрице А равно числу дуг n.

Эта матрица обладает интересным свойством: если возвести матрицу А в k-ю степень, то каждый элемент матрицы Аk будет равен числу путей из узла vi в узел vj длиной в k дуг.

Путь в графе – это последовательность последовательно смежных дуг, ориентированных в одном направлении.

Контур – замкнутый путь.

 


Дата добавления: 2015-02-09; просмотров: 17; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Пути совершенствования систем с управлением. | Пример 1. Как видно (см. рис. 2), через две (k = 2) смежные дуги можно попасть: из вершины 1 в вершину 4, из 2
lektsii.com - Лекции.Ком - 2014-2017 год. (0.011 сек.) Главная страница Случайная страница Контакты