Способы задать граф. Матрица векторов смежности

• Видео посвящено способам задания графов.  

• Основные способы: список вершин, графический способ и матричный способ.  

• Матричный способ позволяет структурировать данные и упростить работу с большими графами.  

• Граф можно задать списком вершин и ребер.  

• Пример: граф с вершинами 1, 2, 3 и ребрами 12 и 31.  

• Ориентированные графы можно задать аналогично.  

• Граф можно нарисовать и задать его структуру.  

• Этот способ понятен и прост для восприятия.  

• Матричный способ позволяет структурировать данные.  

• Матрица смежности и матрица инцидентности.  

• Матрица смежности задает граф через элементы 1 и 0.  

• Пример построения матрицы смежности для графа с 5 вершинами.  

• Матрица инцидентности задает граф через элементы 1 и 0.  

• Пример построения матрицы инцидентности для графа с 5 вершинами и 7 ребрами.  

• Матрица инцидентности полезна для решения задач теории графов.  

• Матрица смежности более удобна для работы с большими графами.  

• Матрица смежности и инцидентности используется для представления графа.  

• Каждая строка матрицы соответствует вектору смежности, компоненты которого являются смежными вершинами.  

• Порядок элементов в векторе соответствует порядку ребер в графе.  

• Пример построения матрицы смежности для графа с 5 вершинами.  

• Вершины смежны с ребрами, которые записываются в матрицу.  

• Матрица ограничена максимальной степенью вершины, поэтому не все ребра записываются.  

• Матрица дополняется нулями для прямоугольности.  

• Матрица полезна при решении задач с небольшим числом просмотров каждого ребра.  

• На практике используется редко, но полезна для понимания.  

• Решение было понятным, но если остались вопросы, можно заказать помощь ВКонтакте.