Алгоритмы решения некоторых теоретико-графовых задач - файл n1.doc

приобрести
Алгоритмы решения некоторых теоретико-графовых задач
скачать (51 kb.)
Доступные файлы (1):

205kb.

14.03.2006 12:59

Алгоритмы решения задач по физике (Документ)
Клир Дж. Системология. Автоматизация решения системных задач (Документ)
Клир Дж. Системология. Автоматизация решения системных задач (Документ)
Гутман В.И, Мощанский В.Н. Алгоритмы решения задач по механике в средней школе (Документ)
Нечепуренко М.И., Попков В.К. и др. Алгоритмы и программы решения задач на графах и сетях (Документ)
Романовский И.В. Алгоритмы решения экстремальных задач (Документ)
Пильщиков В.Н. и др. Машина Тьюринга и алгоритмы Маркова. Решение задач (Документ)
Губарени Н.М. Вычислительные методы и алгоритмы малоракурсной компьютерной томографии (Документ)
Мостовской А.П. Численные методы и система wxMaxima (Документ)
Костин В.Е., Полякова З.И., Сторчак Н.А., Мишустин Н.А. Пересечение поверхностей. Развертки поверхностей. Аксонометрические проекции (Документ)
Тарасевич Ю.Ю. Перколяция: теория, приложения, алгоритмы (Документ)
Бокарев П.А. Коммерческая логистика. Сборник практических задач (Документ)

n1.doc

1 2 3 4 5 6 7 8

1. Элементы теории графов

Основные определения

Граф (graph) - пара G=(V,E), где V - множество объектов произвольной природы, называемых вершинами (vertices, nodes), а E - семейство пар e_i=(v_i1, v_i2), v_ijV, называемых ребрами (edges). В общем случае множество V и/или семейство E могут содержать бесконечное число элементов, но мы будем рассматривать только конечные графы, т.е. графы, у которых как V, так и E конечны.

В приведенном определении графа E не случайно названо семейством пар, а не множеством. Дело в том, что элементы E могут быть неуникальны, т.е. возможны кратные ребра. Существует другое, более корректное определение: граф определяется как тройка G=(V,E,), где V - множество вершин, E - множество ребер, а =(v,u,e) - трехместный предикат (булевская функция от трех переменных), возвращающая True тогда и только тогда, когда ребро e инцидентно вершинам v и u. Однако такие "строгости" в нашем изложении являются чрезмерными.

Если порядок элементов, входящих в e_i, имеет значение, то граф называется ориентированным (directed graph), сокращенно - орграф (digraph), иначе - неориентированным (undirected graph). Ребра орграфа называются дугами (arcs). В дальнейшем будем считать, что термин "граф", применяемый без уточнений "ориентированный" или "неориентированный", обозначает неориентированный граф.

Пример: G=(V,E); V={1,2,3,4}; E=<(1,1), (1,2), (1,3), (2,4), (2,4)>

G
Если e=(v,u), то вершины v и u называются концами ребра. При этом говорят, что ребро e является смежным (инцидентным) каждой из вершин v и u. Вершины v и u также называются смежными (инцидентными). В общем случае, допускаются ребра вида e=(v,v); такие ребра называются петлями.

Степень вершины графа - это число ребер, инцидентных данной вершине, причем петли учитываются дважды. Поскольку каждое ребро инцидентно двум вершинам, сумма степеней всех вершин графа равна удвоенному количеству ребер: Sum(deg(v_i), i=1..|V|)=2|E|.

Граф, не содержащий петель и кратных ребер, называется обыкновенным, или простым графом (simple graph). Во многих публикациях используется другая терминология: под графом понимается простой граф, граф с кратными ребрами называют мультиграфом, с петлями - псевдографом.

Некоторые классы графов получили особые наименования. Граф с любым количеством вершин, не содержащий ребер, называется пустым. Обыкновенный граф с n вершинами, любая пара вершин которого соединена ребром, называется полным и обозначается K_n (очевидно, что в полном графе n(n-1)/2 ребер).

Граф, вершины которого можно разбить на непересекающиеся подмножества V₁ и V₂ так, что никакие две вершины, принадлежащие одному и тому же подмножеству, не смежны, называется двудольным (или бихроматическим, или графом Кенига) и обозначается B_mn (m=|V₁|, n=|V₂|, m+n=|V|). Полный двудольный граф - такой двудольный граф, что каждая вершина множества V₁ связана со всеми вершинами множества V₂, и наоборот; обозначение - K_mn. Замечание: полный двудольный граф B_mn не является полным (за исключением B₁₁=K₂).

B₃₃

Подграфом, или частью графа G=(V,E) называется такой граф G'=(V',E'), что V'V и две несмежные вершины в G не смежны в G'. Полным подграфом называется подграф, любая пара вершин которого смежна.

Остовным подграфом (суграфом) графа G называется любой его подграф, содержащий то же множество вершин, что и G.

Изоморфизм, гомеоморфизм

Графы G₁=(V₁,E₁) и G₂=(V₂,E₂) называются изоморфными (обозначение: G₁~G₂), если между графами существует взаимно-однозначное отображение : G₁G₂ (V₁V₂, E₁E₂), которое сохраняет соответствие между ребрами (дугами) графов, т.е. для любого ребра (дуги) e=(v,u) верно: e'=(v,u)=((v),(u)) (eE₁, e'E₂). Отображение  называется изоморфным отображением.

Иными словами, изоморфные графы различаются только обозначением вершин.

Изоморфные графы. Одно из изоморфных отображений: (0,0), (1,3), (2,5), (3,6), (4,7), (5,2), (6,1), (7,4), (8,9), (9,8).

Характеристики графов, инвариантные относительно изоморфизмов графов (т.е. принимающие одинаковые значения на изоморфных графах), называются инвариантами графов.

Подразделением ребра (v₁,v₂) графа называется операция добавления в граф вершины v' и замены этого ребра на два смежных ребра (v₁,v') и (v',v₂): V'=V+{v'}, E'=E-{(v₁,v₂)}+{(v₁,v')}+{(v',v₂).

Граф G' называется подразделением графа G, если он может быть получен из G путем конечного числа подразделений ребер.

Два графа называются гомеоморфными, если для них существуют изоморфные подразделения.

Пути и циклы

Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг - в орграфе) вида v₀, (v₀,v₁), v₁, ... , (v_n-1,v_n), v_n. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин - простой цепью. Путь может быть замкнутым (v₀=v_n). Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе); без повторяющихся вершин (кроме первой и последней) - простым циклом.

Утверждение 1. Если в графе существует путь, ведущий из вершины v₀ в v_n, то существует и простая цепь между этими вершинами.

Доказательство: такую простую цепь можно построить, "выкинув" из пути все циклы.

~

Граф называется связным, если существует путь между любыми двумя его вершинами, и несвязным - в противном случае. Несвязный граф состоит из нескольких связных компонент (связных подграфов).

Для орграфов понятие связности является более сложным: различают сильную связность, одностороннюю связность и слабую связность. Орграф называется сильно связным, если для любых двух его вершин v и u существует как маршрут из v в u (v->u), так и из u в v (u->v). Орграф называется односторонне связным, если для любых двух его вершин u и v существует по крайней один из маршрутов v->u или u->v. Наконец, орграф называется слабо связным, если связен неориентированный граф, получаемый из этого орграфа путем снятия ориентации с дуг. Очевидно, что любой сильно связный граф является односторонне связным, а односторонне связный - слабо связным, но не наоборот.

Деревья

1 2 3 4 5 6 7 8