Лекция 6 Графы

Содержание

Слайд 2

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Граф

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Граф – это

множество вершин и соединяющих их ребер.
Примеры графов:
Слайд 3

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Примеры

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Примеры графов:

Схема алгоритма

– размеченный орграф, где вершинами являются блоки алгоритма, а дугами – линии передачи управления.
Система дорог – взвешенный размеченный граф, где вершины – города, а ребра – дороги между городами. Вес ребра – длина дороги, метка вершины – название города. Если дороги односторонние, то граф – ориентированный.
Слайд 4

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Представление

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

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

1.

Последовательность ребер (дуг), перед которой указывается количество вершин графа. Каждое ребро (дуга) задается парой смежных вершин. Такая форма удобна для внешнего представления графа при его вводе.
Пример:
5 - число вершин
0 1
1 2
2 3
2 4
3 4
4 0
4 2
Слайд 5

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Если

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Если в таком

виде хранить граф в памяти, нужно описать два параллельных массива для хранения смежных вершин.
Например:
#define NMAX 10 /* макс. число вершин */
#define RMAX 100 /* макс. число ребер */
int v1 [RMAX]; /* массивы смежных */
int v2 [RMAX]; /* вершин */
int n; /* число вершин графа */
int r; /* число ребер графа */
Слайд 6

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ 2.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

2. Матрица смежности

– это квадратная матрица размерности n*n (n – число вершин), в которой элемент
ms[i][j] = 1, ли есть дуга i –> j , и = 0 в противном случае.
Пример матрицы смежности для графа, представленного на рис. а):
| 0 1 2 3 4 5
--------------------
0 | 0 1 0 0 0 1 Для неориентированного графа матрица
1 | 1 0 1 1 1 0 смежности симметрична относительно
2 | 0 1 0 0 0 0 главной диагонали.
3 | 0 1 0 0 1 1
4 | 0 1 0 1 0 0
5 | 1 0 0 1 0 0
Слайд 7

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Пример

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Пример ввода неориентированного

графа в виде последовательности ребер и формирования матрицы смежности.
#define NMAX 10 /* макс. число вершин */
/* Функция ввода графа */
int VvodGraf ( int ms [NMAX] [NMAX] )
/* ms – матрица смежности */
/* Возвращаемое значение – число вершин графа */
{ int n; /* число вершин графа */
int i, j; /* номера вершин */
puts (“\nВведите число вершин графа (<=10)”);
scanf (“%d”, &n);
Слайд 8

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ /*

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ
/* Обнуление матрицы

смежности */
for (i=0; i for (j=0; j puts (“Введите последовательность ребер, завершив ввод ”);
puts (“нажатием Ctrl-Z”);
while (scanf(“%d %d”, &i,&j) !=EOF)
ms[i][j] = ms[j][i] = 1;
return n;
}
/* Главная функция */
void main()
{ int g[NMAX][ NMAX] ; /* матрица смежности */
int n; /* число вершин графа */
…
n = VvodGraf (g); /* вызов ф-ции ввода графа */
…
}
Слайд 9

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ 3.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

3. Матрица весов

– квадратная матрица размерности n*n (n – число вершин), в которой элемент
mw [i][j] = вес дуги i –> j
Например, дана система дорог: вершины – города, ребра – дороги. Вес ребра – длина дороги.
Слайд 10

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Описание

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Описание на языке

С:
#define NMAX 10 /* макс. число вершин */
int mw[NMAX][ NMAX] ; /* матрица весов */
int n; /* число вершин */
Слайд 11

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ 4.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ
4. Матрица инцидентности

– это прямоугольная матрица размерности n*r (n – число вершин, r – число ребер).
Для неориентированного графа элемент матрицы:
1, если i-я вершина инцидентна j-му ребру,
mi[i][j] = 2, если j-е ребро – петля i-й вершины,
0, если i-я вершина не инцидентна j-му ребру.
Слайд 12

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Для

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ


Для орграфа

элемент матрицы инцидентности:
-1, если j-я дуга выходит из i-й вершины
mi[i][j] = 1, если j-я дуга входит в i-ю вершину
2, если j-я дуга – петля i-й вершины,
0, если i-я вершина не инцидентна j-й дуге.
Слайд 13

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Описание

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Описание на языке

С:
#define NMAX 10 /* макс. число вершин */
#define RMAX 100 /* макс. число ребер (дуг) */
int mi[NMAX][ RMAX]; /* м-ца инцидентности */
int n; /* число вершин */
int r; /*число ребер */
Слайд 14

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ 5.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

5. Векторы смежности

.
Для каждой вершины в векторе хранятся номера смежных с ней вершин.
Векторы смежности:
Слайд 15

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Описание

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

Описание на языке

С:
#define NMAX 10 /* макс. число вершин */
int vsm[NMAX][ NMAX+1]; /* векторы смежности */
int n; /* число вершин */
Число столбцов матрицы vsm равно NMAX+1, так как последовательность смежных вершин в каждой строке матрицы удобно хранить с признаком конца, например -1. vsm[i] – вектор смежности для i-й вершины.
Слайд 16

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ Эта

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ
Эта форма представления

графа может быть использована и для ввода графа.
Пример.
Введите число вершин: 4
Введите номера смежных вершин
0: 1 3 -1
1: 0 2 3 -1
2: 1 -1
3: 0 1 -1
Слайд 17

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г. КГТУ (КАИ), кафедра АСОИУ 6.

Бикмурзина А.Р., Захарова З.Х., Хохлов Д.Г.

КГТУ (КАИ), кафедра АСОИУ

6. Списки смежности

.
Для каждой вершины хранится список смежных с ней вершин.
- Предыдущая
Навигаторы ГЛОНАСС/GPS – ожидания и реальность
Следующая -
Extreme matchmoving: Mission Possible. Введение в экстремальный matchmoving Matchmoving (mm) процесс крайне предсказуемый. Это одна из технологий CG, - презентаци

Похожие презентации

В ГБУ «Комплексный центр социального обслуживания населения г.Каменска-Уральского» работает социальный пункт проката средств ре
Инструменты построения информационных систем на основе Wiki-технологии и онтологий предметных областей Шестаков Владимир
Народная лоскутная кукла. Зерновушка - презентация к уроку Технологии
Тема: « ТЕХНОЛОГИЧЕСКИЙ ПРОЦЕСС ИЗГОТОВЛЕНИЯ ЩИТОВОГО ДВЕРНОГО БЛОКА » Преподаватель Астапенко В.А,
Оптическое распознавание символов
Ателье "Модница" - презентация к уроку Технологии_
Проектная деятельность на уроках технологии - презентация к уроку Технологии_
Салфетки Работа учителя технологии МОУ СОШ №3 Суворовой Л. Н. Балаково 2008
Акмолинская область город Степногорск школа-гимназия №4 им.Л.Н.Толстого Бизнес-проект благоустройства детской площадки
Agile Death March Projects Путь ниндзя
Художественная обработка древесины - презентация к уроку Технологии
Вышивка, как один из видов декоративно-прикладного искусства. Подготовка к вышиванию. Презентация урока в 5 классе Подготовила уч
Ассортимент и характеристика сыров - презентация к уроку Технологии
Кукла из бутылки и носков
Метод фокальных объектов
Мастер-класс изготовление корзиночки на основе мыла
Декоративная подушечка - презентация к уроку Технологии_
Качество одежды и экспертиза
Изготовление белой совы из бисера
Формирование ключевых компетентностей через интегрированные технологии - презентация к уроку Технологии_____________________________________________
или как продать Agile команде? Михаил Карпов
Елочка за полчаса Вишератина Надежда Владимировна, учитель технологии МОУ СОШ № 4, г. Сыктывкар, Республика Коми
Мастер-класс по изготовлению кормушки МОУ Афанасьевская средняя общеобразовательная школа учитель начальных классов Веретенн
 Алтернативни извори на  енергија
Из чего это сделано? - презентация к уроку Технологии
Тема. Электробезопасность на производстве Образовательная цель: Сформировать знания о - Основных причинах поражения электриче
Архитектурные проблемы Flex-приложений
Муниципальное бюджетное общеобразовательное учреждение «Средняя общеобразовательная школа № 15 п. Березайка» Презентация к ур
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть