Составители:
Рубрика:
7
вершинами графа и вершинами фигуры, а также между ребрами графа и
отрезками линий фигуры существует взаимно однозначное соответствие.
Можно доказать следующее утверждение:
Теорема 1. Для каждого конечного графа существует его геометрическая
реализация в трехмерном евклидовом пространстве. Заметим, что
сформулированная теорема не справедлива для случая плоскости, т.е. не
всякий граф допускает на плоскости геометрическую реализацию. В частности,
приведенный на рис.1а граф не может быть реализован на плоскости, т.е. его
нельзя расположить на плоскости таким образом, чтобы ни одна из пар линий
не пересекалась. В связи со сказанным большой теоретический и прикладной
интерес представляет вопрос о плоской реализуемости произвольного
конечного графа. Ответ на него дали независимо друг от друга выдающийся
русский математик академик Л.С. Понтрягин и известный польский ученый К.
Куратовский. Они показали, что для того, чтобы конечный граф можно было
реализовать на плоскости, необходимо и достаточно, чтобы он не имел
подграфов, вида приведенных на рис.1б,в.
Кроме геометрической реализации графа, существуют и другие способы
задания графа, одним из которых является задание графа с помощью матрицы
смежностей. Этот способ, изложение которого приведено ниже, очень удобен
для “введения” графа в память ЭВМ. Построение матрицы смежностей
производится следующим образом.
Пусть G=(X,U) граф, где X=x
1
, x
2
, ... ,x
n
- множество его вершин. Любая
пара взятых вершин соединена или нет ребром. Нарисуем прямоугольную
таблицу (матрицу) размером n×n, элементы которой формируются по
следующему правилу. Если в графе G вершины x
i
и x
j
соединены ребром, в
таблице на пересечении i- ой строки и j- го столбца поставим единицу, в
противном случае на соответствующем месте поставим нуль. Заполненная
таким образом таблица u носит название матрицы смежности. Нетрудно
убедиться, что матрица смежности симметрична относительно главной
диагонали, элементами которой будут нули. Если граф имеет петли, т.е. ребра
вида ( x
i
, x
i
) или дуги, выходящие из некоторой вершины и в нее же заходящие,
то на главной диагонали в соответствующих местах будут стоять единицы.
Для графа изображенного на рис.1а, например, матрица смежностей имеет
вид:
Таблица 1
x
1
x
2
x
3
x
4
x
5
x
6
x
1
0 0 0 1 1 1
x
2
0 0 0 1 1 1
x
3
0 0 0 1 1 1
x
4
1 1 1 0 0 0
x
5
1 1 1 0 0 0
x
6
1 1 1 0 0 0
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
