Главная » Просмотр файлов » Спец часть (часть 1) (3 поток) (2015) (by Кибитова)

Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601), страница 5

Файл №1161601 Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (Ответы на спец часть) 5 страницаСпец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601) страница 52019-09-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

По теореме Поста система функций {f0, f1, fS, fM, fL} полна. Рассмотрим функцию f0 (x1, …, xn) ∉ T0 (f0 (0, 0, …, 0) = 1). Возможны два случая: a) f0 (1, 1, …, 1) = 1 ⇒ f0 ∉ S ⇒ [f0, f1, fL, fM] = P2 и система {f0, f1, fL, fM} полна. b) f0 (1, 1, …, 1) = 0 ⇒ f0 ∉ M, T1 ⇒ [f0, fL, fS] = P2 и система {f0, fL, fS} полна. 12 Определение 1. Графом называется произвольное множество элементов V и произвольное семейство E пар из V. Обозначение: G = (V, E).В дальнейшем будем рассматривать конечные графы, то есть графы с конечным множеством элементов и конечным семейством пар.Определение 2. Если элементы из E рассматривать как неупорядоченные пары, то графназываетсянеориентированным,пары называютсярёбрами.Есличислаже элементыиз E рас2. Графы, деревья,планарныеа графы;их свойства.Оценкадеревьев.§15.Основные понятия теории графов.

Изоморфизм графов. Связность.сматривать как упорядоченные, то граф ориентированный, а пары — дуги.Определение1.3.ГрафомПара вида(a, a) называетсяпетлёй,если пара(a, b) встречаетсяв сеОпределениеназываетсяпроизвольноемножествоэлементовV и произвольмействе E несколько раз, то она называется кратным ребром (кратной дугой).ноесемейство E пар из V. Обозначение: G = (V, E).Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть неВ дальнейшем будем рассматривать конечные графы, то есть графы с конечным множеориентированным графом (или просто графом), граф без петель — мультиграфом, а мульством элементов и конечным семейством пар.тиграф, в котором разрешены петли — псевдографом.Определение 2.

Если элементы из E рассматривать как неупорядоченные пары, то графОпределение 5. Две вершины графа называются смежными, если они соединены ребром.называется неориентированным, а пары называются рёбрами. Если же элементы из E расОпределение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину.сматривать как упорядоченные, то граф ориентированный, а пары — дуги.Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентныхОпределение 3.

Пара вида (a, a) называется петлёй, если пара (a, b) встречается в седанной вершине. Для псевдографа полагают учитывать петлю дважды.мействе E несколько раз, то она называется кратным ребром (кратной дугой).Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть не2 5ориентированным графом (илипросто графом), граф без петель — мультиграфом, а муль1тиграф, в котором разрешены петли — псевдографом.Определение 5.

Две вершины графа называются смежными,8 если они соединены ребром.7Определение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину.Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентныхданной вершине. Для псевдографаполагают учитыватьпетлю дважды.43 6Глава II. Основы теории графов..25Утверждение 1. В любом графе (псевдографе) справедливо следующее соотношеp1.ние: ∑ deg vi = 2q , где p — число вершин, а q — число рёбер. 87=1iДоказательство. Когда мы считаем степень одной вершины, мы считаем все рёбра, выходящие из неё. Вычисляя сумму всех степеней, мы получаем, что каждое ребро считается43 6 (петли по определению степени также подважды, так как оно инцидентнодвум вершинамсчитаются дважды). Поэтому общая сумма будет равна удвоенному числу рёбер.

Утверждение Утверждениедоказано.1. В любом графе (псевдографе) справедливо следующее соотношеpОпределение 8. Пусть множество вершин графа V = {v1, v2, …, vp}. Тогда матрицейние:2q , гдеp —назовёмчисло вершин,числорёбер.смежностиграфаматрицуа Aq —= ||aaij = 1, если вершины vi и vj смежныij||, где∑ deg vi =этого(2, 3,i =1… для мультиграфа или псевдографа) и 0 в противном случае, aii при этом равно числуДоказательство.петельв вершине vi.

Когда мы считаем степень одной вершины, мы считаем все рёбра, выходящиеиз неё. Вычисляясумму (иливсех псевдографа)степеней, мы Gполучаем,что каждое ребро считаетсяОпределение9. Два графа1 = (V 1 , E 1 ) и G 2 = (V 2 , E 2 ) называютдважды,так как оноеслиинцидентнодвумдвавершинампо определениюстепенитакжепося изоморфными,существуютвзаимно(петлиоднозначныхотображенияφ1: V1 → V2 исчитаютсядважды).Поэтомуобщаясуммабудетравнаудвоенномучислурёбер.Утверждеφ2: E1 → E2 такие, что для любых двух вершин u и v графа G1 справедливо φ2 (u, v) =ние= (φдоказано.1 (u), φ1 (v)).Определениемножествовершин{v1, v2, …,vp}.

ТогдаматрицейОпределение 8.10Пусть(изоморфизмграфовбез графапетельV и= кратныхрёбер).Два графаG1 =смежностиэтогографаназовёмматрицуA=||a||,гдеa=1,есливершиныvиvijij существует взаимноi однозначноеj смежны= (V1, E1) и G2 = (V2, E2) называются изоморфными,если(2,3, … для мультиграфаили псевдографа)противномотображениеφ1: V1 → V2 такое,что (u, v) ∈ Eи1 0⇔в (φ(u), φ (v)) случае,∈ E2. aii при этом равно числупетельОпределениев вершине vi. 11. Граф G = (V , E ) называется подграфом графа G = (V, E), если111Определение 9. Два графа (или псевдографа) G1 = (V1 , E1 ) и G2 = (V2 , E2 ) называютV1взаимно⊆ V, E1 ⊆однозначныхE.ся изоморфными, если существуют дваотображения φ1 : V1 → V2 иφ2: E1 → E2 такие, что для любых двух вершин u и v графа G1 справедливо φ2 (u, v) == (φ1 (u), φ1 (v)).Определение 12.Путём в графеграфовG = (V, E)любая последовательность15 называетсяОпределение10 (изоморфизмбезпетель и кратныхрёбер).

Два графавидаG1 =v,(v,v),v,(v,v),…,v,(v,v),v.001112n–1n–1nn= (V1, E1) и G2 = (V2, E2) называются изоморфными, если существует взаимно однозначноеЧисло n в данныхназывается длиной пути.отображениеφ1: Vобозначениях1 → V2 такое, что (u, v) ∈ E1 ⇔ (φ (u), φ (v)) ∈ E2.Определение 13.путь, в котором нет повторяющихся рёбер.Определение11.ЦепьюГраф Gназывается1 = (V 1 , E 1 ) называется подграфом графа G = (V, E), еслиОпределение 14. Простой цепью называется путь без повторения вершин.V1 ⊆E. P — путь из v1 в v2. Тогда в P можноУтверждение 2.

Пусть в G = (V, E)v1 V,≠ vE2 1и⊆пустьвыделить подпуть из v1 в v2, являющийся простой цепью.Доказательство. Пусть данный путь — не простая цепь. Тогда в нём повторяется некоторая вершина v, то есть он имеет вид: P1 =15v0C1vC2vC3v2. Тогда он содержит подпуть P2 == v0C1vC3v2. Если в P2 повторяется некоторая вершина, то аналогично удалим ещё кусок иv0, (v0, v1), v1, (v1, v2), …, vn – 1, (vn – 1, vn), vn.Определение12.Путёмв0,графеE)…,называетсявидаvv1), v1G, (v=1,(V,vдлинойvпути., vn), vnпоследовательность.0, (v2),n – 1, (vn – 1любаяЧисло n в данных обозначенияхназываетсяv0, (v, v1), v1, (vпуть,v2), …,vn – 1, (vnнетЧислоОпределениеn в данных обозначенияхпути.0называется1,длиной– 1, vn), vn.13.

Цепьюназываетсяв которомповторяющихся рёбер.Определение13.Цепьюназываетсяпуть,вкоторомнетповторяющихсярёбер.Числоnвданныхобозначенияхназываетсядлинойпути.Определение 14. Простой цепью называется путь без повторениявершин.Определениецепью называетсяпуть безнетповторениявершин.рёбер.Определение 14.13. ПростойЦепью называетсяпуть, в которомповторяющихсяУтверждение 2. Пусть в G = (V, E) v1 ≠ v2 и пусть P — путь из v1 в v2. Тогда в P можноОпределение 2.14.

Простойцепьюпуть PбезУтверждениевG=(V, E)называетсяv1 ≠ v2 и пусть—повторенияпуть из v1 ввершин.v2. Тогда в P можновыделить подпуть из vПусть1 в v2, являющийся простой цепью.выделитьподпуть из2.v1Пустьв v2, являющийсяпростойцепью.УтверждениевG=(V,E)v≠vипустьP—путьизvв. Тогда в P можноДоказательство. Пусть данный путь 1— не2 простая цепь. Тогда в 1нёмv2повторяетсянекоДоказательство.данный путь — не простаявыделитьподпутьиз естьvПустьцепью.цепь. Тогда в нём повторяется неко1 в v2, являющийсятораявершинаv, тоон имеет вид: Pпростой1 = v0C1vC2vC3v2.

Тогда он содержит подпуть P2 =тораяДоказательство.вершина v, то есть он имеетвид:P1—= vнеон всодержитподпуть некоP =данныйпутьТогданёмповторяется0Cпростая1vC2vC3vцепь.2. Тогда= v0C1vC3v2. Если в P2 Пустьповторяетсянекотораявершина,тоаналогичноудалимещё кусок2 и=тораяv0C1vCv.ЕсливPповторяетсянекотораявершина,тоаналогичноудалимещёкусоквершинаv,тоестьонимеетвид:P=vCvCvCv.ТогдаонсодержитподпутьP2и=223 2так далее.3 Процессдолжензакончиться, так1 как0P11 —2конечныйпуть.

Утверждение доказано.такПроцессдолжензакончиться,так как Pпуть. Утверждениедоказано.= v0далее.CОпределениеповторяетсянекотораявершина,аналогичноудалим ещёкусок и1 — конечный1vC3v2. Если в15.P2Путьназываетсязамкнутым,если vто0 = vn.Определение15.Путь закончиться,называется замкнутым,еслиv=v.так далее.ПроцессдолжентаккакP—конечныйпуть.Утверждениедоказано.0n1 если он замкнут, и рёбра в нём неОпределение 16. Путь называется циклом,Определение16.ПутьПутьназываетсяназываетсяциклом, если vони рёбра в нём неОпределение15.замкнутым,0 = vзамкнут,n.повторяются.повторяются.Определение17.16.Путьназываетсяциклом,еслии рёбрав нём неОпределениеПутьназываетсяпростымциклом,еслионv =замкнут,v и вершиныне повторяются.Определение 17. Путь называется простым циклом, если v00 = vnn и вершины не повторяются.повторяются.Определение 18.

Граф G = (V, E) называется связным, если для любых вершин vi, vj ∈ VОпределение18. ПутьГрафназываетсяG = (V, E) простымназываетсясвязным,любых вершинvi, vj ∈ VОпределение 17.циклом,еслиеслиv0 = vдляне повторяются.n и вершины(vi ≠ vj) существует путь из vi в vj.(vi ≠ vОпределениеиз vi вGv=j. (V, E) называется связным, если для любых вершин vi, vj ∈ V18. Графj) существует путьРассмотрим отношение vi → vj существования пути из vi в vj.

Оноотношение(vi ≠ Рассмотримvj) существуетпуть из vivвi →v . v существования пути из vi в vj. Оно1) симметрично, так как(vji →j vj) ⇒ (vj → vi),1)симметрично,так какv(vРассмотримотношение→v vсуществованияi→j) ⇒ (vj → vi), пути из v в v . Оно2) транзитивно, так как (vi i → jvj) & (vj → vk) ⇒ (vi → vk), i j2)(vj(v→→vk)vi⇒1) транзитивно,симметрично,тактаккаккак(v(v→vjv) &)⇒), (vi → vk),i→3) рефлексивно, так как ∀i i(vi →j vi). j3)(vi →2) рефлексивно,транзитивно, так как ∀i(vi →vj) v&i).(vj → vk) ⇒ (vi → vk),Таким образом, получено, что vi → vj — отношение эквивалентности и множество вершинТакимобразом, получено,что(vvi i→→vvi).3) рефлексивно,так как ∀ij — отношение эквивалентности и множество вершинразбивается на конечное число классовэквивалентности: V → V1 ∪ V2 ∪ … ∪ Vk, Vi ∩ Vj = ∅ ⇐разбиваетсянаконечноечислоклассовэквивалентности:V → V1 ∪ V2 ∪ …и∪множествоVk, Vi ∩ Vj =∅⇐Таким образом, получено, что v → vj — отношение эквивалентностивершин⇐ i ≠ j.

При этом граф G разбивается iна связныеподграфы, которые называются компонентами⇐i ≠ j. При этомграф G разбиваетсяна связныеподграфы,Vкоторыеразбиваетсяна конечноечисло классовэквивалентности:→ V1 ∪ называютсяV2 ∪ … ∪ Vкомпонентамиk, Vi ∩ Vj = ∅ ⇐связности.связности.⇐ i ≠ j. При этом граф G разбивается на связные подграфы, которые называются компонентамиV1V2Vkсвязности.V1V2V1V2VkVk………Связные компоненты графа GСвязные компоненты графа GСвязные компоненты графа G§16. Деревья.Деревья.

Характеристики

Тип файла
PDF-файл
Размер
10,47 Mb
Высшее учебное заведение

Список файлов ответов (шпаргалок)

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее