Размещено на http://www.allbest.ru/

КОНТРОЛЬНАЯ РАБОТА

на тему: «Применение графов к решению задач»

Задача № 1

Для графов G₁ и G₂ (рис. 2.1) построить графы G₁G₂, G₁G₂, G₁(G₂), G₂(G₁), матрицы смежности вершин А(G₁), А(G₂) и матрицы инцидентности В(G₁), В(G₂), введя предварительно нумерацию дуг. По матрицам смежности вершин исходных графов построить матрицы смежности вершин А(G₁G₂), А(G₁G₂), А(G₁(G₂)), А(G₂(G₁)). Будут ли изоморфны графы G₁(G₂) и G₂(G₁)?

матрица граф множество

Решение.

Построим графы

Матрицы смежности вершин А(G₁), А(G₂)

Матрицы инцидентности В(G₁), В(G₂).

Найдем А(G₁)+ А(G₂)

Найдем А(G₁)*А(G₂)

Найдем А(G₁(G₂))

Найдем А(G₂(G₁))

Графы G₁(G₂) и G₂(G₁) не изоморфны.

Задача № 2

При условии, что петля считается двойным ребром, для графов G₁ и G₂ (рис. 2.2) построить матрицы смежности вершин А(G₁) и А(G₂), введя предварительно нумерацию рёбер, построить матрицы инцидентности В(G₁) и В(G₂). По матрицам смежности вершин исходных графов построить матрицы смежности вершин А(G₁G₂) и А(G₁G₂).

Решение.

Матрицы смежности вершин А(G₁), А(G₂)

Найдем матрицы смежности вершин А(G₁G₂) и А(G₁G₂)

Задача № 3

Построить код (G) по дереву G (рис. 20.3) и восстановить G.

Рис. 20.3

Задача № 4

По алгоритму Краскала построить для нагруженного графа G, изображенного на рис. 20.4, минимальный каркас G₁ с указанием последовательности выбора рёбер e_i. Определить вес построенного каркаса (G₁).

Решение.

Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его основным лесом минимального веса.

Вес каркаса: 1+2+2+3+3+3+3+4+4+4+5=34.

Задача № 5.

В графе G, изображённом на рис. 2.5, найти все минимальные внешне устойчивые множества вершин, наименьшие доминирующие множества и число внешней устойчивости (G).

Рис. 20.5

Решение.

Данный граф имеет единственное минимальное внешне устойчивое множество {v2, v4}. Данное множество является наименьшим. Число внешней устойчивости (G) = 2.

Задача № 6

Построить максимальный поток и разрез с минимальной пропускной способностью в транспортной сети, приведённой на рис. 20.6, по алгоритму Форда-Фалкерсона.

Рис. 20.6

Решение.

Выбираем полные пути из истока s в сток t по ненасыщенным ребрам.

m1:sct.

Пропускная способность пути (минимальная из пропускных способностей ребер): R(m1)=min{4,3; 5,3}=4,3. Насыщается ребро (s, c).

m2:sbdt.

R(m2)=min{6,3; 4,3; 6,4}=4,3. Насыщается ребро (b, d).

m3:sbadt. R(m3)=min{2,0; 4,2; 3,1; 2,1}=2,0.Насыщается ребро (s, b).

m4:saet. R(m4)=min{5,2; 5,3; 4,1}=4,1. Насыщается ребро (e, t).

m5:sadt. R(m5)=min{1,1; 1,1; 0,1}=0,1. Насыщается ребро (d, t).

m6:sfdt. R(m6)=min{1,9; 1,1; 2,1}=1,1. Насыщается ребро (f, d).

m7:saect. R(m7)=min{1,0; 1,2; 3,0; 1,0}=1,0. Насыщается ребра (s, a), (c, t).

Разрез с минимальной пропускной способностью образуют ребра: (s, a), (a, b), (s, c). Или же, разрез с минимальной пропускной способностью образуют ребра: (c, t), (d, t), (e, t).

Максимальная пропускная способность сети: 5,2+6,3+4,3=15,8 ед.,

или 6,4+5,3+4,1=15,8 ед.

Задача № 7

Доказать справедливость тождества для произвольных множеств А, B, C и D:

Решение.

= = =

=

Справедливо.

Задача № 8.

Доказать, что множества Х и Y равномощны, построив взаимно-однозначное соответствие между ними.

Х=(-6,11), Y=[-3,2].

Решение.

Взаимно однозначное соответствие между ними устанавливает формула:

у =

Задача № 9

Даны три вещественных функции:

f(x)=3x¹³+27, g(x)=2arccos(5x), h(x)=log₅(2x+7)-10.

1) Найти заданные композиции функций: hgf, hfh, hfg.

2) Являются ли f, g, h инъекциями, сюръекциями, биекциями на R?

3) Найти обратные функции к f, g, h. Если функции со своими областями определения обратных не имеют, то найти обратные функции к их сужениям.

Решение.

1) Найти заданные композиции функций: fgh, hgf, ffh.

hgf= log₅(2 (2arccos(5 (3x¹³+27)))+7)-10;

hfh= log₅(2 (3 (log₅(2x+7)-10)¹³+27)+7)-10;

hfg= log₅(2(3(2arccos(5x))¹³+27)+7)-10.

2) Являются ли f, g, h инъекциями, сюръекциями, биекциями на R?

f(x)= 3x¹³+27 - биекция (взаимно однозначное отображение)

h(x)= 2arccos(5x) - сюръекция.

g(x)= log₅(2x+7)-10 - инъекция.

3) Найти обратные функции к f, g, h. Если функции со своими областями определения обратных не имеют, то найти обратные функции к их сужениям.

f(x)= 3x¹³+27: обратная f^-1(x) = .

h(x)= log₅(2x+7)-10: .

g(x)= 2arccos(5x): обратная g^-1(x) = .

Задача № 10

Является ли несимметричной композиция бинарных отношений R₁ и R₂, если отношения R₁ и R₂ несимметричны? В случае отрицательного ответа необходимо привести конкретный пример

Решение.

Поскольку бинарные отношения R₁ и R₂ несимметричны, то каждое из них задается ориентированным графом с петлями. Находя композицию бинарных отношений R₁ и R₂, получим ориентированный граф с петлями. Следовательно, композиция бинарных отношений R₁ и R₂ будет несимметричным.

Размещено на Allbest.ru