Дополнительные характеристики графов. Граф называется:

Граф называется:

- связным, если для любых вершин u,v есть путь из u в v.

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

- деревом, если он связный и не содержит простых циклов.

- полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.

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

- k-дольным, если его вершины можно разбить на k непересекающихся подмножества V1, V2, …, Vk так, что не будет рёбер, соединяющих вершины одного и того же подмножества.

- полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.

- планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.

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

Инцидентность — понятие, используемое только в отношении ребра и вершины: если v1,v2 — вершины, а e = (v1,v2) — соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.

Смежность — понятие, используемое в отношении только двух рёбер либо только двух вершин: Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Минимальное остовное дерево

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

Пример

Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.

Задача о нахождении минимального остовного дерева часто встречается в подобной постановке: допустим, есть n городов, которые необходимо соединить дорогами, так, чтобы можно было добраться из любого города в любой другой (напрямую или через другие города). Разрешается строить дороги между заданными парами городов и известна стоимость строительства каждой такой дороги. Требуется решить, какие именно дороги нужно строить, чтобы минимизировать общую стоимость строительства.

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

Дата добавления: 2015-10-13