Математический аппарат инженера
Шрифт:
9. Постройте графы, соответствующие следующим матрицам смежности:
– 59 -
Охарактеризуйте полученные графы и запишите для них матрицы инцидентности.
10. Расположите на плоскости четыре вершины, как в графе на рис. 11, а, но обозначения вершин v2 и v3
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) как блоки, постройте соответствующий сепарабельный граф. Сколько возможно различных вариантов (без учета изолированной вершины G2)?
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 -
Главная цель применения в логике математической символики заключалась в том, чтобы свести операции с логическими заключениями к формальным действиям над символами. При этом исходные положения записываются формулами, которые преобразуются по определенным законам, а полученные результаты истолковываются в соответствующих понятиях.
Бурное развитие математической логики связано, прежде всего, с задачами обоснования математики, где она используется для доказательства непротиворечивости исходных понятий и правильности рассуждении и выводов математических теорий. Некоторые ученые даже склонны рассматривать логику как одну из наиболее общих наук, частью которой является сама математика.
В последние десятилетия логика находит все более широкое применение в технике при исследовании и разработке релейно-контактных схем, вычислительных машин, дискретных автоматов. Ее методы используются в теории преобразования и передачи информации, теории вероятностей и комбинаторном анализе. Математическая логика начинает внедряться в такие нематематические области, как экономика, биология, медицина, психология, языкознание, право. Интенсивно развиваются специальные разделы математической логики, призванные обслуживать конкретные области науки и техники.