Рис. 3.6. Дерево вариантов обеда

↑

⇐ ПредыдущаяСтр 4 из 6Следующая ⇒

Рис. 3.5. Граф схемы дорог

Строки и столбцы таблицы будут соответствовать вершинам графа. Если две вершины являются смежными (соединены ребром), то в ячейку на пересечении соответствующих столбца и строки будем записывать вес этого ребра. В противном случае (вершины не являются смежными) в ячейку будем записывать 0. Получится таблица типа «объект — объект».

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

Матрица смежности неориентированного графа симметрична относительно главной диагонали, идущей от левого верхнего угла к правому нижнему углу. У матрицы смежности неориентированного графа такая симметрия отсутствует.

Пример 2. Обед в школьной столовой состоит из двух блюд и напитка. На первое можно выбрать щи или окрошку, на второе — плов или пельмени, на третье — сок или компот. Все возможные варианты представлены с помощью дерева на рисунке 3.6.

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

Получилась таблица типа «объект-свойства»: объектами в ней являются варианты обеда, а свойствами — составляющие его блюда. При этом число граф в полученной таблице соответствует числу уровней в дереве.

При решении класса задач, связанного с нахождением кратчайшего пути в ориентированном графе, можно:

1) от исходного графа перейти к матрице смежности;
2) по матрице смежности построить дерево решений;
3) по дереву решений выбрать подходящий вариант.

Пример 3. Найдём кратчайший путь от вершины А до вершины F в графе, приведённом на рисунке 3.7.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры