Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 1.97 Mb.
|
| Тема 7.6 Плоские графы. Граф называется плоским, если никакие два его соседних ребра не имеют других общих точек за исключением их общей вершины. Рисунок графа называется его плоским представлением, если на нем никакие два ребра не имеют общих точек пересечения, если не считать точкой пересечения их вершину. Теорема: Для того, чтобы граф являлся плоским необходимо и достаточно ,чтобы существовало его плоское представление. В качестве характеристики плоского графа вводят понятие грань. Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не имеющая внутри себя других циклов. Грани: (2,4,5,6,2) (1,2,3,1) (1,7,4,1) (1,4,2,3,1) Границей грани называется простой цикл, ограничивающий грань. Две грани называются соседними, если их границы имеют хотя бы одно общее ребро. Существует так называемая бесконечная грань, т.е. часть плоскости, лежащая вне графа и ограниченная изнутри простым циклом АВ называют перегородкой, и если у графа есть перегородка, то не существует бесконечной грани. Теорема: Если в плоском представлении графа без перегородок V – количество вершин, P – количество ребер, G – количество граней (с учетом бесконечной), то V – P + G = 2 (формула Эйлера). Данная теорема используется в задачах для того, чтобы доказать, что заданный граф не является плоским. Тема 7.7 Деревья. Код Пруфера. Деревом называется всякий несвязный граф без циклов. Граф, состоящий из изолированной вершины, тоже считается деревом. Вершина дерева, степень которой равна 1, называется висячей. Лесом называется граф представленный в виде объединения деревьев. Теорема: Если у дерева n вершин, то ребер n-1. Рассмотрим произвольное дерево с 11 вершинами, пронумерованными в произвольном порядке. В результате возникает вопрос: сколько существует таких деревьев с 11 вершинами? Английский математик Кэли нашел ответ на этот вопрос: деревьев с n вершинами можно создать столько, сколько существует последовательностей вида:  , где и таких последовательностей будет nn-2.Немецкий математик Пруффер продолжил решать эту проблему и указал алгоритм, согласно которому любому дереву можно поставить во взаимно-однозначное соответствие – код. Алгоритм:
1. вершина № 2 2. записываем вершину № 1 3. выбираем вершину № 3 4. записываем вершину № 1 и т.д., в результате получаем код: (1, 1, 5, 5, 6, 6, 6, 6, 5) И наоборот, зная код можно изобразить дерево. Алгоритм составления дерева по коду:
Дан код (1, 5, 5, 3, 6, 4). Количество вершин = 8,
Тема 7.8 Понятие ориентированный граф (орграф). Ребро <А,В> называется ориентированным, если одну вершину считают его началом, вторую концом <А,В> <В,А> Граф называется ориентированным, если каждое его ребро ориентировано. Степенью входа вершины А называется количество ребер входящих в А. Степенью выхода вершины А называется количество ребер выходящих из нее. Рассмотрим
степень входа – 1, степень выхода – 1;
степень входа – 3, степень выхода – 0;
степень входа – 0, степень выхода – 2. Стоком называется вершина, степень выхода которой равна 0, а степен7ь входа больше 0. Источником называется вершина, степень выхода которой больше 0, а степень входа равна 0. Изолированной вершиной называется вершина, у которой степень входа и степень выхода равны 0. Путем от вершины А1 до вершины Аn называется такая последовательность ребер, ведущих от А1 до Аn Расстоянием от вершины А до вершины В называется длина наименьшего пути. Если пути от вершины А до вершины В не существует, то расстояние считают равным бесконечности. S(A,B)=1 S(A,C)=2 S(C,A)=∞ Теорема: Если в графе m вершин, р – ребер, то степень входа А1+ степень входа А2+…+ степень входа Am = степень выхода А1+ степень выхода А2+…+ степень выхода Am = р Тема 7.9 Достижимость вершин в орграфе. Вершина А достижима из вершины В, если существует путь от В до А. Для ориентированного графа Г вводят матрицу достижимости, следующего вида: где , если вершина достижима из вершины и , если не достижима.Считается, что вершина достижима сама из себя, т.е. элементы главной диагонали матрицы достижимости равны 1. Раздел 8. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ. Тема 8.1 Определение класса финитно-поставленных задач. Класс однотипных задач называется классом финитно-поставленных задач, если существует конечный алфавит А, словами которого можно закодировать условие и ответ любой задачи этого класса. Класс финитно-поставленных задач можно свести к задаче вычисления значений некоторой функции на множестве N. Пусть f(n) определена на N, закодируем все слова с помощью конечного алфавита А={а1, …аn} следующим образом: берем каждый символ и ставим ему в соответствие его порядковый номер. , тогда если - слова, тогде р – все простые числа При этом натуральное число является кодом, если оно делиться на все простые числа, начиная с 2 и заканчивая этим числом. Тогда если к – некоторый класс финитно-поставленных задач и существуют конечные алфавиты, словами которого можно закодировать условие и ответ, то задача сводиться к определению кода на множестве N. Общий метод решения задач в данном случае имеет вид: Задача → кодируем условие на N( )→ вычисляем ()→ декодируем ответ.Функция - называется кодовой.Тема 8.2 Машины Тьюринга. Будем считать, что машина Тьюринга имеет ленту (магнитную, печатную и т.д.), которая бесконечна в обе стороны и разбита на участки называемые ячейками. Имеется считывающее устройство и существует механизм, который передвигает это устройство, как вправо, так и влево. Дан конечный алфавит А, следующего вида: , где - пустой знакВ каждую ячейку машина может печатать только один знак. Алфавит А называется внешним алфавитом машины. Считаем, что машина может находиться в одном из конечного числа состояний: . Состояние Q – называется внутренним алфавитом машины, где - пассивное состояние машины, а все остальные состояния называются активными состояниями машины.В каждый момент времени t считывающее устройство видит только одну ячейку и при этом на ленте конечное число знаков (не пустых символов). Если в момент времени t машина находиться в состоянии и обозревает ячейку , то называется локальной информацией машины.Участок между непустыми символами - называется глобальной информацией машины.Машина делает 4 операции:
Работа машины заключается в следующей последовательности шагов:
Выполнение этих шагов осуществляется под действием команды (приказы), которые зависят от настоящей ситуации. Множество приказов обозначается: и называется программой машины.Тема 8.3 Уточнения понятия алгоритм. Существует четыре уточнения понятия алгоритм (тезисы):
, где , все рi, ai – слова в алфавите А, А – конечный алфавит.Схема работает следующим образом: пусть - это слово из алфавита А, тогда отыскиваем сверху первую строку, левая часть которой входит по крайней мере 1 раз в слово :Заменяем самое левое вхождение рi в слове самым правым вхождением ai. Если ни одно рi не входит в слово , то будем считать, что алгоритм не применим к этому слову.Заменив рi на ai, получим новое слово и повторим процесс. Процесс заканчивается на том шаге, когда .
Итоговая (выходная) контрольная работа. Вариант 1
2. Даны множества М=[2,8] N[4,10]. Найти множество N\M.
а) ¬ ¬ x ≈ x б) x ∧ (x ∨ z)≈ (x ∧ y)∨ (x ∧ z)
|
