Контрольная работа по "Высшей математике"

Л а б о р а т о р н а я р а б о т а № 1

Задание №1

Условие:

Теоретическое решение:

1)определим расстояние между всеми парами вершин

d(x1,x2) = 1

d(x1,x3) = 2 d(x2,x3) = 1

d(x1,x4) = 1 d(x2,x4) = 1 d(x3,x4) = 2

d(x1,x5) = 2 d(x2,x5) = 1 d(x3,x5) = 1 d(x4,x5) = 2

d(x1,x6) = 2 d(x2,x6) = 2 d(x3,x6) = 3 d(x4,x6) = 1 d(x5,x6) = 2

d(x1,x7) = 2 d(x2,x7) = 2 d(x3,x7) = 2 d(x4,x7) = 1 d(x5,x7) = 1 d(x6,x7) = 1

d(x1,x8) = 3 d(x2,x8) = 2 d(x3,x8) = 2 d(x4,x8) = 2 d(x5,x8) = 1 d(x6,x8) = 2 d(x7,x8) = 1;

2)определим диаметр как d(G) = max d(xi,xj): d(G) = 3;

3)определим эксцентриситет каждой вершины:

r(x1) = 3; r(x2) = 2; r(x3) = 3; r(x4) = 2; r(x5) = 2; r(x6) = 3; r(x7) = 2; r(x8) = 3;

4)определим радиус графа как r(G) = min r(xi): r(G) = 2;

5)определим центральные вершины: {x2, x4, x5, x7};

6)построим матрицу смежности.

x1 x2 x3 x4 x5 x6 x7 x8

x1 0 1 0 1 0 0 0 0

x2 1 0 1 1 1 0 0 0

x3 0 1 0 0 1 0 0 0

x4 1 1 0 0 0 1 1 0

x5 0 1 1 0 0 0 1 1

x6 0 0 0 1 0 0 1 0

x7 0 0 0 1 1 1 0 1

x8 0 0 0 0 1 0 1 0

Решение, полученное на ЭВМ (Centre.exe):

Вывод: данные, полученные двумя способами, идентичны.

Задание №2

Условие:

Теоретическое решение:

1)вершинная раскраска графа

χ(G) = 3

Цветные классы: X = (X1 or X2 or X3)

X1 = {x1, x5, x9}

X2 = {x2, x6, x7}

X3 = {x3, x4, x8}

2)рёберная раскраска графа

Вершина x5 имеет степень 6, то есть Pmax(X) = 6. Следовательно, для правильной раскраски рёбер данного графа потребуется шесть цветов.

Цветные классы: V = (V1 or V2 or V3 or V4 or V5 or V6)

V1 = {(x1, x2), (x4, x5), (x8, x9)}

V2 = {(x2, x3), (x1, x4), (x5, x7), (x6, x9)}

V3 = {(x2, x4), (x3, x5), (x6, x8)}

V4 = {(x2, x5), (x4, x7)}

V5 = {(x5, x6)}

V6 = {(x5, x8)}

Задание №3

Условие:

Теоретическое решение:

Выберем