Дискретная математика
Способы представления графовИзображение графа рисунком удобно для восприятия человеком. Однако, если для решений задачи, связанной с графом, надо применить компьютер, такой способ представления уже малопригоден. Поэтому используют другие способы представления графов. Граф называется нагруженным, если каждому ребру сопоставлено некоторое число. В зависимости от рассматриваемой задачи это число может обозначать расстояние между вершинами, или время перехода от одной вершины к другой (если, например, графом изображена какая-либо транспортная схема), или пропускную способность канала, соединяющего две данные вершины (если в виде графа изображена какая-либо коммуникационная сеть), или еще что-либо. Иногда удобно рассматривать ненагруженный граф как нагруженный, у которого каждому ребру поставлено в соответствие число 1. Поэтому мы обсудим способы представления нагруженных графов. Обычно граф задают одним из двух способов: перечислением всех его ребер или таблицей, где в клетке на пересечении строки и столбца, соответствующих данным вершинам, указано, соединены эти вершины ребром или нет. Такая таблица называется таблицей смежности. Если граф нагруженный, то для каждого ребра в соответствующей клетке указывается нагрузка. Приведем список ребер для нагруженного графа, изображенного на рисунке 1.3: (АА;2), (АВ;3), (АС; 6), (ВС; 2), (АD; 4), (BD; 3), (CD; 5). Таблица 1.1 является таблицей смежности для этого графа.
В таблице смежности ненагруженного графа везде вместо чисел, указывающих нагрузку (т.е. отличных от 0), стояло бы число 1. А в списке ребер ненагруженного графа просто не нужна числовая характеристика. Надо уметь переходить от одного способа описания графа к другому. Но эта работа совершено формальна и, следовательно, может быть получена компьютеру, только нужно составить соответствующий алгоритм.
В дальнейшем в заданиях на составление алгоритма, тем или иным образом обрабатывающего граф, мы для простоты будем считать вершины графа перенумерованными натуральными числами от 1 до n (без пропусков и повторений). Список ребер для нагруженного графа будем задавать как двумерный массив A[1 : 3; 1 : n], где в первой строке соответствующей этому массиву таблицу указывается один конец ребра, во второй - другой его конец, а в третьей - величина нагрузки (здесь n - число ребер в графе). Для ненагруженного графа соответствующий массив содержит только первые две строки. Если граф задается таблицей смежности, то договоримся считать значение первого индекса номером первой вершины, а второго индекса - номером второй вершины; сами номера вершин в массиве не присутствуют. В частности, для графа на рисунке 1.3 при естественной нумерации вершин A - 1, B - 3, C - 3 и D - 4 список ребер в силу нашей договоренности задается массивом, который можно изобразить таблицей 1.2, а таблица смежности имеет вид таблицы 1.3.
рис. 1.2
рис. 1.3 Вопросы и задания!
1. Что такое таблица смежности?
2. На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
 3. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет). Определите длину кратчайшего маршрута из А в F.
 |
Календарь
Калькулятор
Поиск
Друзья сайта
|
