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

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

G(X,U)

U_ij=(x_i,x_j),

Дуга U_j исходя из x_i и заходит в x_j. Такая дуга становится инцидентной вершинам x_i и x_j.

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

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

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

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

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

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

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

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

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

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

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

, для любого

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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