Технологии Программирования. 9 лекция
.pdfТема 7:
Основы теории графов
Теория графов началась с задачи про 7 кенигсбергских
мостов.
Задача 1: Может ли пешеход обойти все мосты (рис.),
пройдя по каждому из них только один раз, и вернуться в исходную точку?
Рис.1 Схема расположения мостов в Кенигсберге.
Л. Эйлер блестяще решил эту задачу при помощи теории графов.
Задача 2 (Задача четырех красок). Можно ли любую карту так раскрасить четырьмя красками, чтобы никакие две области, имеющие общий участок границы, не были окрашены в один и
тот же цвет?
К широко известным задачам относится так же следующая задача,
предложенная Кэрроллом.
Задача 3 (Задача о домиках и колодцах). Имеются три
домика и три колодца. Можно ли проложить тропинки от каждого домика к каждому колодцу так, чтобы тропинки
не пересекались?
1. Понятие графа.
Чтобы дать определение графа, необходимо ввести несколько промежуточных определений
Кружок (или точка) – вершина
графа (vertex).
Прямая, соединяющая любые две
вершины ребро графа (edge) .
Рис.2 Пример графа G1
Опр.
Вершинами графа будем называть множество точек VG
={V1,V2,V3,…,Vn} или VG ={1,2,3,…,n}.
Опр.
Ребра графа будем обозначать парами
EG={(V1,V2), (V3,V4)} или EG={(1,2), (3,4)}
Ребра графа - пары
EG={(V1,V2), (V3,V4)} или EG={(1,2), (3,4)}
Рис.3
Пары могут быть упорядоченными и неупорядоченными.
Неупорядоченная пара вершин называется
(неориентированное) ребро (undirected edge).
Упорядоченная пара вершин называется
ориентированным ребром (directed edge) или дугой (arc).
Опр. Граф G (graph)– это множество вершин VG и
множество ребер EG.
Иногда граф называют сетью (network), вершины - узлами (node), ребра - связями (bond).
Опр. Неориентированный граф – граф, для которого
при записи ребра не имеет значения, в каком порядке
выписаны вершины, т.е. пары вершин (2,3) и (3,2) задают
одно и то же ребро.
неориентированный граф - граф, содержащий только неориентированные ребра.
Граф G1(неориентированный) Рис.2
состоит 6 вершин
VG ={1,2,3,…,6}
и шести ребер
EG={(0,1), (0,2), (0,5) , (2,3) , (3,4) , (4,5)}
2.Представление неориентированного графа в памяти компьютера.
Существует несколько способов представления графов в памяти.
•Один из способов использует матрицу смежности.
Для графа G1 матрица смежности имеет вид
|
|
|
столбцы |
|
|
|
Рис.2 |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
С |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
Т |
|
|||||||
|
|
|
|
|
|
|
|
|
Р |
2 |
1 |
0 |
0 |
1 |
0 |
0 |
|
О |
|
|||||||
К |
3 |
0 |
0 |
1 |
0 |
1 |
0 |
|
и |
|
|||||||
|
4 |
0 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
5 |
1 |
0 |
0 |
0 |
1 |
0 |
|
матрица 6x6
В ячейках Aij и Aji матрицы ставим 1,
если вершины соединены ребром,
в противном случае заполняем 0.
При изменении нумерации вершин
графа меняется и его матрица
смежности.
ОПР. Матрица смежности является симметричной, если на
главной диагонали стоят нули.
Преимущество
Чтобы узнать, соединены ли вершины i,j ребром, достаточно
только проверить, чему равен элемент Aij
Недостаток такого представления: - для хранения графа из n вершин и nребер требуется
n x n ячеек памяти.
•Второй способ задания графа – использование
списка смежности.
Каждой вершине i ставятся в соответствие только
вершины, которые находятся с ней в паре.
Число строк = числу вершин.
Число столбцов = числу связей.
Рис.2
Недостатки:
чтобы выяснить соединены ли вершины i,j ребром,
необходимо проделать большее число операций.
Пример 1 (матрица смежности)
#include <fstream.h> main()
{ int **Graf, i, j, N;
ifstream input(” Gtaf.dat”); /* Открываем файл для чтения */
input>>N; //читаем количество вершин из файла
// выделяет динам. память для матрицы смежности
Graf=new int *[N];
for(i=0;i<N;i++) Graf[i]=new int [N];
// обнуляем все элементы матрицы
for(i=0;i<N;i++) for(j=0;j<N;j++) Graf[i][j]=0; while( !input.eof() )
{input>>i>>j; Graf[i][j]=1; Graf[j][i]=1;} return 0;
}