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

UptoLike

ВУЗ: 

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

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

Рубрика: 

152
времени каждая бактерия либо делится на две но-
вые, либо погибает. Тогда для потомства одной
бактерии мы получим двоичное дерево.
Нас будет интересовать лишь один вопрос: в
скольких случаях n-е поколение одной бактерии
насчитывает ровно k потомков? Рекуррентное со-
отношение, обозначающее число необходимых
случаев, известно в биологии под названием про
-
цесса Гальтона-Ватсона. Его можно рассматривать
как частный случай многих общих формул.
6.4. Графы и физика
Еще недавно одной из наиболее сложных и
утомительных задач для радиолюбителей было
конструирование печатных схем.
Печатной схемой называют пластинку из ка-
кого-либо диэлектрика (изолирующего материала),
на которой в виде металлических полосок вытрав-
лены дорожки. Пересекаться дорожки могут толь-
ко в определенных точках, куда устанавливаются
необходимые элементы (диоды, триоды, резисто-
ры
и другие), их пересечение в других местах вы-
зовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вы-
чертить плоский граф, с вершинами в указанных
точках.
6.5. Графы и экономика
25
(x
2
,x
5
,x
6
,x
7
,x
2
) – простой элементарный контур, т.к.
это замкнутый путь, в котором все ду-
ги и вершины, кроме первой и по-
следней, различны.
Рис. 10.
6B1.6. Связность графа
Определение 1.28. Неориентированный граф на-
зывается связным, если каждая пара различных
вершин может быть соединена, по крайней мере,
одной цепью.
Определение 1.29. Ориентированный граф назы-
вается сильно связным, если для любых двух его
вершин x
i
и x
j
существует хотя бы один путь, со-
единяющий x
i
с x
j
.
Определение 1.30. Ориентированный граф назы-
вается односторонне связным, если для любых
двух его вершин, по крайней мере, одна достижи-
ма из другой.
x
1
x
2
x
4
x
7
x
5
x
3
x
6 
времени каждая бактерия либо делится на две но-    (x2,x5,x6,x7,x2) – простой элементарный контур, т.к.
вые, либо погибает. Тогда для потомства одной                      это замкнутый путь, в котором все ду-
бактерии мы получим двоичное дерево.                               ги и вершины, кроме первой и по-
      Нас будет интересовать лишь один вопрос: в                   следней, различны.
скольких случаях n-е поколение одной бактерии                          x2                    x4
насчитывает ровно k потомков? Рекуррентное со-
отношение, обозначающее число необходимых
случаев, известно в биологии под названием про-              x1                                  x5   x7
цесса Гальтона-Ватсона. Его можно рассматривать
как частный случай многих общих формул.                                     x3
                 6.4. Графы и физика
      Еще недавно одной из наиболее сложных и                                               x6
                                                                                 Рис. 10.
утомительных задач для радиолюбителей было
конструирование печатных схем.                                    1.6. Связность графа
                                                                  6B




      Печатной схемой называют пластинку из ка-
                                                   Определение 1.28. Неориентированный граф на-
кого-либо диэлектрика (изолирующего материала),
                                                   зывается связным, если каждая пара различных
на которой в виде металлических полосок вытрав-
                                                   вершин может быть соединена, по крайней мере,
лены дорожки. Пересекаться дорожки могут толь-
                                                   одной цепью.
ко в определенных точках, куда устанавливаются
                                                   Определение 1.29. Ориентированный граф назы-
необходимые элементы (диоды, триоды, резисто-
                                                   вается сильно связным, если для любых двух его
ры и другие), их пересечение в других местах вы-
                                                   вершин xi и xj существует хотя бы один путь, со-
зовет замыкание электрической цепи.
                                                   единяющий xi с xj.
      В ходе решения этой задачи необходимо вы-
                                                   Определение 1.30. Ориентированный граф назы-
чертить плоский граф, с вершинами в указанных
                                                   вается односторонне связным, если для любых
точках.
                                                   двух его вершин, по крайней мере, одна достижи-
               6.5. Графы и экономика              ма из другой.



                         152                                                           25

Страницы