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

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

Доступно в Google Play

n1.doc

  1   2   3   4   5   6   7   8
1. Элементы теории графов

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

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

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

Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным (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(vi), i=1..|V|)=2|E|.

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

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



Граф, вершины которого можно разбить на непересекающиеся подмножества V1 и V2 так, что никакие две вершины, принадлежащие одному и тому же подмножеству, не смежны, называется двудольным (или бихроматическим, или графом Кенига) и обозначается Bmn (m=|V1|, n=|V2|, m+n=|V|). Полный двудольный граф - такой двудольный граф, что каждая вершина множества V1 связана со всеми вершинами множества V2, и наоборот; обозначение - Kmn. Замечание: полный двудольный граф Bmn не является полным (за исключением B11=K2).

B33

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

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

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

Графы G1=(V1,E1) и G2=(V2,E2) называются изоморфными (обозначение: G1~G2), если между графами существует взаимно-однозначное отображение : G1G2 (V1V2, E1E2), которое сохраняет соответствие между ребрами (дугами) графов, т.е. для любого ребра (дуги) e=(v,u) верно: e'=(v,u)=((v),(u)) (eE1, e'E2). Отображение  называется изоморфным отображением.

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


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

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

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

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

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

Пути и циклы

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

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

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

~

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

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

Деревья
  1   2   3   4   5   6   7   8


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации