Дискретная математика: графы и автоматы. Альпин Ю.А - 6 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

6 Глава 1. Неориентированные графы
Говорят, что вершины u и v связаны, если u = v или существует
(u, v)-маршрут. Граф называется связным, если любые две его вер-
шины связаны. Если граф не связен, то он представляет собой объ-
единение нескольких связных подграфов. Чтобы выразиться точнее,
введем понятие подграфа.
Граф (V
1
, E
1
) называется подграфом графа (V, E), если V
1
⊆ V ,
E
1
⊆ E. Например, цепь в графе можно рассматривать как подграф.
Говорят, что подграф порождён подмножеством вершин V
1
, если E
1
состоит из рёбер, соединяющих вершины из V
1
. Говорят, что подграф
порождён подмножеством рёбер E
1
, если V
1
состоит из концов рёбер
из E
1
.
Легко убедиться, что бинарное отношение связанности на мно-
жестве вершин графа рефлексивно, симметрично и транзитивно, то
есть, связанность вершин является отношением эквивалентности.
Как известно, всякое отношение эквивалентности разбивает мно-
жество, на котором оно задано, на классы. Классы связанности вер-
шин назовём компонентами графа и тем же термином обозначим
подграфы, порождённые этими классами. Ясно, что компоненты —
это связные графы и что вершины из разных компонент несмежны.
Сколько компонент у графа, изображенного на рис. 1?
Задача 1. Докажите, что связный подграф является компонен-
той тогда и только тогда, когда он не содержится в другом связном
подграфе.
Определение графа не предполагает нумерации его вершин. Но
часто это бывает удобно, поскольку тогда мы можем сопоставить гра-
фу матрицу и использовать для изучения графов матричную алгебру.
Если на множестве V вершин графа с n вершинами задана нумера-
ция, то есть, некоторая биекция σ : V → {1, 2, . . . , n}, то граф на-
зывается нумерованным. Вершины нумерованного графа будем обо-
значать числами 1, 2, . . . , n. Матрицей смежности нумерованного
графа с n вершинами называется матрица A = (a
ij
) порядка n, в
которой
a
ij
=
½
1, если вершины i и j смежны,
0 в противном случае.
Очевидно, матрица смежности симметрична и ее главная диагональ
состоит из нулей. Наоборот, любая симметричная (0,1)-матрица с ну-
левой диагональю определяет нумерованный граф, в котором верши-
ны i и j смежны, если (i, j)-элемент матрицы равен 1. В дальнейшем,
когда речь идёт о матрице смежности графа, то обычно молчаливо
предполагается, что граф нумерован.
6                                     Глава 1. Неориентированные графы


     Говорят, что вершины u и v связаны, если u = v или существует
(u, v)-маршрут. Граф называется связным, если любые две его вер-
шины связаны. Если граф не связен, то он представляет собой объ-
единение нескольких связных подграфов. Чтобы выразиться точнее,
введем понятие подграфа.
     Граф (V1 , E1 ) называется подграфом графа (V, E), если V1 ⊆ V ,
E1 ⊆ E. Например, цепь в графе можно рассматривать как подграф.
Говорят, что подграф порождён подмножеством вершин V1 , если E1
состоит из рёбер, соединяющих вершины из V1 . Говорят, что подграф
порождён подмножеством рёбер E1 , если V1 состоит из концов рёбер
из E1 .
     Легко убедиться, что бинарное отношение связанности на мно-
жестве вершин графа рефлексивно, симметрично и транзитивно, то
есть, связанность вершин является отношением эквивалентности.
     Как известно, всякое отношение эквивалентности разбивает мно-
жество, на котором оно задано, на классы. Классы связанности вер-
шин назовём компонентами графа и тем же термином обозначим
подграфы, порождённые этими классами. Ясно, что компоненты —
это связные графы и что вершины из разных компонент несмежны.
Сколько компонент у графа, изображенного на рис. 1?
   Задача 1. Докажите, что связный подграф является компонен-
той тогда и только тогда, когда он не содержится в другом связном
подграфе.
   Определение графа не предполагает нумерации его вершин. Но
часто это бывает удобно, поскольку тогда мы можем сопоставить гра-
фу матрицу и использовать для изучения графов матричную алгебру.
Если на множестве V вершин графа с n вершинами задана нумера-
ция, то есть, некоторая биекция σ : V → {1, 2, . . . , n}, то граф на-
зывается нумерованным. Вершины нумерованного графа будем обо-
значать числами 1, 2, . . . , n. Матрицей смежности нумерованного
графа с n вершинами называется матрица A = (aij ) порядка n, в
которой             ½
                      1, если вершины i и j смежны,
              aij =
                      0 в противном случае.
Очевидно, матрица смежности симметрична и ее главная диагональ
состоит из нулей. Наоборот, любая симметричная (0,1)-матрица с ну-
левой диагональю определяет нумерованный граф, в котором верши-
ны i и j смежны, если (i, j)-элемент матрицы равен 1. В дальнейшем,
когда речь идёт о матрице смежности графа, то обычно молчаливо
предполагается, что граф нумерован.

Страницы