lecture_04
.pdfСтруктура графов
Основные определения и свойства графов
Козлов Александр Иванович
Институт программных систем
Козлов Александр Иванович |
Институт программных систем |
Структура графов |
|
Строгое определение графа
Графом 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. Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.
Козлов Александр Иванович |
Институт программных систем |
Структура графов |
|