Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

АЛГОРИТМЫ НА ГРАФАХ

ЗАДАНИЕ 4 Графы: представления и операции

Теория графов, обладая стройной системой понятий и обозначений, является продуктивным средством моделирования систем и процессов информационного характера. Из всех разделов дискретной математики именно графы и особенно алгоритмы на графах широко применяются в программировании. В задании вводится язык теории графов [16], излагаются способы машинного представления графов. Цель задания: практика программирования операций над графами и преобразования одного способа представления графа в другой.

Основные понятия и обозначения

Пусть V - непустое конечное множество, Е2) - множество всех его двухэлементных подмножеств. Пара G = (V, Е), где Е - произвольное подмножество множества Г2 называется графом (или неориентированным графом). Граф G - (V, Е) конструируется из элементов конечного множества V, поэтому он является комбинаторным объектом.

Элементы множества V принято называть вершинами, а элементы множества Е - ребрами графа G = (V, Е). В свою очередь, вершины и ребра - элементы этого графа. Число | V вершин графа называется его порядком. Если V-n и | Е |= т, то граф G = (V,E) называется (п, т)-графом.

Две вершины графа и иг смежны, когда е = {и, v} е Е, и не смежны в противном случае. Если е = {и, v} - ребро графа, то вершины и иг называются его концами. Два ребра смежны, если они имеют общий конец.

Вершину v и ребро е называют инцидентными, если v является концом ребра е, и неинцидентными в противном случае. Таким образом, смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.

Множество всех вершин графа, смежных с некоторой вершиной v, называется окрестностью вершины v и обозначается N(v). Степенью вершины v графа называется число инцидентных ей ребер, т е. число вершин, образующих ее окрестность. Степень вершины обозначается d(y) (или deg v). Тем самым d(v) = |7V(v) |. Вершина степени О считается изолированной, степени 1 - висячей.

Список степеней вершин графа называется его степенной последовательностью. Пусть d, ..., d„- степени вершины графа порядка п, выписанные в порядке неубывания:

Упорядоченный набор (d, ..., d„) называется вектором степеней графа G и обозначается d(G).

Маршрутом (или (vj, vk + )-маршрутом) в графе называется чередующаяся последовательность вершин и ребер

в которой любые два соседних элемента инцидентны. Если Vi = v*+b то маршрут замкнут (или цикличен). Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. Замкнутая цепь называется циклом, замкнутая простая цепь - простым циклом. Граф без циклов является ациклическим (или лесом). Длина маршрута (цикла) определяется числом составляющих его ребер.

Две вершины в графе считаются связными, если существует соединяющая их простая цепь. Граф, в котором любые две вершины связные, называется связным.

Граф G’- (V, Е') называется подграфом графа G-(V,E), если Г' с Г и Е' с ?. Всякий максимальный (по числу вершин и ребер) связный подграф графа G называется его компонентой связности. Число компонент связности графа G обозначается через k(G). Если k(G) = 1, то G - связный граф. Если k(G) > 1, то G - несвязный граф.

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

Граф, состоящий из одной вершины, называется тривиальным. Граф является безреберным, если в нем нет ребер, т. е. Е = 0. Безре- берный граф порядка п обозначается Оп. Граф называется полным, если любые две его вершины смежны, т. е. Е = И2). Полный граф порядка п обозначается К„. Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным долям.

Граф считается взвешенным, если каждому его ребру е & Е приписано вещественное число w(e) - вес ребра.

Граф порядка п является помеченным, если его вершинам присвоены некоторые метки, например, номера от 1 до п. Подобным образом можно пометить ребра графа.

Пример 4.1. Граф G, изображенный на рис. 4.1, является связным двудольным графом, поскольку он состоит из одной компоненты связности и множество его вершин V— {1, 2, 3, 4} разбивается на две доли V = {1, 3}, V2= {2, 4} так, что Vx и V2 = V, V о У2 = 0 и концы каждого ребра принадлежат разным долям. Кроме того, для вершин данного графа имеем:

Исходя из этого графу G соответствует вектор степеней

В графе G нет циклов, а вершины с номерами 3 и 4 соединены простой цепью: 3, ех, 2, е2, 1, е3, 4.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>