Графы. Решение практических задач с использованием графов (С++)
| Категория реферата: Рефераты по математике
| Теги реферата: реферат влияние на человека реферат древняя культура, диплом рф
| Добавил(а) на сайт: Мосенцев.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Представление графа с помощью квадратной булевой матрицы M, отражающей смежность вершин, называется матрицей смежности, где
Для матрицы смежности n(p,q) = O(p2).
Замечание
Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.
Матрица инциденций
Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа
а для орграфа
Для матрицы инциденций n(p,q) = O(pq).
Списки смежности
Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей на списки смежных вершин, где элемент списка представлен структурой
N : record v : 1..p; n :↑ N end record,
называется списком смежности. В случае представления неориентированных графов списками смежности n(p,q) = O(p+2q), а в случае ориентированных графов n(p,q) = O(p+q).
Массив дуг
Представление графа с помощью массива структур
E : array [1..q] of record b,e : 1..p end record,
отражающего список пар смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = O(2q).
Обзор задач теории графов
Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.
Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.
Далее перечислим некоторые типовые задачи теории графов и их приложения:
- Задача о кратчайшей цепи
замена оборудования
Рекомендуем скачать другие рефераты по теме: реферат памятники, бесплатные рефераты без регистрации.
Категории:
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Главная