Математические модели в управлении. Заболотский В.П - 69 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

69
Определение 2.1.6. Две вершины графа называются смежными, если
существует хотя бы одна дуга, инцидентная им обеим.
В графе две вершины смежные, если для какой-либо из дуг графа
они являются концевыми.
Определение 2.1.7. Две дуги графа называются смежными, если
существует хотя бы одна вершина, инцидентная им обеим.
В графе дуги будут смежными, если существует общая концевая вер-
шина для этих дуг.
Граф может быть задан следующими тремя способами: аналити-
ческим, геометрическим и матричным.
Аналитический способ задания графов
Говорят, что граф G = < X, U > задан аналитически, если задано
множество X и соответствие Г = < X, X , U >, для которого множество U
является графиком, т. е. U ⊂ X × X.
Соответствие, определяющее граф, может быть задано различным
образом, что обусловливает разные формы аналитического задания гра-
фа. Так, например, соответствие Г может задаваться множеством Г(x)
образов для каждого элемента x множества X. Тогда граф будет задан в
виде, приведенном в примере 2.1.1.
Пример 2.1.1
X = {x
1
, x
2
, x
3
, x
4
, x
5
}.
Г(x
1
) = {x
1
, x
3
, x
5
}, Г(x
2
) =∅, Г(x
3
) = {x
1
, x
2
, x
5
}, Г(x
4
) = {x
1
},
Г(x
5
) = {x
1
, x
2
, x
3
, x
4
, x
5
}.
Граф может быть задан также путем перечисления всех элементов
множества X и множества U так, как приведено в примере 2.1.2.
Пример 2.1.2
X = {x
1
, x
2
, x
3
, x
4
, x
5
}.
U = {< x
1
, x
1
>, < x
1
, x
3
>, < x
1
, x
5
>, < x
3
, x
1
>, < x
3
, x
2
>, < x
3
, x
5
>,
< x
4
, x
1
>, < x
5
, x
1
>, < x
5
, x
2
>, < x
5
, x
3
>, < x
5
, x
4
>, < x
5
, x
5
>}.
В примерах 2.1.1 и 2.1.2 задан один и тот же граф.

Страницы