Основные понятия теории графов. Гладких О.Б - 29 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

148
6. Применение теории графов
6.1. Графы и информация
Двоичные деревья играют весьма важную
роль в теории информации. Предположим, что оп-
ределенное число сообщений требуется закодиро-
вать в виде конечных последовательностей раз-
личной длины, состоящих из нулей и единиц. Если
вероятности кодовых слов заданы, то наилучшим
считается код, в котором средняя длина слов ми-
нимальна по сравнению с прочими распределе
-
ниями вероятности. Задачу о построении такого
оптимального кода позволяет решить алгоритм
Хаффмана.
Двоичные кодовые деревья допускают ин-
терпретацию в рамках теории поиска. Каждой
вершине при этом сопоставляется вопрос, ответить
на который можно либо «да», либо «нет». Утвер-
дительному и отрицательному ответу соответст-
вуют два ребра, выходящие из вершины. «Опрос»
завершается,
когда удается установить то, что тре-
бовалось.
Таким образом, если кому-то понадобится
взять интервью у различных людей, и ответ на
очередной вопрос будет зависеть от заранее неиз-
вестного ответа на предыдущий вопрос, то план
такого интервью можно представить в виде двоич-
ного дерева.
29
Матрица сильной связности этого графа
имеет вид:
S =
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
0 0 0 1 0
1 1 1 0 1
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
Мы видим, что 1 – ая, 2 – ая, 3 – ая и 5 – ая строки
матрицы S одинаковы.
7B1.7. Пути во взвешенных ориентированных
графах
Определение 1.34. Ориентированный граф назы-
вается нагруженным,
если дугам этого графа по-
ставлены в соответствие веса, так что дуге (x
i
, x
j
)
сопоставлено некоторое число c(x
i
, x
j
) = c
ij
, назы-
ваемое длиной
(или весом, или стоимостью) дуги.
Определение 1.35. Длиной (или весом или стои-
мостью) пути s, состоящего из некоторой после-
довательности дуг (x
i
, x
j
), называется число l (s),
равное сумме длин дуг, входящих в этот путь, т.е.
l (s) =
∑
c
ij
,
причем суммирование ведется по всем дугам
(x
i
,.x
j
)
∈
s. Матрица C = (c
ij
) называется матрицей
длин дуг или матрицей весов. 
         6. Применение теории графов                      Матрица сильной связности этого графа
                                                     имеет вид:
            6.1. Графы и информация                                     ⎛1   1 1 0 1⎞
                                                                        ⎜1   1 1 0 1⎟⎟
      Двоичные деревья играют весьма важную
                                                                     S= ⎜
роль в теории информации. Предположим, что оп-                          ⎜1   1 1 0 1⎟
                                                                        ⎜            ⎟
ределенное число сообщений требуется закодиро-                          ⎜0   0 0 1 0⎟
вать в виде конечных последовательностей раз-                           ⎜1   1 1 0 1⎟⎠
                                                                        ⎝
личной длины, состоящих из нулей и единиц. Если
вероятности кодовых слов заданы, то наилучшим        Мы видим, что 1 – ая, 2 – ая, 3 – ая и 5 – ая строки
считается код, в котором средняя длина слов ми-      матрицы S одинаковы.
нимальна по сравнению с прочими распределе-
                                                       1.7. Пути во взвешенных ориентированных
ниями вероятности. Задачу о построении такого
                                                       7B




                                                                          графах
оптимального кода позволяет решить алгоритм
Хаффмана.                                            Определение 1.34. Ориентированный граф назы-
      Двоичные кодовые деревья допускают ин-         вается нагруженным, если дугам этого графа по-
терпретацию в рамках теории поиска. Каждой           ставлены в соответствие веса, так что дуге (xi, xj)
вершине при этом сопоставляется вопрос, ответить     сопоставлено некоторое число c(xi, xj) = cij, назы-
на который можно либо «да», либо «нет». Утвер-       ваемое длиной (или весом, или стоимостью) дуги.
дительному и отрицательному ответу соответст-        Определение 1.35. Длиной (или весом или стои-
вуют два ребра, выходящие из вершины. «Опрос»        мостью) пути s, состоящего из некоторой после-
завершается, когда удается установить то, что тре-   довательности дуг (xi, xj), называется число l (s),
бовалось.                                            равное сумме длин дуг, входящих в этот путь, т.е.
      Таким образом, если кому-то понадобится
взять интервью у различных людей, и ответ на
                                                                        l (s) =   ∑   cij,
очередной вопрос будет зависеть от заранее неиз-     причем суммирование ведется по всем дугам
вестного ответа на предыдущий вопрос, то план        (xi,.xj) ∈ s. Матрица C = (cij) называется матрицей
такого интервью можно представить в виде двоич-      длин дуг или матрицей весов.
ного дерева.

                          148                                                     29

Страницы