Пример 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. Дан орграф в виде матрицы инцидентности, числа вершин и числа ребер. Опишите функцию вывода числа предшественников каждой вершины. Приведите пример вызова этой функции.

Дата добавления: 2014-01-04