Составители:
68
Построение структурных схем сложных систем осуществляется с
использованием графов, поэтому графы составляют основу аппарата
формализованного описания структур систем. Так как графы нашли
широкое применение в структурном моделировании, то рассмотрим
основные положения теории графов, необходимые при решении задач
структурного анализа и синтеза систем.
Определение 2.1.1. Граф G – пара множеств < X, U >, состоящая из
множества X и подмножества U прямого произведения множества X
самого на себя, т. е. G = < X, U >, где U ⊂ X × X.
Граф называется конечным, если множества X и U конечны, и бес-
конечным в противном случае.
Элементы х множества Х называются вершинами графа, а само
множество Х – множеством вершин графа.
Элементы < x, y > множества U, где x
∈
X, y
∈
X, называются
дугами, а само множество U – множеством дуг графа.
Говорят, что дуга < x, y > исходит из вершины x и заходит в вершину y.
Вершины x и y дуги < x, y > называются концевыми вершинами этой
дуги, при этом вершина x называется начальной, а вершина y – конеч-
ной вершиной этой же дуги.
Определение 2.1.2. Дуга и вершина графа называются инцидент-
ными, если вершина является концевой для данной дуги.
Это означает, что дуга < x, y > инцидентна вершинам x и y, а верши-
ны x и y инциденты дуге < x, y >.
Определение 2.1.3. Вершина графа, не инцидентная никакой дуге, на-
зывается изолированной.
Определение 2.1.4. Дуги графа, имеющие общую начальную и об-
щую конечную вершины, называются кратными дугами.
Определение 2.1.5. Дуга графа, у которой начальная и конечная вер-
шины совпадают, называется петлей.
Страницы
- « первая
- ‹ предыдущая
- …
- 66
- 67
- 68
- 69
- 70
- …
- следующая ›
- последняя »
