ВУЗ:
Составители:
Рубрика:
14
Расстоянием
),( yxd
между вершинами
x
и
y
в
неориентированном графе
G называется наименьшее число
ребер, соединяющих эти вершины.
Условный радиус графа
G
относительно вершины
c определяется формулой:
),(max)(
)(
xcdcr
GVx∈
= .
Здесь
)(GV
– это множество вершин графа G .
Радиус графа G определяется как наименьший из
условных радиусов графа, а
центр графа составляют вершины,
условные радиусы графа относительно которых совпадают с
радиусом графа.
Для данного графа таблица расстояний и условных
радиусов вершин имеет вид:
1
x
2
x
3
x
4
x
5
x
6
x
7
x )(
i
xr
1
x
0 1 2 1 1 2 3 3
2
x
1 0 1 1 2 2 2 2
3
x
2 1 0 1 3 2 1 3
4
x
1 1 1 0 2 1 2 2
5
x
1 2 3 2 0 1 2 3
6
x
2 2 2 1 1 0 1 2
7
x
3 2 1 2 2 1 0 3
Радиус графа G 2)(
=
Gr , следовательно, центр графа –
это множество вершин
{
}
642
,, xxx .
5. Элементы теории алгоритмов.
Алгоритмы. Требования к алгоритмам. Модели алгорит-
мов. Машина Тьюринга. Рекурсивные функции. Вычислимость
и разрешимость.
Литература: [2], гл. 5.
Расстоянием d ( x, y ) между вершинами x и y в
неориентированном графе G называется наименьшее число
ребер, соединяющих эти вершины. Условный радиус графа G
относительно вершины c определяется формулой:
r (c) = max d (c, x) .
x∈V ( G )
Здесь V (G ) – это множество вершин графа G .
Радиус графа G определяется как наименьший из
условных радиусов графа, а центр графа составляют вершины,
условные радиусы графа относительно которых совпадают с
радиусом графа.
Для данного графа таблица расстояний и условных
радиусов вершин имеет вид:
x1 x2 x3 x4 x5 x6 x7 r ( xi )
x1 0 1 2 1 1 2 3 3
x2 1 0 1 1 2 2 2 2
x3 2 1 0 1 3 2 1 3
x4 1 1 1 0 2 1 2 2
x5 1 2 3 2 0 1 2 3
x6 2 2 2 1 1 0 1 2
x7 3 2 1 2 2 1 0 3
Радиус графа G r (G ) = 2 , следовательно, центр графа –
это множество вершин {x 2 , x 4 , x6 } .
5. Элементы теории алгоритмов.
Алгоритмы. Требования к алгоритмам. Модели алгорит-
мов. Машина Тьюринга. Рекурсивные функции. Вычислимость
и разрешимость.
Литература: [2], гл. 5.
14
