Читать «Математический аппарат инженера» онлайн - страница 38

16. Постройте блоки, на которые разбивается сепарабельный граф (см. рис. 14, а).

17. Постройте все различные деревья с восьмью вершинами (их должно быть 23).

18. Постройте все покрывающие деверья и их дополнения для графа (см. рис. 11, а). Сколько имеется существенно различных деревьев?

19. Постройте покрывающий лес несвязанного графа (см. рис. 13).

20. Постройте все прадеревья оргарфа (см. рис. 8, а) с корнем в вершине d.

21. Рассматривая компоненты несвязанного графа (см. рис. 13) как блоки, постройте соответствующий сепарабельный граф. Сколько возможно различных вариантов (без учета изолированной вершины G₂)?

22. Покажите, что приведенные на рис. 21 графы неплоские. Какое минимальное число ребер необходимо удалить из графа на рис. 21, а, чтобы он превратился в плоский? Сколько имеется различных способов такого превращения с точностью до изоморфизма?

23. Покажите, что графы на рис. 21, а и в гомеоморфные.

- 60 -

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

25. Докажите, что (p, p — k) — граф при k ≥ 2 всегда является несвязным и состоит не менее, чем из k компонент.

26. Изобразите все неизоморфные простые графы с пятью вершинами (изолированные вершины допускаются), содержащие три, пять восемь, девять и десять дуг (всего их должно быть 14).

27. Покажите, что число ребер полного графа равно 1/2 p(p — 1), где p — число его вершин.

28. Найдите общее выражение для числа ребер, при котором граф с p вершинами может быть несвязным.

29. Покажите, что любое дерево можно представить как двухдольный граф. Какие деревья являются полными двудольными графами?

Рис. 21. Неплоские графы.

30. Докажите: а) кубический граф имеет точку сочленения тогда и только тогда, когда он содержит мост; б) наименьшее число вершин в кубическом графе, имеющем мост, равно 10.

31. Постройте граф, изоморфный графу Понтрягина-Куратовского (см. рис. 19, б), в котором внешние ребра образуют шестиугольник. Рассматривая его как подграф полного шестиугольника, нарисуйте дополнение этого подграфа. Укажите характерные свойства полученного дополнения.

32. Покажите, что следующие свойства дерева Т равносильны:

а) Т связно и не содержит циклов;

б) Т не содержит циклов и имеет p — 1 ребер, где p — число вершин;

в) Т связно и имеет p — 1 ребер;

г) Т не содержит циклов, но добавление ребра между любыми двумя несмежными вершинами приводит к появлению цикла;

д) Т связно, но утрачивает это свойство при удалении любого ребра;

е) всякая пара вершин в Т соединена цепью и притом только одной.

5. Логика

1. Чем занимается математическая логика? Логика как искусство рассуждении зародилась в глубокой древности. Начало науки о законах и формах мышления связывают с именем Аристотеля. Прошло два тысячелетия, прежде чем Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею последовательно реализовал в прошлом столетии Джордж Буль и тем самым заложил основы математической (символической) логики.