Теория графов

Граф – это средство для наглядного представления состава и структуры системы.

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

Граф, в котором все линии направленные, называется ориентированным графом(орграфом)

ОрграфВершиныДуги ЧайнвордСловаСовпадение последней и первой букв (возможность связать два слова в цепочку) СтройкаРаботыНеобходимое предшествование (например, стены нужно построить раньше, чем крышу, т. п.) ОбучениеКурсыНеобходимое предшествование (например, курс по языку Pascal полезно изучить прежде, чем курс по Delphi, и т.п.) Одевание ребенка Предметы гардероб а Необходимое предшествование (например, носки должны быть надеты раньше, чем ботинки, и т.п.) Европейский город ПерекресткиУзкие улицы с односторонним движением ОрганизацияСотрудникиИерархия (начальник - подчиненный) Примеры орграфов

Взвешенный граф – это граф с вершинами или линиями которого связана дополнительная информация. Ее называют весом.

Таблица Примеры взвешенных графов ГрафВершиныВес вершиныРебра (дуги)Вес ребра (дуги) ТаможниГосударс тва Площадь территорииНаличие наземной границыСтоимость получения визы ПереездыГородаСтоимость ночевки в гостинице ДорогиДлина дороги Супер- чайнв орд Слова-Совпадение конца и начала слов(возможность "сцепить" слова) Длина пересекающихся частей КартаГосударс тва Цвет на картеНаличие общей границы- СетьКомпьют еры -Сетевой кабельСтоимость кабеля Примеры взвешенных графов

Для наглядного представления графа используют схемы. Для математических расчетов граф представляют в форме матрицы смежности. Если вершины смежны, то элемент матрицы равен 1, если не смежны