Графы, их элементы.

23 Графтар, олардың элементтері

При проектировании конструкций пользователю удобно иметь дело с моделями, представленными чертежами, графиками, где элементы конструкций изображены точками, а связи между ними – линиями. Такое представление весьма наглядно. Осуществить его можно с помощью аппарата теории графов.

Объект, состоящий из двух множеств (множества точек и множество линий), которые находятся между собой в некотором отношении, называют графом.

Множество точек графа называют множество вершин и обозначают

Множество линий, соединяющих пары вершин (x_i,x_j), называется множеством ребер, которые обозначаются

Обычно вершины обозначают цифрами (1, 2 …n), буквами с индексами (x_1…x_j…) или заглавными буквами (А, В, С…).

Линии обычно обозначают буквами с индексами (а₁, а₂…u_j…) или двумя цифрами или буквами, обозначающими вершины, которые соединены этой линией (u₁=(x₁, x₂), (x_i, x_j)=u₂...).

Можно выделить три вида графов.

1. Логический смысл вершин начала и конца дуг различен, линии – дуги помечены стрелками. Такие графы называются ориентированными (орграфы)(например, сеть радиовещания).

2. Направление связей не имеет принципиального значения, линии не имеют стрелок и называются ребрами. Граф называется неориентированным (например, ГТС).

3. Графы, имеющие как дуги, так и ребра, называются смешанными (напр., система телекоммуникации).

Особое место занимает нуль-граф – граф без дуг и ребер, состоящий только из вершин.

Дата добавления: 2015-07-17