Теория графов и их применение
Вид материала | Курсовая |
СодержаниеВзвешенные графы |
- 1. Элементы теории графов Введение в теорию графов: основные понятия и определения., 32.17kb.
- «Теория графов», 114.81kb.
- Задача является np-полной для кубических планарных графов, реберных графов, ориентированных, 39.45kb.
- «Применение информационный технологий в теории графов», 272.84kb.
- Билеты по Дискретной математике «Теория Графов», 12.79kb.
- Программа вступительного экзамена в аспирантуру по специальностям 05. 13. 05 - "Элементы, 88.59kb.
- Спецкурс «Теория графов» пм 4 курс История возникновения и развития теории графов., 13.97kb.
- Задание графов соответствием 9 > Матричное представление графов 10 Вопросы применения, 230.14kb.
- Знать содержание программы курса; иметь навыки структурного моделирования типовых объектов;, 56.2kb.
- Теория конечных графов и её приложения прак зан, 29.91kb.
Взвешенные графы
Часто, особенно когда графы используются для моделирования реальных систем, их вершинам, или ребрам, или и тем, и другим приписываются некоторые числа. Природа этих чисел может быть самая разнообразная. Например, если граф представляет собой модель железнодорожной сети, то число, приписанное ребру, может указывать длину перегона между двумя станциями, или наибольший вес состава, который допустим для этого участка пути, или среднее число поездов, проходящих через этот участок в течение суток и т.п. Что бы ни означали эти числа, сложилась традиция называть их весами, а граф с заданными весами вершин и

Изоморфизм
На рис. 1.8 изображены два графа с одним и тем же множеством вершин



Рис. 1.8.
Определение. Графы










Тот факт, что графы



Для графов, изображенных на рис. 1.8, изоморфизмом является, например, отображение, задаваемое следующей таблицей:
![]() ![]() | ![]() | ![]() | ![]() | ![]() |
![]() ![]() | ![]() | ![]() | ![]() | ![]() |
Заметим, что в этом примере есть и другие изоморфизмы первого графа на второй.
Сформулированное определение изоморфизма годится и для ориентированных графов, нужно только обе упоминаемые в нем пары вершин считать упорядоченными.
Изоморфизм - бинарное отношение на множестве графов. Очевидно, что это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются абстрактными графами. Когда говорят, что рассматриваются абстрактные графы, это означает, что изоморфные графы считаются одинаковыми. Абстрактный граф можно представлять себе как граф, у которого стерты имена (пометки) вершин, поэтому абстрактные графы иногда называют также непомеченными графами.