Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
6.2. Представления графовНаиболее известный и популярный способ представления графов состоит в геометрическом изображении точек (вершин) и линий (ребер) на бумаге. При численном решении задач на вычислительных машинах граф должен быть представлен дискретным способом. Существует довольно много способов такого рода представления графов. Однако простота использования представления графа, как и эффективность алгоритма, в основе которого он лежит, в полной мере зависит от конкретного выбора этого представления. Одно из направлений теории графов связано с их матричным представлением. Существуют различные виды матриц, ассоциированные с графами. Эти алгебраические формы используются для решения многих задач теории графов. Ниже рассматриваются две такие матричные формы и несколько нестандартных представлений, которые наиболее широко используются в алгоритмах на графах. 6.2.1. Матрица смежности графа• Определение. Матрицей смежности ориентированного помеченного графа с
Матрица смежности однозначно определяет структуру графа. Примеры орграфа и его матрицы смежности приведены соответственно на рис. 6.10 и рис. 6.11. Отметим, что петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1, но это не принято, обычно же представляют каждый элемент матрицы одним двоичным разрядом.
Рис. 6.10. Ориентированный граф
Рис. 6.11. Матрица смежности ориентированного графа рис. 6.10 6.2.2. Матрица инцидентности графа• Определение. Матрицей инцидентности для неориентированного графа с
• Определение. Матрицей инцидентности для ориентированного графа с
Матрица инцидентности однозначно определяет структуру графа. На рис. 6.12 представлена такая матрица для орграфа на рис. 6.10.
Рис. 6.12. Матрица инцидентности ориентированного графа 6.2.3. Матрица весов графа• Определение. Граф называется взвешенным, если каждому его ребру сопоставлено число. Простой взвешенный граф может быть представлен своей матрицей весов 6.2.4. Список ребер графаПри описании графа списком его ребер каждое ребро представляется парой инцидентных ему вершин. Это представление можно реализовать двумя массивами
• Интересно, что данное представление позволяет легко описать петли и кратные ребра. 6.2.5. Структура смежности графаОриентированный или неориентированный граф может быть однозначно представлен структурой смежности своих вершин. Структура смежности состоит из списков
Структуры смежности могут быть удобно реализованы массивом из
|
1 |
Оглавление
|