Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 40
Текст из файла (страница 40)
Показать, что хотя бы одна из функций дз(х) и дз(х) не является примитивно рекурсивной. 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-фактор. Максимальным паросочгтанием графа называется паросочетание, содержащее наиболыпее число ребер. Единичным и-мгрным кубом называется граф Н", вершинами которого являются двоичные наборы длины п, а ребрами неупорядоченные пары соседних наборов (см. гл. 1, ~) 1).
206 Гл. Рй Грифы и сети Вершина графа, при удалении которой увеличивается число компонент связности, называется разделяющей (или тонной сочленения). Граф называется 1-соязнььн, если при удалении любых й — 1 его вершин получается связный граф, отличный от тривиального. Всюду в данном параграфе под графом понимается граф без петель и кратных ребер. 1.1. Показать, что для произвольного псевдографа С = (Ъ; Х) справедливо равенство ~ ши) = 2~Х~.
сеи Замечание. Это первая теорема теории графов (принадлежащая Леонарду Эйлеру и опубликованная в 1736 г.). 1.2. Обозначим через п,(С) число вершин степени з в графе С. Построить все попарно неизоморфные графы без петель и кратных ребер, у которых: 1) пз(С) = 1, пз(С) = п4(С) .= 2 и п,ф) = 0 при с' ф 2, 3, 4; 2) пз(С) = 3., пз(С) = 2, п4(С) = 1 и п,(С) = 0 при г ~ 2, 3, 4. 1.3. Изобразить все попарно неизоморфные 4-вершинные графы без петель и кратных ребер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
