lecture_04

Структура графов

Основные определения и свойства графов

Козлов Александр Иванович

Институт программных систем

Строгое определение графа

Графом G(V; E) называется конечное множество V , называемое множеством вершин, и множество E двухэлементных подмножеств множества V . Множество E называется множеством ребер (дуг).

Строгое определение графа

Графом G(V; E) называется конечное множество V , называемое множеством вершин, и множество E двухэлементных подмножеств множества V . Множество E называется множеством ребер (дуг).

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

Строгое определение графа

Графом G(V; E) называется конечное множество V , называемое множеством вершин, и множество E двухэлементных подмножеств множества V . Множество E называется множеством ребер (дуг).

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

Количество вершин графа G(V; E) мы будем обозначать через jV j, а количество ребер через jEj.

Пример 1

Вершины и рёбра

Вершины инцидентные или смежные. Ребро инцидентное вершинам. Рёбра смежные. Петля.

Виды графов

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

Виды графов

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

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

Виды графов

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

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

Если же допускается и наличие петель и существование более одного ребра между двумя вершинами, то такой объект называется

псевдографом.

Везде далее, если не будет оговорено противное, речь пойдет о графах без петель и параллельных ребер.

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

Рассмотрим два матричных и два списочных представления графа:

Iматрица смежности;

Iматрица инцидентности;

Iсписок ребер;

Iструктура смежности графа.

Будем предполагать, что вершины графа обозначены символьной строкой и всего их от 1 до n, а ребер – от 1 до m. Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.