Пример 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; /*число ребер */

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