Ви є тут

Часть 3. Способы задания графов

Во многих задачах, особенно, решаемых на ЭВМ, графы удобно описывать матрицами.

1.Задание графов матрицей смежности:

Матрица смежности – это квадратная матрица порядка p (количество вершин),  элемент которой,  стоящий в i строке и j столбце определяется по правилу:

ПРИМЕР

2. Задание графов матрицей инцидентций.

Матрицей  инцидентции называется прямоугольная матрица размерности  (–  количество вершин, q – количество ребер), элемент которой стоящий в iстроке и j столбце определяется по правилу:

                                             - для неориентированного графа.

- для ориентированного графа.

ПРИМЕР

 

 

Тема 4.6. Операции над графами

1. Объединением графов G1(V1E1) и G2(V2E2)  называется граф

G(VE) = ,

где  V = E = .

ПРИМЕР

 

Найти объединение графов G1(V1E1) и G2(V2E2).

                         

G1(V1E1)                                                          G2(V2E2)

РЕШЕНИЕ

2. Пересечением графов G1(V1E1) и G2(V2E2)  называется граф

G(VE) = , где V =   E = .

ПРИМЕР

Найти пересечение графов G1(V1E1) и G2(V2E2).

РЕШЕНИЕ

3.  Кольцевой суммой графов  G1(V1E1) и G2(V2E2)  называется граф

G(VE) = , где V = E = .

ПРИМЕР

Найти кольцевую сумму графов G1(V1E1) и G2(V2E2).

РЕШЕНИЕ

4.  Дополнением графа  G1(V1E1) называется граф

G(VE) = , где  ,  E = .

ПРИМЕР

Найти дополнение графа G1(V1E1).

РЕШЕНИЕ

Изоморфизм графов

Важным при рассмотрении графов является вопрос о том, какие графы можно и нужно считать различными, а какие – одинаковыми.

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

Изоморфизм графов означает, что можно так переобозначить вершины первого графа, что в новых обозначениях вершины и ребра будут совпадать со вторым графом.

ПРИМЕР

 Графы приведенные на рисунке изоморфны:

     

 

Тема 4.8. Связные графы

Еще один из выделяемых видов графов связан с возможностью попадания из одной его вершины в другую.

Две вершины называются связными, если существует маршрут между ними. Связность для вершин является бинарным отношением.

Неориентированный граф называется связным, если между любыми двумя вершинами есть маршрут.

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

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

Ребро (vu) связного графа G называется мостом, если после его удаления G станет несвязным и распадется на два связных графа G’ и G’’.

ПРИМЕР

Ребро (v3v4) связного графа является мостом, т. к. после его удаления G станет несвязным и распадется на два связных графа

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

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

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer