Графы

Лекция 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. Схема алгоритма – размеченный орграф, где вершинами являются блоки алгоритма, а дугами – линии передачи управления. 2. Система дорог – взвешенный размеченный граф, где вершины – города, а ребра – дороги между городами. Вес ребра – длина дороги, метка вершины – название города. Если дороги односторонние, то граф – ориентированный. Графы можно использовать в различных областях для описания строения разнообразных систем. Вершинами графа могут быть объекты произвольгой природы, а дугами или ребрами – различные типы связей между ними: математические, физические, общественные, экономические и т.п. Представление графов Рассмотрим наиболее распространенные формы представления графов. 1. Последовательность ребер (дуг), перед которой указывается количество вершин графа. Каждое ребро (дуга) задается парой смежных вершин. Такая форма удобна для внешнего представления графа при его вводе. Пример для рис. 20.1.в: 5 - число вершин 0 1 1 2 2 3 2 4 3 4 4 0 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 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 #include #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 v2, где v1 – предшественник, v2 – преемник. в) Напечатать номер вершины, имеющей наибольшее число преемников. г) Определить число вершин, соединенных дугами в обоих направлениях. 4. Задан граф в виде количества вершин n<=7, количества ребер k<=28 и матрицы инцидентности. а) Для каждой вершины напечатать список инцидентных ей ребер. б) Определить степень каждой вершины графа. в) Проверить, есть ли вершины со степенью 0. г) Определить число вершин, инцидентных только одному ребру. д) Определить наибольшее число смежных между собой ребер, инцидентных одной и той же вершине. е) Проверить, есть ли в графе петли.