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

Содержание

• 
  Слайд 1

  Способы представления графов

• 
  Слайд 2
  

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

• 
  Слайд 3
  

  Обычно граф задают одним из двух способов: перечислением всех его ребер или таблицей, где в клетке на пересечении строки и столбца, соответствующих данным вершинам, указано, соединены эти вершины ребром или нет. Такая таблица называется таблицей смежности. Если граф нагруженный, то для каждого ребра в соответствующей клетке указывается нагрузка. Приведем список ребер для нагруженного графа, изображенного на рисунке 6.7: (АА; 2), (АВ; 3), (АС; 6), (ВС; 2), (АD; 4), (ВВ; 3), (СВ; 5).

• 
  Слайд 4
  

  В таблице смежности ненагруженного графа везде вместо чисел, указывающих нагрузку (т. е. отличных от 0), стояло бы число 1. А в списке ребер ненагруженного графа просто не нужна числовая характеристика.

• 
  Слайд 5
  

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

• 
  Слайд 6
  

  Если граф задается таблицей смежности, то значение первого индекса cчитаетсяномером первой вершины, а второго индекса — номером второй вершины; сами номера вершин в массиве не присутствуют. В частности, для графа на рисунке 6.7 при естественной нумерации вершин А— 1, В— 2, С— 3 и D— 4 список ребер в силу нашей договоренности задается массивом, который можно изобразить таблицей 6.2, а таблица смежности имеет вид таблицы 6.3.