Представление информации в форме графа

Граф— совокупность точек, соединённых между собой линиями. Эти точки называют вершинами графа.

Линии, соединяющие вершины, называются дугами, если задано направление от одной вершины к другой, или рёбрами, если направленность двусторонняя.

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

Граф однозначно задан, если заданы множество его вершин, множество рёбер (дуг) и указано, какие вершины какими рёбрами соединены.

Пример

На рис. 3 представлены различные типы конфигураций локальных вычислительных сетей (ЛВС), являющиеся информационными моделями структур ЛВС, представленными в виде графов:

• шинная конфигурация, когда к незамкнутому каналу с некоторыми интервалами подключаются отдельные абоненты (К), причем информация от абонента-источника распространяется по каналу в обе стороны;

• кольцевая конфигурация, когда каждый абонент непосредственно связан с двумя соседними абонентами, а информация передаётся по замкнутому кольцу, чаще всего в одну сторону;

• звездообразная конфигурация, в центре которой находится центральный коммутатор (ЦК), который последовательно опрашивает абонентов и предоставляет им право на обмен данными;

• древовидная конфигурация образуется подсоединением нескольких простых каналов связи к одному магистральному;

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

Рис.3 Различные типы конфигураций локальных вычислительных сетей

Формализация при построении графавключает в себя следующие этапы:

• выявление всех элементов объекта;

• определение характеристик элементов (названий, номеров, весов и т. п.);

• установление наличия и вида связей (односторонняя или двухсторонняя) между элементами;

• определение характеристик связей — весов рёбер и дуг;

• выбор формы изображения вершин и рёбер, ввод условных обозначений в случае необходимости;

• представление выделенных элементов и связей в графическом виде.

Для компьютерного моделирования более удобным является символическое и/или табличное задание графа.

Символическое задание графа— перечисление всех его рёбер с указанием вершин, которые они соединяют, либо перечисление всех вершин с указанием исходящих из них рёбер.

Пример

Графы, представленные на рис.7 могут быть описаны, например, следующими способами. Символическая запись: а(1,2) b(l,4) c(2,4) d(3,5) e(4,5) f(3,4)

Табличная запись:

Рис.7. Графы, имеющие одинаковые описания в виде таблицы и символической записи