Теорема Менгера: граф G является k-связанным тогда и только тогда, когда любые два различные узла x и y графа G соединены по крайне мере k путями, не содержащими общих узлов. k-связанные графы представляют особый интерес для сетевых приложений. Определенную проблему составляет автоматическое отображение графа на экране или бумаге. Кроме того, для многих приложений (например, CAD) все узлы графа должны совпадать с узлами технологической сетки. Возникают и другие ограничения, например необходимость размещения всех узлов на прямой линии. В этом случае ребра графа могут представлять собой кривые линии, дуги или ломаные линии, состоящие из отрезков прямых.

2.2 Способы численного представления графа

1. Матричный способ (с помощью матрицы смежности). Матрица смежности имеет m - строк и n - столбцов, где m - количество вершин графа.

Элементами матрицы смежности являются 0 и 1, Если вершины соединены, то ставится 1 и наоборот.

Матрица смежности графа GРис.

2.2.1 Граф и его матрица смежности

Матрица смежности симметрична относительно главной диагонали (рис. 2.2.1).

2. Матрица инцидентности вершин и рёбер содержит m - строк и n - столбцов, где m - количество вершин, n - количество рёбер.

Рис.1

Рис 2.2.2 Граф и его матрица инцидентности

В любом столбце матрицы инцидентности (рис. 2.2.2) лиши две единички.

Другой способ представления графа обеспечивает функция, которая выдает списки узлов, с которыми данный узел связан непосредственно. Для графа, отображенного на рис. 2.2.3, такое описание можно представить в виде структуры (таблица 2.1). В колонке s представлены номера узлов, далее в строке таблицы следует список соседних узлов. По этой причине число колонок в каждой из строк различно.

Таблица 2.1

2.3 Представление ориентированных граф

Представление ориентированных граф элементами матриц смежности и инцидентности являются 0, 1, -1. Пусть даны два ориентированных графа (рис. 2.3.1), тогда матрицы смежности и инцидентности для них будут выглядеть как в таблицe 2.3

Рис. 2.3.1 Ориентированные графы

Таблица 2.3

В матрице инцидентности для ориентированных граф ставится 0 - если вершина и ребро не инцидентны, -1 - если вершина является началом, 1 - если вершина является концом.

3. Виды графов и операции над ними

3.1 Элементы графов

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

Граф G'(V', Е') называется подграфом графа G(V, Е) (обозначается G' G), если V' V и/или Е' Е.

Если V' = V, то G ' называется остовным подграфом G.

Если V' V & Е' Е & (V' V Е' Е), то граф G ' называется собственным подграфом графа G.

Подграф G'(V' , Е') называется правильным подграфом графа G(V,Е), если G ' содержит все возможные ребра G:

и,v V' (и, v) Е (и, v) Е'.

Правильный подграф G '(V ' , Е') графа G (V, Е) определяется подмножеством вер шин V '.

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

v0, e1, v1, e2, v2,…,ek, vk,

Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер.

Если v0 = vk, то маршрут замкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи v0, e1, v1, e2, v2,…,ek, vk,

вершины v0 и vk, называются концами цепи. Говорят, что цепь с концами и и v соединяет вершины и и v. Цепь, соединяющая вершины и и v, обозначается (и, v). Очевидно, что если есть цепь, соединяющая вершины и и v, то есть и простая цепь, соединяющая эти вершины.

Страницы: 1, 2, 3, 4