Презентация на тему Способы представления графов

если для решения задачи, связанной с графом, надо применить

компьютер, такой способ представления уже малопригоден. Поэтому используют другие способы представления графов.
Граф называется нагруженным, если каждому ребру сопоставлено некоторое число. В зависимости от рассматриваемой задачи это число может обозначать расстояние между вершинами, или время перехода от одной вершины к другой (если, например, графом изображена какая-либо транспортная схема), или пропускную способность канала, соединяющего две данные вершины (если в виде графа изображена какая-либо коммуникационная сеть), или еще что-либо. Иногда удобно рассматривать ненагруженный граф как нагруженный, у которого каждому ребру поставлено в соответствие число 1. Обсудим способы представления нагруженных графов.

всех его ребер или таблицей, где в клетке на

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

Приведем список ребер для нагруженного графа, изображенного на рисунке 6.7: (АА; 2), (АВ; 3), (АС; 6), (ВС; 2), (АD; 4), (ВВ; 3), (СВ; 5).

указывающих нагрузку (т. е. отличных от 0), стояло бы

число 1. А в списке ребер ненагруженного графа просто не нужна числовая характеристика.

образом обрабатывающего граф, вершины графа считаются перенумерованными натуральными числами

от 1 до n (без пропусков и повторений).
Список ребер для нагруженного графа задается как двумерный массив А[1:3;1:n], где:
в первой строке соответствующей этому массиву таблицы указывается один конец ребра,
во второй — другой его конец,
а в третьей — величина нагрузки (здесь n - число ребер в графе).
Для ненагруженного графа соответствующий массив содержит только первые две строки.