Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 41
Текст из файла (страница 41)
Может ли хотя бы одна из этих функций зависеть существенно только от одной переменной? 2) У всюду определенной функции Дх, д) ровно одна существенная переменная. Могут ли у функции д,у(х, д) быть существенными обе переменные, если предположить дополнительно, что она всюду определена? 2.10.
Обосновать вычислимость следующих функций: 1) е( ) ~ ] ( . зб(2х, )),( + 1)з. 2) Дх, д, х) = ( — '+ 2~ ?~~) ((хз — ' д) + х)); 3) ?(х, д, х) = 4л " ' — (хз+ 1)з. (зб(х — ' 2У) + я); з з 4) ((х, д, х) = У 2се т"Р-Я~х хт1 2.11. Каковы мощности классов К„р, К,р, К„„и К,? 2. Некоторые специальные свойства рекурсивных функций. 2.12. Опровергнуть следующее утверждение: если машина Тьюринга вычисляет функцию ~з(х) Е К„р~К„р, то вычислимая на этой машине функция ?з(х, д) не является примитивно рекурсивной.
2.13. 1) Машины Тьюринга Т, и Тз вычисляют примитивно рекурсивные функции ~х(х) и ?з(х) соответственно. Следует ли отсюда, что композиция ТзТя этих машин вычисляет обязательно примитивно рекурсивную функцию? А если машины Тз и Тз правильно вычисляют функции?з и ?з? 2) Машина Тьюринга Т вычисляет примитивно рекурсивную функцию )(х). Справедливо ли следующее утверждение: если итерация машины Т вычисляет некоторую всюду определенную функцию д(х), то функция д(х) обязательно примитивно рекурсивна? 2.14. Известно, что ?(х) Е Кер и что при всех х ) 0 выполняются соотношения Д(2х) = ? (х + 1) и ?" (2х + 1) = Д(х) .
Вытекает ли отсюда, что? (х) примитивно рекурсивная функция? 2.15. Функции ед(х) и дз(х) являются всюду определенными вычислимыми функциями, удовлетворяющими следующому условию: какова бы ни была примитивно рекурсивная функция у(х), найдется хс такое, что з(хс) < дз(хв) + дз(хс). Показать, что хотя бы одна из функций дз(х) и дз(х) не является примитивно рекурсивной. 2.16. Функция у'(х) принадлежит множеству К„р)К„р (т.
е. общерекурсивна, но не является примитивно рекурсивной функцией). Показать, что каждая из приводимых ниже функций также содержится в множестве К„р~К„р: 1) ?(х+ 3) 2) ?(х — '2); 3) ?(Н); 4) Яз?х)) 5) ?(х дз) 202 Гж 'е'. Зоемеиты теории алгоритмов б) 1(х — ' р'); 7) 1(2и +р); 8) 1(~ Р~). 2.17. Пусть частично рекурсивная функция ~(ж) такова, .что функ- ция д(х), опредсляемая условием ( 0 в тех точках, где ~(х) определена, М.)=' 11 в точках, где Дт) не определена, является общерекурсивной. Показать, что функцию Дх) можно до- определить до общерекурсивной функции.
2.18. Выяснить, образует ли множество М полную систему отно- сительно совокупности операций Ю в классе К„р, если: 1) М = Ки„~Кар, б = 1операции примитивной рекурсии и мини- мизации); 2) М = Кар~Кот Ю = (операция отождествления переменных); 3) М = Кор1К„ю Ю = )операции суперпозиции и минимизации). Глава У1 ГРАФЫ И СЕТИ З 1. Основные понятия теории графов 1.
Простейшие свойства графов. Изоморфизм графов. Пусть г' — - конечное непустое множество и Х вЂ” некоторый набор пар элементов из г'. В наборе Х могут встречаться пары, состоящие из одинаковых элементов, а также одинаковые пары. Множество Ь' и набор Х определяют граф с кратными ребрамп, а петлями (или, короче, гшввдогрпф) С = (Г, Х). Элементы множества Р' называются веришнами псевдографа, а элементы набора Х -- ребрами псевдо- графа. Ребра вида (о, о), о е р', называются петлями.
Псевдограф без петель называется графом с кратпными ребра и (или, короче, мультиграфом). Если в наборе Х нет петель и ни одна пара не встречается более одного раза, то мультиграф С = (Г, Х) называется графом. Ниже почти все определения даются для графов. Эти определения, как правило, легко переносятся на мультиграфы и псевдографы. В тех случаях, когда различия в определениях существенны, даются определения и для псевдографов. Если пары в набора Х являются упорядоченными, то граф называется ориентированным графом (или, короче, орграфом).
Ребра ориентированного графа часто называются дугами. Если пары в наборе Х являются неупорядоченными, то граф называется неоригнтированным графом (или просто графом). Если и = (и, о) †. ребро графа, то вершины и и и называются концами ребра т. Если вершина и является концом ребра и, то говорят, что о и т инцидентны. Вершины и и о графа С называются смежными., если существует ребро графа С, соединяющее их (т. е, (и, о) б Х). Лва ребра называются смежными если они имеют общую вершину.
Степенью вершины о (обозначения д(о) и йе„(о)) называется число ребер графа, инцицентных вершине и. В псевдографе степень вершины и равна общему числу ребер (и петель), инцидентных этой вершине, сложенному с числом петель, инцидентных ей (т.е. каждая петля, инцидентная вершине о, в величину степени вершины о «вносит вклад», равный 2).
Вершина графа, имеющая степень О, 204 Гл. Уй Графы и сети называется изолированной, а вершина, имеющая степень 1, висячей (ипи концевой). Ребро, инцидентное висячей вершине, называют концевым. Последовательность п»х»огхгпз ... ил »х„ †»ив (и Ъ 2), в которой чередуются вершины и ребра и при етом дпя каждого 1 = = 1, ..., и — 1 ребро х; имеет вид (ин и,, »), называется маршрутом, соединяющим всришны и» и ив (или, короче, (ю~, ив)-маршру1пом). Число ребер в маршруте называется его длиной.
Маршрутом длины нуль называется последовательность, состоящая из единственной вершины. Маршрут, в котором всо ребра разные, называется цепью. Маршрут, в котором все вершины разные, называется простой цепью. Маршрут (1) называется замкнуп»ььм, если и» = и„. Замкнутый маршрут, в котором все ребра различные, называется циклом. Цикл, в котором все вершины, кроме первой и последней, разные, называется простым циклом. Граф называется связным, если для любых двух различных его вершин существует цепь (маршрут, простая цепь), соединяющая их.
Расстоянием между вершинами связного графа называется длина кратчайшей (а значит, простой) цепи, соединяющей зти вершины. Яиаметром связного графа называется расстояние между двумя наиболее удаленными друг от друга вершинами. Лиаметр графа С обычно обозначают через Р(С). Подграфо,м графа С называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа С. Подграф называется собственным, если он отличен от самого графа. Компонентой связности (или, короче, компонентой) графа С называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа графа С. Остовным называется подграф, содержащий все вершины графа. Подграфом графа С = (У, Х), порожденным подмножеством П (П С У), называется граф Н = (все, У), множество робер которого состоит из тех и только тех ребер графа С, оба конца которых лежат в П.
Графы (псевдографы) С = (ь'., Х) и Н = (с», У) изоморфны, если существуют такие два взаимно однозначных соответствия ун У е» П и ф; Х е» У, что ддя всякого ребра х = (и, и) из Х справедливо соотношение у»1х) = г»»(и), у»(и)). В случае графов можно дать следующее определение.
Графы С = = (ь'., Х) и Н = (с», У) пзоморфны, если существует такое взаимно однозначное отображение у»: У е» П, что (и, и) е Х тогда и только тогда, когда (у»(и), р(и)) Е У. Такое отображение у» называется изоморфным (или изоморфизма,м). Операция удаления вершины из графа С состоит в удалении некоторой вершины вместе с инцидентными ей ребрами.
Операция уда,— ления ребра из графа С = (Ъ; Х) заключается в удадении соот- г 1. Основные понятия теории графов 205 ветствуюшей пары из набора Х. При этом, если не оговаривается противное, все вершины в графе сохраняются. Дополнением С графа С называется граф, в котором две вершины сможны тогда и только тогда, когда они не смежны в С. Если графы Сз и Сг изоморфны, то их дополнения также изоморфны. Операция подразбагния ребра (и, о) в графе С = (1г, Х) состоит в удалении от Х ребра (и, и), добавлении к К новой вершины ю и добавлении к Х11(и, о)) двух ребер (и, ю) и (ю, о).
Граф С называется подразбиением графа Н, если С может быть получен из Н с помощью операции подразбиения ребра, примененной конечное число раз. В частности, подразбиенисм графа Н является и сам граф Н. Графы С и Н называются гомеоморфными, .если некоторые их подразбиения изоморфны. Объединение.м графов С = (1г, Х) и Н = = Щ У) называется граф г' = (Г 0 О, Х О у ). Деревом называется связный ациклический (т.е.
не имеющий циклов) граф. Ациклический граф называется лесом. Полным называется граф, в котором любые две различные вершины смежны. Полный граф с и вершинами обозначается через К„. Пустым (,вполне несвязным) называется граф, не имеющий ребер. Вполне несвязный граф с л вершинами является, очевидно, дополнением полного графа К„и поэтому часто обозначается через К„. Одновершинный граф без ребер называется тривиа ьным (его можно обозначать через Кь или Кз). Дв удаль ным называется граф, множество вершин которого можно разбить на два непустых подмножества (на две доли) 1гз и 1гг таким образом, что никакис две вершины из одной и той же доли нс являются смежными. Лвудольный граф с долями 1гз и 1'з и множеством ребер Х обычно обозначается через Я, )4з, Х). Если каждая вершина из 1гь смежна с каждой вершиной из 1'з, то двудольный граф называется полным двудольным графом.
Полный двудольный граф ('гы 1гг, Х), у которого ~$'~~ = пь и ~1гз~ = пг, обозначается через К„, „,. Справедлива следующая теорема Л. Кенига: граф является двудольным тогда и только тогда, когда в нем отсутствуют циклы нечетной длины. Граф называется однородным (или регулярным) графом сглгпени д, если все его вершины имеют степень д. Регулярный граф (подграф) степени 1 называется паросочетанаем. Регулярный граф степени 3 называется кубическим:, к-фактором графа называется его остовный однородный подграф степени к. Совершенным паросочетанигм графа называется его 1-фактор. Максимальным паросочгтанием графа называется паросочетание, содержащее наиболыпее число ребер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
