Способы представления графов и орграфов на эвм: матрица смежности, матрица инцидентности, список смежности, массив ребер (дуг).
Существует несколько способов представления графов в памяти ЭВМ. Она различаются объемом занимаемой памяти, скоростью выполнения операций, выбор способа зависит от специфики рассматриваемой задачи.
Рассмотрим G(V,X), │V│=n,│X│=m. Матрицей смежности графа (орграфа) G называется A2n×n, элементы которой =1, если {Vi,Vj}∈X; =0, если {Vi,Vj}∈X.
Матрицей инцидентности графа G(V,X) называется матрица В n×m, элементы которой инцидентно ; не инцидентно .
Матрицей инцидентности орграфа G(V,X) называется матрица В n×m, элементы которой начало ; конец ; =0, если не инцидентно
Представление графа с помощью списочной структуры, отражающей смежности вершин и состоящей из массива указывающего на смежные вершины называется списком смежности.
Представление графа с помощью массива структур, отражающего список пар смежных вершин называется массивом ребер для графа или массивом дуг для орграфа.
-
Yandex.RTB R-A-252273-3
- Множества. Элементы множеств. Интуитивный принцип объемности. Способы задания множества. Мощность множества.
- Подмножества и их свойства.
- Операции над множествами: объединение, пересечение, разность, дополнение. Диаграммы Эйлера-Венна.
- Свойства операций над множествами (с доказательством).
- Прямое произведение множеств. Бинарные отношения. Способы задания бинарных отношений.
- Операции над бинарными отношениями: композиция отношений, степень отношения, обратное отношение, дополнение отношения, объединение, пересечение, разность отношений.
- Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, связность.
- Замыкания отношений. Транзитивное замыкание, рефлексивное транзитивное замыкание. Теоремы о транзитивном и рефлексивном транзитивном замыкании.
- Операции над бинарными отношениями, заданными в матричной форме.
- Алгоритм определения матрицы транзитивного замыкания бинарного отношения.
- Отношение эквивалентности. Классы эквивалентности и их свойства. Разбиения множеств. Связь эквивалентности с разбиением (теоремы с доказательством).
- Отношение порядка. Строгий и нестрогий порядок. Частичный и полный порядок. Упорядоченные множества.
- Соответствия. Образ и прообраз. Свойства соответствий: всюду определенные, инъективные, сюръективные, функциональные, взаимнооднозначные соответствия.
- Функции и отображения. Виды отображений. Обратные соответствия и функции. Способы задания функций.
- Алгебраические операции. Примеры операций. Арность операции. Способы задания.
- Свойства бинарных алгебраических операций: коммутативность, ассоциативность, дистрибутивность, поглощение, идемпотентность. Нейтральный и симметричный элементы.
- Комбинаторные правила суммы и произведения. Выборки (упорядоченные, неупорядоченные, с повторениями и без).
- Операции над графами.
- Способы представления графов и орграфов на эвм: матрица смежности, матрица инцидентности, список смежности, массив ребер (дуг).
- Маршруты в графах. Виды маршрутов: замкнутые и незамкнутые. Цепь. Простая цепь. Цикл. Простой цикл. Длина маршрута. Расстояние между вершинами. Диаметр графа.
- Орграфы и бинарные отношения. Отношение достижимости вершин орграфа. Матрица достижимости. Связь между отношениями достижимости и смежности.
- Определение матрицы достижимости орграфа как матрицы рефлексивного и транзитивного замыкания отношения смежности.
- Алгоритм выделения компонент связности (сильной связности)
- Нагруженные орграфы Длина пути в нагруженном орграфе. Минимальные пути в нагруженных орграфах.
- Нагруженные орграфы. Алгоритм Форда-Беллмана выделения минимального пути в нагруженном орграфе.