Математический аппарат инженера - [22]
11. Выполните следующие упражнения с графом (см. рис. 11, а):
а) Найдите все ориентированные маршруты от вершины а к вершине е.
б) Найдите все пути и простые пути от вершины а к вершине е.
в) Определите все простые контуры графа.
13. В орграфе (см. рис. 8, а) измените направления дуг таким образом, чтобы он преобразовался в ациклический граф. Постарайтесь найти общее правило такого преобразования.
14. Для графа (см. рис. 12) простойте:
а) часть, состоящую из четырех вершин и пяти ребер;
б) суграф с четырьмя, пятью и шестью ребрами.
15. Два графа G' = (V', E') и G" = (V", E") называются непересекающимися, если V' ∩ V" = ∅ и E' ∩ E" = ∅. Постройте непересекающиеся подграфы графа рис. 12, содержащие по три вершины.
16. Постройте блоки, на которые разбивается сепарабельный граф (см. рис. 14, а).
17. Постройте все различные деревья с восьмью вершинами (их должно быть 23).
18. Постройте все покрывающие деверья и их дополнения для графа (см. рис. 11, а). Сколько имеется существенно различных деревьев?
19. Постройте покрывающий лес несвязанного графа (см. рис. 13).
20. Постройте все прадеревья оргарфа (см. рис. 8, а) с корнем в вершине d.
21. Рассматривая компоненты несвязанного графа (см. рис. 13) как блоки, постройте соответствующий сепарабельный граф. Сколько возможно различных вариантов (без учета изолированной вершины G>2)?
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. Чем занимается математическая логика? Логика как искусство рассуждении зародилась в глубокой древности. Начало науки о законах и формах мышления связывают с именем Аристотеля. Прошло два тысячелетия, прежде чем Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею последовательно реализовал в прошлом столетии Джордж Буль и тем самым заложил основы математической (символической) логики.
- 61 -
Главная цель применения в логике математической символики заключалась в том, чтобы свести операции с логическими заключениями к формальным действиям над символами. При этом исходные положения записываются формулами, которые преобразуются по определенным законам, а полученные результаты истолковываются в соответствующих понятиях.
Бурное развитие математической логики связано, прежде всего, с задачами обоснования математики, где она используется для доказательства непротиворечивости исходных понятий и правильности рассуждении и выводов математических теорий. Некоторые ученые даже склонны рассматривать логику как одну из наиболее общих наук, частью которой является сама математика.
В последние десятилетия логика находит все более широкое применение в технике при исследовании и разработке релейно-контактных схем, вычислительных машин, дискретных автоматов. Ее методы используются в теории преобразования и передачи информации, теории вероятностей и комбинаторном анализе. Математическая логика начинает внедряться в такие нематематические области, как экономика, биология, медицина, психология, языкознание, право. Интенсивно развиваются специальные разделы математической логики, призванные обслуживать конкретные области науки и техники.
