Граф — совокупность точек, соединённых между собой линиями. Эти точки называют вершинами графа.
Линии, соединяющие вершины, называются дугами, если задано направление от одной вершины к другой, или рёбрами, если направленность двусторонняя.
Граф называется взвешенным, если вершины или рёбра (дуги) характеризуются некоторой дополнительной информацией — весом вершины или ребра (дуги).
Граф однозначно задан, если заданы множество его вершин, множество рёбер (дуг) и указано, какие вершины какими рёбрами соединены.
Пример
На рис. 3 представлены различные типы конфигураций локальных вычислительных сетей (ЛВС), являющиеся информационными моделями структур ЛВС, представленными в виде графов:
• шинная конфигурация, когда к незамкнутому каналу с некоторыми интервалами подключаются отдельные абоненты (К), причем информация от абонента-источника распространяется по каналу в обе стороны;
• кольцевая конфигурация, когда каждый абонент непосредственно связан с двумя соседними абонентами, а информация передаётся по замкнутому кольцу, чаще всего в одну сторону;
|
|
• звездообразная конфигурация, в центре которой находится центральный коммутатор (ЦК), который последовательно опрашивает абонентов и предоставляет им право на обмен данными;
• древовидная конфигурация образуется подсоединением нескольких простых каналов связи к одному магистральному;
• полносвязная конфигурация обеспечивает выбор наиболее быстрого маршрута связи между абонентами и удобна там, где управление оказывается достаточно сложным.
Рис.3 Различные типы конфигураций локальных вычислительных сетей
Формализация при построении графа включает в себя следующие этапы:
• выявление всех элементов объекта;
• определение характеристик элементов (названий, номеров, весов и т. п.);
• установление наличия и вида связей (односторонняя или двухсторонняя) между элементами;
• определение характеристик связей — весов рёбер и дуг;
• выбор формы изображения вершин и рёбер, ввод условных обозначений в случае необходимости;
• представление выделенных элементов и связей в графическом виде.
Для компьютерного моделирования более удобным является символическое и/или табличное задание графа.
Символическое задание графа — перечисление всех его рёбер с указанием вершин, которые они соединяют, либо перечисление всех вершин с указанием исходящих из них рёбер.
Пример
Графы, представленные на рис.7 могут быть описаны, например, следующими способами. Символическая запись: а(1,2) b(l,4) c(2,4) d(3,5) e(4,5) f(3,4)
Табличная запись:
а | b | ||||
а | с | ||||
f | d | ||||
b | с | f | e | ||
d | e |
|
|
Рис.7. Графы, имеющие одинаковые описания в виде таблицы и символической записи