Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция 20. Графы
Графы
Граф – это множество вершин и соединяющих их ребер.
На рис. 20.1 приведены примеры графов.
а) неориентированный б) неориентированный в) ориентированный
связный граф несвязный граф граф (орграф)
Рис. 20.1. Примеры графов
В ориентированном графе ребра имеют направление и называются дугами. Если есть дуга v1 –> v2 (от вершины v1 к вершине v2), то вершина v1 называется предшественником вершины v2, а вершина v2 – преемником вершины v1.
Вершины, соединенные ребром или дугой, называют смежными. Ребра (дуги), имеющие общую вершину, также называют смежными. Например, на рис. 20.1.а вершина 1 смежна с вершинами 0, 2, 3, 4, на рис. 20.1.в вершина 4 смежна с 0, 2, 3.
Ребро (дуга) и любая из его двух вершин называются инцидентными. Степень вершины – это количество инцидентных ей ребер (дуг). Например, на рис. 20.1.б вершина 0 имеет степень 2, вершина 1 – степень 3, а вершина 4 – степень 0. На рис. 19.1.в вершина 0 имеет степень 2, вершина 2 – степень 4.
Степень графа – это максимальная степень его вершин. Граф на рис. 20.1.а имеет степень 4.
Ребро (дуга), соединяющее вершину с ней самой, называют петлей.
Путь – это последовательность вершин, в которой каждая вершина соединена ребром или дугой со следующей вершиной. Длина пути равна количеству его ребер (дуг). Например, в графе на рис. 20.1.а между вершинами 0 и 3 есть три пути:
0 – 1 – 3 (длина 2),
0 – 1 – 4 – 3 (длина 3),
0 – 5 – 3 (длина 2).
Замкнутый путь, в котором все ребра (дуги) различны, называют циклом. На рис. 20.1.а три цикла:
0 – 1 – 3 – 5 – 0 ,
0 – 1 – 4 – 3 – 5 – 0 ,
1 – 3 – 4 – 1 .
У взвешенного графа каждое ребро (дуга) имеет вес – числовую или символьную характеристику. У размеченного графа каждой вершине соответствует некоторая информация – метка.
Примеры графов:
Графы можно использовать в различных областях для описания строения разнообразных систем. Вершинами графа могут быть объекты произвольгой природы, а дугами или ребрами – различные типы связей между ними: математические, физические, общественные, экономические и т.п.
Представление графов
Рассмотрим наиболее распространенные формы представления графов.
1. Последовательность ребер (дуг), перед которой указывается количество вершин графа. Каждое ребро (дуга) задается парой смежных вершин. Такая форма удобна для внешнего представления графа при его вводе.
Пример для рис. 20.1.в:
4 2
Если в таком виде хранить граф в памяти, нужно описать два параллельных массива для хранения смежных вершин.
Пример 20.1.
#define NMAX 10 /* макс. число вершин */
#define RMAX 55 /* макс. число ребер */
/* RMAX = NMAX * (NMAX - 1) / 2 + NMAX; */
int v1 [RMAX]; /* массивы смежных */
int v2 [RMAX]; /* вершин */
int n; /* число вершин графа */
int r; /* число ребер графа */
2. Матрица смежности – это квадратная матрица размерности n*n (n – число вершин), в которой элемент
1, ли есть дуга i –> j ,
ms[i][j] =
0 в противном случае.
Пример матрицы смежности для графа, представленного на рис. 20.1.а:
| 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
Пример 20.2. Ввод с клавиатуры неориентированного графа в виде последовательности ребер и формирование матрицы смежности. Конец ввода ребер отмечается нажатием клавиш Ctrl – Z (конец файла).
#define NMAX 10 /* макс. число вершин */
/* Функция ввода графа */
int VvodGraf ( int ms [NMAX] [NMAX] )
/* ms – матрица смежности */
/* Возвращаемое значение – число вершин графа */
{ int n; /* число вершин графа */
int i, j; /* номера вершин */
puts (“\nВведите число вершин графа (<=10)”);
scanf (“%d”, &n);
/* Обнуление матрицы смежности */
for (i=0; i<n; i++)
for (j=0; j<n; j++) ms[i][j] = 0;
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); /* вызов функции ввода графа */
…
}
3. Матрица весов – квадратная матрица размерности n*n (n – число вершин), в которой элемент
mw [i][j] = вес дуги i –> j
Например, дана система дорог: вершины – города, ребра – дороги. Вес ребра – длина дороги.
50 45 | 0 1 2 3 4 5
------------------------
30 60 0 | 0 50 0 0 0 100
30 1 | 50 0 45 60 30 0
100 mw = 2 | 0 45 0 0 0 0
60 3 | 0 60 0 0 30 60
4 | 0 30 0 30 0 0
5 | 100 0 0 60 0 0
Рис. 20.2. Пример системы дорог и матрицы весов.
Описание на языке С:
#define NMAX 10 /* макс. число вершин */
int mw[NMAX][ NMAX] ; /* матрица весов */
int n; /* число вершин */
4. Матрица инцидентности – это прямоугольная матрица размерности n*r ( n – число вершин, r – число ребер).
Для неориентированного графа элемент матрицы:
1, если i-я вершина инцидентна j-му ребру,
mi[i][j] = 2, если j-е ребро – петля i-й вершины,
0, если i-я вершина не инцидентна j-му ребру.
| 0 1 2 3 4 5 6
1 ----------------------------------
0 2 6 0 | 1 0 0 0 0 1 0
4 1 | 1 1 1 0 1 0 0
mi = 2 | 0 1 0 0 0 0 2
3 3 | 0 0 1 1 0 0 0
5 4 | 0 0 0 1 1 1 0
Рис. 20.3. Пример графа и матрицы инцидентности.
Для орграфа элемент матрицы инцидентности:
-1, если j-я дуга выходит из i-й вершины j
mi[i][j] = 1, если j-я дуга входит в i-ю вершину j
2, если j-я дуга – петля i-й вершины,
0, если i-я вершина не инцидентна j-й дуге.
| 0 1 2 3 4 5
0 1 -------------------------------
0 | -1 0 0 1 0 0
4 mi = 1 | 1 -1 0 0 1 0
3 2 2 | 0 1 1 0 0 0
3 | 0 0 -1 -1 -1 2
5
Рис. 20.4. Пример орграфа и матрицы инцидентности.
Описание на языке С:
#define NMAX 10 /* макс. число вершин */
#define RMAX 100 /* макс. число ребер (дуг) */
int mi[NMAX][ RMAX] ; /* матрица инцидентности */
int n; /* число вершин */
int r; /*число ребер */
Пример 20.3.
/* Функция вывода матрицы инцидентности */
void VivodMatrIn (int mi[NMAX][RMAX], int n, int r)
{
int i, j;
printf (“ |”);
for (j=0; j<r; j++) printf (“%3d”, j);
printf (“\n”);
for (j=0; j<3*r +2; j++) putchar(‘–’);
for (i=0; i<n; i++)
{ printf (“\n%d|”, i);
for (j=0; j<r; j++)
printf (“%3d”, mi[i][j]);
}
printf (“\n”);
}
5. Векторы смежности .
Для каждой вершины в векторе хранятся номера смежных с ней вершин.
Векторы смежности:
Рис. 20.5. Пример графа и векторов смежности.
Для хранения векторов смежности в программе удобно использовать двумерный массив, где i-я строка – это вектор смежности для i-й вершины.
Описание на языке С:
#define NMAX 10 /* макс. число вершин */
int vsm[NMAX][ NMAX+1] ; /* векторы смежности */
int n; /* число вершин */
Число столбцов матрицы vsm равно NMAX+1, так как последовательность смежных вершин в каждой строке матрицы удобно хранить с признаком конца, например -1. vsm[i] – вектор смежности для i-й вершины.
Эта форма представления графа может быть использована и для ввода графа.
Пример 20.4.
/* Функция ввода графа и формирования векторов смежности */
void VectSm (int vsm[NMAX][NMAX+1], int *pn)
/* Вых. данные: vsm – векторы смежности,
*pn – число вершин графа */
{ int i, j; /* номера вершин */
printf (“Введите число вершин:”);
scanf(“%d”, pn);
puts (Введите номера смежных вершин);
for (i = 0; i < *pn: i++)
{ printf (“%d: ”, i);
j = -1;
do scanf(“%d”, &vsm[i][++j]);
while (vsm[i][j] != -1);
}
}
Граф, представленный на рис. 20.5, вводить следует в виде (выделено жирным шрифтом):
Введите число вершин: 4
Введите номера смежных вершин
0: 1 3 -1
1: 0 2 3 -1
2: 1 -1
3: 0 1 -1
/* Вызов функции */
int vsm[NMAX][ NMAX+1] ; /* векторы смежности */
int n; /* число вершин */
VectSm ( vsm, &n);
В результате выполнения функции получится матрица:
| 0 1 2 3 4
--------------------
0 | 1 3 -1
vsm = 1 | 0 2 3 -1
2 | 1 -1
3 | 0 1 -1
6. Списки смежности .
Для каждой вершины хранится список смежных с ней вершин.
Рис. 20.6. Пример графа и списков смежности.
Описание на языке С:
#define NMAX 10 /* макс. число вершин */
/* тип элемента списка */
struct LIST
{ int v; /* вершина */
struct LIST *next; /* ссылка на следующий элемент */
};
struct LIST *p [NMAX]; /* массив указателей списков смежности */
int n; /* число вершин */
Задача 20.1. Дан граф без петель в виде количества вершин n<=7 и матрицы смежности. Сформировать для этого графа матрицу инцидентности.
Программа:
#include <stdio.h>
#include <conio.h>
#define NMAX 7 /* максимальное число вершин графа */
#define RMAX 21 /* максимальное число ребер */
/*---------------------------------------------------------*/
/* функция ввода матрицы смежности */
/*---------------------------------------------------------*/
void VVOD_MATR_SM ( int g1 [NMAX][NMAX] , int n )
/* Входные данные: n – количество вершин */
/* Выходные данные: g1 – матрица смежности */
{ int i,j ; /* параметры циклов */
printf ("Введите матрицу смежности:\n\n");
printf (" ¦ ");
for (j=0; j<n; j++) printf ("%d ",j);
putchar ('\n');
for (i=0; i<2*n+2; i++) putchar ('-');
for (i=0; i<n; i++)
{ printf ("\n%d¦ ",i);
for (j=0; j<n; j++) scanf ("%d", &g1[i][j]);
}
putchar ('\n');
}
/*------------------------------------------------------------*/
/* функция вывода матрицы инцидентности */
/*------------------------------------------------------------*/
void VIVOD_MATR_IN ( int g2 [NMAX][RMAX], int n, int k )
/* Входные данные: g2 – матрица инцидентности ,
n – количество вершин ,
k – количество ребер */
{ int i,l ; /* параметры циклов */
printf ("Матрица инцидентности\n\n");
printf (" ¦ ");
for (l=0; l<k; l++) printf ("%3d ", l );
putchar ('\n');
for (i=0; i<3*k+2; i++) putchar ('-');
for (i=0; i<n; i++)
{ printf ("\n%d¦ ", i);
for (l=0; l<k; l++)
printf ("%3d ",g2[i][l]);
}
putchar ('\n');
}
/*------------------------------*/
/* главная функция */
/*------------------------------*/
void main()
{
int g1 [NMAX][NMAX] , /* матрица смежности */
g2 [NMAX][RMAX] = {0} , /* м-ца инцидентности */
n , /* количество вершин */
k ; /* количество ребер */
int i, j; /* индексы элементов матриц g1,g2 */
printf ("\nВведите количество вершин:");
scanf ("%d", &n);
VVOD_MATR_SM (g1, n); /* ввод матрицы смежности g1 */
/* Формировавание матрицы инц-ти g2 */
k=0;
for (i=0; i<n; i++)
for (j=i; j<n; j++)
if (g1[i][j])
{ g2[i][k]=1;
g2[j][k]=1;
k++;
}
VIVOD_MATR_IN (g2, n, k ); /* вывод м-цы g2 */
getch();
}
Тесты
1. Исходные данные: Ожидаемый результат:
n=4 матрица смежности матрица инцидентности
¦ 0 1 2 3 ¦ 0 1 2 3 4
0 1 2 ---------- ------------
0 0¦ 0 1 0 1 0¦ 1 1 0 0 0
3 1¦ 1 0 1 1 1¦ 1 0 1 1 0
1 4 2¦ 0 1 0 1 2¦ 0 0 1 0 1
3¦ 1 1 1 0 3¦ 0 1 0 1 1
2. Граф, изображенный на рис. 20.1а. n=NMAX=7. Вид матрицы смежности приведен на рис. 20.2а. Ожидаемый результат: матрица инцидентности, приведенная на рис. 20.2б.
3. Полный граф (все вершины смежны между собой), число вершин максимальное.
Исходные данные:
n=7,
матрица смежности:
¦ 0 1 2 3 4 5 6
----------------
0¦ 0 1 1 1 1 1 1
1¦ 1 0 1 1 1 1 1
2¦ 1 1 0 1 1 1 1
3¦ 1 1 1 0 1 1 1
4¦ 1 1 1 1 0 1 1
5¦ 1 1 1 1 1 0 1
6¦ 1 1 1 1 1 1 0
Ожидаемый результат:
матрица инцидентности:
¦ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
-----------------------------------------------------------------
0¦ 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1¦ 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
2¦ 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0
3¦ 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0
4¦ 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0
5¦ 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1
6¦ 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1
4. В графе нет ребер.
Исходные данные: Ожидаемый результат:
n=3 м-ца смежности м-ца инцидентности
¦ 0 1 2 ¦
-------- --
0¦ 0 0 0 0¦
1¦ 0 0 0 1¦
2¦ 0 0 0 2¦
Контрольные вопросы и упражнения
1. Что такое граф? Нарисуйте какой-нибудь неориентированный граф. Есть ли в этом графе циклы?
2. Приведите пример орграфа. Определите степень этого орграфа и степень каждой его вершины.
3. Что такое путь между двумя вершинами графа? Какой граф является связным?
4. Какой граф называется размеченным и какой – взвешенным?
5. Нарисуйте матрицу смежности для орграфа на рис. 20.1.в. Как по матрице смежности определить преемников и предшественников заданной вершины?
6. Дан орграф в виде матрицы смежности и количества вершин. Опишите функцию определения степени заданной вершины. Приведите пример вызова этой функции.
7. Дан граф в виде матрицы смежности и количества вершин. Опишите функцию вывода номеров вершин со степенью 4. Приведите пример вызова этой функции.
8. Нарисуйте матрицу инцидентности для графа на рис. 20.1.а. Как по матрице инцидентности определить степень каждой вершины и степень графа?
9. Дан орграф в виде матрицы инцидентности, числа вершин и числа ребер. Опишите функцию вывода номеров вершин, имеющих петли. Приведите пример вызова этой функции.
10. Дан орграф в виде матрицы инцидентности, числа вершин и числа ребер. Опишите функцию вывода числа предшественников каждой вершины. Приведите пример вызова этой функции.
Выполнение контрольных заданий
1. Получите у преподавателя индивидуальное задание.
2. Составьте программу на языке С и подберите тесты для проверки программы на компьютере.
3. Отладьте программу на компьютере.
5. Оформите и сдайте отчет.
Контрольные задания
1. Задан граф в виде количества вершин n<=10 и последовательности ребер (каждое ребро задается парой смежных вершин). Получить матрицу смежности.
а) Напечатать матрицу смежности. Проверить, есть ли в графе петли.
б) Напечатать матрицу смежности. Проверить, есть ли в графе вершины, не смежные с другими.
в) Напечатать для каждой вершины номера смежных вершин.
г) Проверить, есть ли в графе вершина, смежная со всеми другими вершинами.
д) Определить степень каждой вершины графа.
е) Напечатать номера вершин со степенью 1.
ж) Определить степень графа (максимальную степень его вершин).
2. Задан орграф в виде количества вершин n<=10 и последовательности дуг (дуга задается парой “предшественник преемник”).
а) Напечатать номера вершин, имеющих более двух преемников.
б) Напечатать номера вершин, не имеющих предшественников.
в) Для каждой вершины напечатать номера всех предшественников.
г) Проверить, есть ли в графе вершины, имеющие только одного преемника.
3. Задан орграф в виде количества вершин n<=10 и матрицы смежности.
а) Напечатать номера вершин, имеющих и предшественников и преемников.
б) Напечатать список дуг орграфа в виде: v1 –> v2, где v1 – предшественник, v2 – преемник.
в) Напечатать номер вершины, имеющей наибольшее число преемников.
г) Определить число вершин, соединенных дугами в обоих направлениях.
4. Задан граф в виде количества вершин n<=7, количества ребер k<=28 и матрицы инцидентности.
а) Для каждой вершины напечатать список инцидентных ей ребер.
б) Определить степень каждой вершины графа.
в) Проверить, есть ли вершины со степенью 0.
г) Определить число вершин, инцидентных только одному ребру.
д) Определить наибольшее число смежных между собой ребер, инцидентных одной и той же вершине.
е) Проверить, есть ли в графе петли.
PAGE 205