Графы – основные понятия.
Граф G(V,E) – совокупность двух множеств: непустого множества V (вершины) и множества Е (ребра) – множество неупорядоченных пар различных элементов множества V. Вершины и рёбра графа называются также элементами графа, число вершин в графе p= |V| — порядком, число рёбер q = |E| — размером графа.
Если v1, v2 — вершины, а e=(v1,v2) — соединяющее их ребро, тогда вершина v1 и ребро e инцидентны (принадлежат одному множеству), вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Вершины u и v называются концевыми вершинами ребра e = {u,v}. Две концевые вершины одного и того же ребра называются соседними. Два ребра называются смежными, если они имеют общую концевую вершину. Два ребра называются кратными, если множества их концевых вершин совпадают. Ребро называется петлёй (псевдографом), если его концы совпадают, то есть e = {v,v}.
Если Е – не множества, а НАБОР, содержащий несколько одинаковых элементов, то такие элементы называются кратными ребрами (граф – мультиграф). Если элементами множества Е являются упорядоченные пары, то граф – ориентирован. Тогда вершины – это узлы, а ребра – дуги. Если задана функция F: V -> M, F: E->M, то множество М – помечено, граф – помеченный.
Маршрут в граф – чередующаяся последовательность вершин и ребер, где любые два соседние элемента инцидентны. V0, e1, v1, e2, … , vk. Если V0=Vk, то маршрут замкнут. Длина маршрута – количество ребер в нем (с повторениями). Расстояние между u и v – длина кратчайшей цепи {u,v}.
Формы представления графов. Матрица смежности.
V1
V2 0 1 0 1
G
= 1
0 1 0
0 0 0 1
V4 V3 1 1 1 0
Формы представления графов. Матрица инцидентности.
В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".
Формы представления графов. Списки смежности.
Представление графа с помощью матрицы смежностей зачастую неудобно, поскольку количество вершин требуется знать заранее. Если граф должен создаваться или изменяться во время исполнения программы, то для каждого добавления или удаления вершины необходимо строить новую матрицу. Кроме того, даже если граф содержит малое число ребер (дуг) и матрица смежностей состоит в основном из нулей, память должна быть отведена для всех возможных дуг вне зависимости от того, существуют ли они.
Список смежности содержит для каждой вершины графа V список смежных ей вершин. Каждый элемент такого списка является записью R, содержащей в поле R.Stroka вершину графа, а в поле R.Next - указатель на следующую запись в списке (ясно, что для последней записи в списке R.Next содержит Nil). Обозначим Beg[v] - указатель на начало списка, содержащего вершины, смежные с вершиной v.
|
|
Очевидно, что количество ячеек памяти, необходимое для представления графа с помощью списков смежности, будет иметь порядок |V|+|E|.
Ф
ормы
представления графов. Массив дуг.
Чаще всего это двумерный массив размером 2*E, в первой строке которого хранится информация, из какой вершины начинается дуга, во второй - в какой кончается.
1 |
2 |
3 |
4 |
5 |
5 |
2 |
3 |
4 |
2 |
1 |
2 |
Достижимость и обходы графа.
Вершина w достижима из вершины v, если v = w или в G есть путь из v в w. Для неориентированных графов это отношение симметрично. Вершины v и w ориентированного графа G=(V,E) называются взаимно достижимыми, если в G есть путь из v в w и путь из w в v.
Под обходом графа мы будем понимать процесс систематического просмотра всех вершин графа с целью отыскания вершин, удовлетворяющих некоторому условию.
Алгоритм Дейкстры
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как не посещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Вычисление выражений по их символьному представлению.
Построение обратной польской записи выражения.
Отличительной особенностью обратной польской нотации является то, что все аргументы (или операнды) расположены перед знаком операции. В общем виде запись выглядит следующим образом:
Например, для выражения 7 2 3 * - эквивалентное 7-2*3.
Особенности обратной польской записи следующие:
Порядок выполнения операций однозначно задаётся порядком следования знаков операций в выражении, поэтому отпадает необходимость использования скобок и введения приоритетов и ассоциативности операций.
В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций. Так, выражение 5 * (-3 + 8)использует знак «минус» как символ унарной операции (изменение знака числа). Чтобы записать это выражение, придётся либо переформулировать его, либо ввести для операции изменения знака отдельное обозначение, например, «±»: 5 3 ± 8 + *.
Одно и то же вычисление может быть записано в нескольких разных вариантах. 10 15 - 3 * или 3 10 15 - *
Из-за отсутствия скобок обратная польская запись короче инфиксной. За этот счёт при вычислениях на калькуляторах повышается скорость работы оператора, а в программируемых устройствах сокращается объём тех частей программы, которые описывают вычисления. Последнее может быть немаловажно для портативных и встроенных вычислительных устройств, имеющих жёсткие ограничения на объём памяти.
Автоматизация вычисления выражений в обратной польской нотации основана на использовании стека. Алгоритм вычисления для стековой машины элементарен:
Обработка входного символа
Если на вход подан операнд, он помещается на вершину стека.
Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
Если входной набор символов обработан не полностью, перейти к шагу 1.
После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.
Приоритеты операций.