Построить все неизоморфные простые несвязные графы с 5 вершинами и 2 компонентами связности

  • ID: 19183 
  • 3 страницы

Фрагмент работы:

1. Построить все неизоморфные простые несвязные графы с 5 вершинами и 2 компонентами связности.

РЕШЕНИЕ:

2.Какие из трех указанных графов являются изоморфными, а какие – не изоморфными? Для изоморфных графов указать соответствие вершин, сохраняющее смежность. Для неизоморфных пояснить причину этого.

РЕШЕНИЕ:

1-й и 3-й графы изоморфны, т.к. Назвав вершины:

1

2

3

4

5

A

B

C

D

E

мы видим, что установив соответствие 1®B, 2®E, 3®A, 4®C, 5®D получим изоморфизм, т.к. при этом сопоставлении сохраняются рёбра.

Второй граф не может быть изоморфен первому, т.к. у него есть вершина степени 4, а у первого графа таких вершин нет. Следовательно неизоморфен и третьему (по транзитивности изоморфизма).

3. Для указанного ниже графа построить его дополнение, реберный граф и геометрически двойственный граф.

РЕШЕНИЕ:

Дополнение графа: Рёберный граф:

Геометрически двойственный граф:

5. Найти коэффициент при [image] в разложении [image].

РЕШЕНИЕ:

[image]=[image]=[image]

Коэффициент равен нулю, т.к. сумма степеней 4+5=9 – не может быть получена при возведении степени [image], т.е. суммарная степень не может быть больше 8.

6. Найти число целых положительных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел: 7, 8, 14.

РЕШЕНИЕ:

Найдём, сколько чисел делится на 7: a7 = 142. ( [1000/7] )

Делится на 8: a8 = 125.

Делится на 14: a14 = 71.

Делится и на 7 и на 8: a[7,8]=17.

Делится на 7 и 14: a[7,14]=71.

Делится на 8 и 14: a[8,14]=17.

Делится на 7, 8 и 14: a[7,8,14]=17.

Итого целых положительных чисел делящихся на 7, или на 14 или на 8:

s=a7+a8+a14-a[7,8]-a[7,14]-a[8,14]+a[7,14,8] =142+125-17=250.

Тогда остальные числа = 750.

Ответ: 750.

7. Найти решение рекуррентного соотношения.

[image], [image], [image].

РЕШЕНИЕ:

составим характеристическое уравнение:

l2+6l+9=0, l1= – 3.

Общее решение: [image]

6 = – 3(c1+с2); c1+с2= – 2.