Дерево выражений. Примеры использования синтаксических структур
Топологическая сортировка
Топологическая сортировка – это получение такой последовательности вершин, что если существует дуга из вершины v в вершину w, то в результате топологической сортировки вершина v должна предшествовать вершине w (Неприменима на циклических графах).
1 шаг.
На каждом шаге в лексикографическом порядке выбираем вершину, у которой нет входящих дуг. Такая вершина обязана быть, так как граф ациклический.
2 шаг.
Найденную вершину помещаем в результирующую очередь, удаляем из графа (например, при помощи массива mark, помечая вершину как посещённую (удалённую). Значение этого массива будем учитывать на первом шаге при выборе вершины), а также удаляем все исходящие дуги (обнуляем строку, соответствующую вершине в матрице смежности, тогда критерием отсутствия входящих дуг есть столбец, в котором все нули).
3 шаг.
Шаги 1 и 2 повторяются до тех пор, пока не обойдём весь граф (массив mark = 0).
Замечание: последовательность вершин не единственна.
Алгоритм сильной связности
Сильно связной компонентой орграфа называют множество вершин взаимно достижимых друг друга – это имеет место при наличии цикла между вершинами. Часто сильно связная компонента определяют через класс эквивалентности.
Пусть G=(V;E) – орграф. Множество вершин V разбивается на классы эквивалентности V_1, V_2, …, V_r, причём v и w, будут эквивалентны, т.е. принадлежать к одному классу эквивалентности V_i тогда и только тогда, когда v достижимо из w, а w из v.
Шаг 1
Обход исходного графа в глубину. Для каждого узла запоминается глубинное число, равное порядковому номеру завершения обхода всех смежных с узлом узлов.
Шаг 2
Построение обратного графа G’=(V, E’);
(w,v)∈E, то (w,v)∈E’; (w,v)∈V
Шаг 3
Граф G’ обходится в глубину каждый раз начиная с вершины, имеющей наибольшее глубинное число соответствующих вершин, вычисленных на первом шаге.
Шаг 4.
В полученном глубинном остовном лесу для графа G’ каждое отдельное дерево представляет собой сильно связную компоненту.
Замечание
Узлы отдельного дерева, т.е. отдельный ССК можно обозначить отдельным узлом и кратные дуги графа G между полученными узлами образуют дуги индуцированного графа.
Вершинамии которог о являются ССК, в противном случае была бы одна ССК.
Неориентированные графы.
Реализация неорграфов.
Матрица смежности симметрична относительно главной диагонали, а матрица инцидентности имеет всего лишь 2 значения – 0 и 1.
Цикл имеет место быть тогда, когда его длина больше 3-х.
Пусть дан граф G=(V,E) граф G’ называется подграфом графа G, если
V’⊆ V;
(v,w)∈ E (v,w)∈E ⋀ {v,w}∈ V’
Если множество E’ состоит из всех рёбер (v,w) множества E, таких, что обе вершины (v,w) принадлежат V’, то граф G’ называется индуцированным подграфом графа G.
Связные компоненты графа G называются максимальной связный индуцированный подграф графа G.
Д и Е – связные компоненты графа G, так как содержат все дуги исходного графа инцидентные узлам вошедших в подграф.
Ациклический граф, представляющий собой дерево без корня, является свободным деревом (на рис А и Б)
Свойства свободных деревьев
В свободном дереве из n вершин ровно n-1 дуга
Если в свободное дерево добавить хотя бы одно ребро, то гарантированно образуется цикл.