Графы презентация

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

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

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

Последовательность ребер (дуг), перед которой указывается количество вершин графа. Каждое ребро (дуга) задается парой смежных вершин. Такая форма удобна для внешнего представления графа при его вводе.

Пример:

5 - число вершин
0 1
1 2
2 3
2 4
3 4
4 0
4 2

виде хранить граф в памяти, нужно описать два параллельных массива для хранения смежных вершин.

Например:



#define NMAX 10 /* макс. число вершин */
#define RMAX 100 /* макс. число ребер */
int v1 [RMAX]; /* массивы смежных */
int v2 [RMAX]; /* вершин */
int n; /* число вершин графа */
int r; /* число ребер графа */

– это квадратная матрица размерности 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

графа в виде последовательности ребер и формирования матрицы смежности.


#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 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); /* вызов ф-ции ввода графа */
…
}

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

С:

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

– это прямоугольная матрица размерности n*r (n – число вершин, r – число ребер).



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

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

С:

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

.

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

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

С:

#define NMAX 10 /* макс. число вершин */
int vsm[NMAX][ NMAX+1]; /* векторы смежности */
int n; /* число вершин */

Число столбцов матрицы vsm равно NMAX+1, так как последовательность смежных вершин в каждой строке матрицы удобно хранить с признаком конца, например -1. vsm[i] – вектор смежности для i-й вершины.

графа может быть использована и для ввода графа.


Пример.
Введите число вершин: 4
Введите номера смежных вершин
0: 1 3 -1
1: 0 2 3 -1
2: 1 -1
3: 0 1 -1

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

С:

#define NMAX 10 /* макс. число вершин */



/* тип элемента списка */
struct LIST
{ int v; /* вершина */
struct LIST *next; /* ссылка на следующий элемент */
}
struct LIST *p [NMAX]; /* массив указателей списков смежности */
int n; /* число вершин */